zbMATH — the first resource for mathematics

Logic and rational languages of words indexed by linear orderings. (English) Zbl 1142.03346
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 76-85 (2008).
Summary: We prove that every rational language of words indexed by linear orderings is definable in monadic second-order logic. We also show that the converse is true for the class of languages indexed by countable scattered linear orderings, but false in the general case. As a corollary we prove that the inclusion problem for rational languages of words indexed by countable linear orderings is decidable.
For the entire collection see [Zbl 1136.68005].

03D05 Automata and formal grammars in connection with logical questions
03B15 Higher-order logic; type theory (MSC2010)
03B25 Decidability of theories and sets of sentences
68Q45 Formal languages and automata
PDF BibTeX Cite
Full Text: DOI