Logic and rational languages of words indexed by linear orderings

DOI10.1007/S00224-009-9222-6MaRDI QIDQ987379zbMATH OpenOpenAlexFDO

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

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

automatadecidabilityformal languageslinear orderingsmonadic second-order logic

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Logic and Rational Languages of Words Indexed by Linear Orderings
• Tree Automata and Automata on Linear Orderings
• Regular languages of words over countable linear orderings
• Developments in Language Theory
• A KLEENE THEOREM FOR LANGUAGES OF WORDS INDEXED BY LINEAR ORDERINGS

Cites work

• A KLEENE THEOREM FOR LANGUAGES OF WORDS INDEXED BY LINEAR ORDERINGS
• Application of model theoretic games to discrete linear orders and finite automata
• Automata on linear orderings
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Developments in Language Theory
• Developments in Language Theory
• First-order logic and star-free sets
• Hierarchy among automata on linear orderings
• scientific article; zbMATH DE number 3915652 (Why is no real title available?)
• scientific article; zbMATH DE number 3924161 (Why is no real title available?)
• scientific article; zbMATH DE number 3767656 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 1086492 (Why is no real title available?)
• scientific article; zbMATH DE number 2051168 (Why is no real title available?)
• scientific article; zbMATH DE number 1929934 (Why is no real title available?)
• scientific article; zbMATH DE number 3993564 (Why is no real title available?)
• scientific article; zbMATH DE number 1834651 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• Logic over words on denumerable ordinals
• On finite monoids having only trivial subgroups
• Star-free regular sets of ω-sequences
• The monadic theory of order
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(10)

• Regular languages of words over countable linear orderings
• Logic and Rational Languages of Words Indexed by Linear Orderings
• Tree Automata and Automata on Linear Orderings
• scientific article; zbMATH DE number 3557672 (Why is no real title available?)
• An algebraic approach to MSO-definability on countable linear orderings
• GROUP EXTENSIONS OVER INFINITE WORDS
• OPERATIONAL CHARACTERIZATION OF SCATTERED MCFLs
• Non-emptiness test for automata over words indexed by the reals and rationals
• Deciding reachability in automata on words indexed by the reals and rationals
• An axiomatizable logical foundation for lattice-ordered qualitative linguistic approach for reasoning with words

This page was built for publication: Logic and rational languages of words indexed by linear orderings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q987379)