AN ALGEBRAIC APPROACH TO MSO-DEFINABILITY ON COUNTABLE LINEAR ORDERINGS

DOI10.1017/jsl.2018.7zbMath1502.03007arXiv1702.05342OpenAlexW4300342593MaRDI QIDQ4692085

Olivier Carton, Thomas Colcombet, Gabriele Puppis

Publication date: 26 October 2018

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1702.05342

zbMATH Keywords

monoidsrecognizabilitylinear orderingsgeneralized wordsmondaic second-order logic

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Total orders (06A05) Higher-order logic (03B16)

Related Items

First-order logic and its infinitary quantifier extensions over countable words, Unnamed Item, Algebraic characterizations and block product decompositions for first order logic and its infinitary quantifier extensions over countable words, First-order separation over countable ordinals, Unnamed Item, Pro-aperiodic monoids via saturated models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4--8, 2011. Proceedings, Part II
• Factorization forests for infinite words and applications to countable scattered linear orderings
• Automata on linear orderings
• Logic and rational languages of words indexed by linear orderings
• The monadic theory of order
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• The first order properties of products of algebraic systems
• Tree Automata and Automata on Linear Orderings
• Monadic theory of order and topology in ZFC
• Continuous monoids and yields of infinite trees
• AN ALGEBRAIC THEORY FOR REGULAR LANGUAGES OF FINITE AND INFINITE WORDS
• Definability and undefinability with real order at the background
• Composition with Algebra at the Background
• On the Ehrenfeucht-Fraïssé game in theoretical computer science
• COMPLEMENTATION OF RATIONAL SETS ON COUNTABLE SCATTERED LINEAR ORDERINGS
• On the elementary theory of linear order
• Decidability of Second-Order Theories and Automata on Infinite Trees