DMTCS Proceedings, Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001

Font Size:  Small  Medium  Large

A Poset Classifying Non-Commutative Term Orders

Jan Snellman


We study a poset N on the free monoid (X*) on a countable alphabet X. This poset is determined by the fact that its total extensions are precisely the standard term orders on X*. We also investigate the poset classifying degree-compatible standard term orders, and the poset classifying sorted term orders. For the latter poset, we give a Galois coconnection with the Young lattice.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional