Relationships between classifications of regular languages by their ordered syntactic monoids and semilattice-ordered syntactic monoids
by
Libor Polák
Department of Mathematics, Masaryk University, Janáckovo nám. 2a, 662 95 Brno, Czech Republic

A standard construction assigns to any language its syntactic monoid. Certain properties of languages (being star-free, piecewise testable, ...) are characterizable in terms of theirs syntactic monoids. This led to the famous Eilenberg theorem: certain classes of regular languages (called varieties) correspond to so-called pseudovarieties of monoids. J.-E. Pin generalized this theorem using ordered syntactic monoids. Recently the speaker has assigned to any language a semilattice-ordered monoid. An Eilenberg-type theorem also holds here. In our contribution we will compare these classifications.

http://www.math.muni.cz/~polak

Date received: November 3, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafo-12.