What are the known computation-friendly well-orderings on words from $A^*$, where $A$ is a finite alphabet, except the standard weightlex and syllable-order?
-
1$\begingroup$ Do you want a partial or a total order? $\endgroup$– J.-E. PinOct 21, 2013 at 16:19
-
$\begingroup$ Clearly, one can find computable well-orderings of this set of any infinite order type up to $\omega_1^{CK}$, provided $A$ is nonempty. $\endgroup$– Joel David HamkinsOct 21, 2013 at 18:16
-
$\begingroup$ Recursive path orderings are very useful in rewriting systems. $\endgroup$– Derek HoltOct 21, 2013 at 19:43
-
$\begingroup$ Jean-Eric: partial orderings would be great, too. $\endgroup$– VictorOct 22, 2013 at 4:23
-
$\begingroup$ Derek: am I right that recursive order is not a well-order? It seems not always possible to apply it to prove that a rewriting system is terminating. $\endgroup$– VictorOct 22, 2013 at 4:24
2 Answers
Here are three relevant references for partial wqo on words:
[1] F. D'Alessandro, S. Varricchio, Well quasi-orders, unavoidable sets, and derivation systems, RAIRO - Theoretical Informatics and Applications 40 (2006) 407-426, DOI
[2] A. Ehrenfeucht, D. Haussler, G. Rozenberg, On regularity of context-free languages, Theoret. Comput. Sci. 27 (1983) 311–332.
[3] M. Kunc, Regular solutions of language inequalities and well quasi-orders, Theoret. Comput. Sci. 348 (2005) 277–293, ISSN 0304-3975, DOI.
There is a combination of lexicographic and graded lexicographic which is quite useful for Groebner Bases for engineering applications. These are admissible orders (in the sense of Mora).
Look for papers in the list
http://math.ucsd.edu/~helton/BILLSPAPERSscanned/bibWEB.pdf
which have a co-author of Mark Stankus and have "Computer" in their title.
Edward Green (from Virginia Tech) call this "noncommutative lex".