zbMATH — the first resource for mathematics

On logical descriptions of regular languages. (English) Zbl 1059.03034
Rajsbaum, Sergio (ed.), LATIN 2002: Theoretical informatics. 5th Latin American symposium, Cancun, Mexico, April 3–6, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43400-3). Lect. Notes Comput. Sci. 2286, 528-538 (2002).
Summary: There are many examples in the research literature of families of regular languages defined by purely model-theoretic means (that is, in terms of the kinds of formulas of predicate logic used to define them) that can be characterized algebraically (that is, in terms of the syntactic monoids or syntactic morphisms of the languages). In fact the existence of such algebraic characterizations appears to be the rule. The present paper gives an explanation of the phenomenon: A generalization of Eilenberg’s variety theorem is proved and then applied to logic. We find that a very wide assortment of families of regular languages defined in model-theoretic terms form varieties in this new sense, and that consequently membership in the family depends only on the syntactic morphism of the language.
For the entire collection see [Zbl 0989.00058].

03C98 Applications of model theory
68Q45 Formal languages and automata
68Q70 Algebraic theory of languages and automata
03D05 Automata and formal grammars in connection with logical questions
Full Text: Link