5
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ Do you want a partial or a total order? $\endgroup$
    – J.-E. Pin
    Oct 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$ Oct 21, 2013 at 18:16
  • $\begingroup$ Recursive path orderings are very useful in rewriting systems. $\endgroup$
    – Derek Holt
    Oct 21, 2013 at 19:43
  • $\begingroup$ Jean-Eric: partial orderings would be great, too. $\endgroup$
    – Victor
    Oct 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$
    – Victor
    Oct 22, 2013 at 4:24

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.