Logic and rational languages of words indexed by linear orderings

DOI10.1007/S00224-009-9222-6zbMath1205.68190OpenAlexW2046438722MaRDI QIDQ987379

Chloé Rispal, Alexis Bès, Nicolas Bedon, Olivier Carton

Publication date: 13 August 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.141.4463

zbMATH Keywords

automatamonadic second-order logicdecidabilityformal languageslinear orderings

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (5)

GROUP EXTENSIONS OVER INFINITE WORDS ⋮ Regular Languages of Words over Countable Linear Orderings ⋮ AN ALGEBRAIC APPROACH TO MSO-DEFINABILITY ON COUNTABLE LINEAR ORDERINGS ⋮ Logic and rational languages of scattered and countable series-parallel posets ⋮ OPERATIONAL CHARACTERIZATION OF SCATTERED MCFLs

Cites Work

• Hierarchy among automata on linear orderings
• Automata on linear orderings
• First-order logic and star-free sets
• The monadic theory of order
• Logic over words on denumerable 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
• On finite monoids having only trivial subgroups
• Developments in Language Theory
• A KLEENE THEOREM FOR LANGUAGES OF WORDS INDEXED BY LINEAR ORDERINGS
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Developments in Language Theory
• 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: Logic and rational languages of words indexed by linear orderings