Johannes Waldmann - Matchbox for String Rewriting

Matchbox for String Rewriting

Computations are performed with limited resources. So if you want to handle more complicated input, please download and compile the programs on your own.

Control expression
The default is the "WST contest version" that tries to decide termination by checking for loops (in absence of a prescribed strategy) and looking for match bounds for the original and for the reversed system (in absence of a theory).
not (loop . nostrategy) par ( (approx match . rfc . id or reverse . fill . notheory) before (empty . (discount . remove . rfc . id or reverse)^* . fill . notheory))
Maximum size of intermediate automata? (Larger automata will stop the computation.)
Automata graphs will be output as .dot files, and they can be rendered into .png and .eps graphics.
Maximum size of rendered automata?
If rendered, .png files can be embedded in the HTML output.
Maximum size of displayed automata?

Decomposition for Deleting Rewrite Systems

You can input a deleting rewrite system here, and I will show its transformation into a product of a substitution and an inverse context-free system.

Note that the system has to be deleting w.r.t. the alphabetical ordering (a > b > c > ...), and left hand sides of rules have to have distinct letters.

Match-Bounds and Change-Bounds

For comparison, you can use change bounds as defined by Ravikumar. Note that this only work for length-preserving systems.

Back to Matchbox main page

http://www.imn.htwk-leipzig.de/~waldmann/