Automata on linear orderings

DOI10.1016/j.jcss.2006.10.009zbMath1178.68307OpenAlexW2056871658MaRDI QIDQ859978

Olivier Carton, Véronique Bruyère

Publication date: 22 January 2007

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.2006.10.009

zbMATH Keywords

automatachainslinear orderingsrational expressions

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (18)

Schützenberger and Eilenberg theorems for words on linear orderings ⋮ Büchi context-free languages ⋮ Universal first-order quantification over automata ⋮ Regular Languages of Words over Countable Linear Orderings ⋮ EQUATIONAL DESCRIPTIONS OF LANGUAGES ⋮ Logic and rational languages of words indexed by linear orderings ⋮ Complementation of Branching Automata for Scattered and Countable N-Free Posets ⋮ Unnamed Item ⋮ AN ALGEBRAIC APPROACH TO MSO-DEFINABILITY ON COUNTABLE LINEAR ORDERINGS ⋮ An Analysis of the Fuller Phenomenon on Transfinite Hybrid Automata ⋮ Tree Automata and Automata on Linear Orderings ⋮ Logic and rational languages of scattered and countable series-parallel posets ⋮ Complementation of Branching Automata for Scattered and Countable Series-Parallel Posets ⋮ Craig Interpolation for Linear Temporal Languages ⋮ MSO-definable Properties of Muller Context-Free Languages Are Decidable ⋮ On Müller context-free grammars ⋮ ON CONTEXT-FREE LANGUAGES OF SCATTERED WORDS ⋮ OPERATIONAL CHARACTERIZATION OF SCATTERED MCFLs

Cites Work

• Finite divergence
• Bilimites de langages reconnaissables
• The monadic theory of order
• Finite automata, definable sets, and regular expressions over \(\omega^n\)- tapes
• Weak Second‐Order Arithmetic and Finite Automata
• On frontiers of regular trees
• COMPLEMENTATION OF RATIONAL SETS ON COUNTABLE SCATTERED LINEAR ORDERINGS
• Developments in Language Theory
• $ℵ_0$-categoricity of linear orderings
• On the Forms of the Predicates in the Theory of Constructive 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

This page was built for publication: Automata on linear orderings