Schützenberger and Eilenberg theorems for words on linear orderings

DOI10.1016/j.jcss.2011.06.003zbMath1279.68129OpenAlexW1975463147MaRDI QIDQ414913

Nicolas Bedon, Chloé Rispal

Publication date: 11 May 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.06.003

zbMATH Keywords

first-order logicvarietiesregular languagestransfinite wordsinfinite wordsrecognizable languageslinear orderingsrational languagesstar-free sets

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Related Items (3)

Recognisable Languages over Monads ⋮ First-order separation over countable ordinals ⋮ Logic and rational languages of scattered and countable series-parallel posets

Cites Work

• Automata on linear orderings
• First-order logic and star-free sets
• Unambiguous Büchi automata.
• Logic over words on denumerable ordinals
• Star-free sets of words on ordinals
• Weak Second‐Order Arithmetic and Finite Automata
• Application of model theoretic games to discrete linear orders and finite automata
• Star-free regular sets of ω-sequences
• Automata, Semigroups and Recognizability of Words on Ordinals
• On finite monoids having only trivial subgroups
• COMPLEMENTATION OF RATIONAL SETS ON COUNTABLE SCATTERED LINEAR ORDERINGS
• Developments in Language Theory
• $ℵ_0$-categoricity of linear orderings
• Decision methods in the theory of ordinals
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Schützenberger and Eilenberg theorems for words on linear orderings