AN ALGEBRAIC APPROACH TO MSO-DEFINABILITY ON COUNTABLE LINEAR ORDERINGS
From MaRDI portal
Publication:4692085
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
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