A Hierarchy of Automaticω-Words having a Decidable MSO Theory

DOI10.1051/ITA:2008008MaRDI QIDQ3526410zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Vince Bárány

Publication date 25 September 2008

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/246081

zbMATH Keywords

automatic structuresmonadic second-order logicautomatic sequencesfinite automatonmorphic wordslexicographic hierarchieslexicographic word orderingrecognizability by finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Grammars and rewriting systems (68Q42) Combinatorics on words (68R15) Decidability of theories and sets of sentences (03B25) Hierarchies of computability and definability (03D55)

Recommendations

• Deciding monadic second order logic over \(\omega \)-words by specialized finite automata
• Infinite trees and automaton-definable relations over -words
• Brzozowski hierarchy of \(\omega\)-languages
• Infinite and bi-infinite words with decidable monadic theories
• The monadic theory of morphic infinite words and generalizations

Cites work

• scientific article; zbMATH DE number 3841819 (Why is no real title available?)
• scientific article; zbMATH DE number 3911740 (Why is no real title available?)
• scientific article; zbMATH DE number 3974304 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 1223638 (Why is no real title available?)
• scientific article; zbMATH DE number 2040323 (Why is no real title available?)
• scientific article; zbMATH DE number 1929935 (Why is no real title available?)
• scientific article; zbMATH DE number 2086419 (Why is no real title available?)
• scientific article; zbMATH DE number 1916667 (Why is no real title available?)
• scientific article; zbMATH DE number 2102748 (Why is no real title available?)
• scientific article; zbMATH DE number 806750 (Why is no real title available?)
• scientific article; zbMATH DE number 1400048 (Why is no real title available?)
• A Combinatorial Theorem for Trees
• A topological approach to transductions
• Automata Presenting Structures: A Survey of the Finite String Case
• Automata, logics, and infinite games. A guide to current research
• Automatic Sequences
• Automatic graphs and D0L-sequences of finite graphs
• Bertrand numeration systems and recognizability
• Context-Sensitive Languages, Rational Graphs and Determinism
• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
• Decidability questions related to abstract numeration systems
• Decidable Theories of the Ordering of Natural Numbers with Unary Predicates
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Families of automata characterizing context-sensitive languages
• Finite presentations of infinite structures: Automata and interpretations
• Invariants of Automatic Presentations and Semi-synchronous Transductions
• Iterated GSMs and CO-CFL
• Iterated pushdown automata and sequences of rational numbers
• Logic and p-recognizable sets of integers
• Mathematical Foundations of Computer Science 2003
• Monadic second-order logic on tree-like structures
• Monadic second-order logic, graph coverings and unfoldings of transition systems
• On decidability of monadic logic of order over the naturals extended by monadic predicates
• STACS 2004
• Synchronized rational relations of finite and infinite words
• The Monadic Theory of Tree-like Structures
• The monadic second-order logic of graphs. IX: Machines and their behaviours
• The monadic theory of morphic infinite words and generalizations
• The monadic theory of order
• The theory of ends, pushdown automata, and second-order logic
• Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem

Cited in

(4)

• Deciding monadic second order logic over \(\omega \)-words by specialized finite automata
• The isomorphism problem on classes of automatic structures with transitive relations
• Logic for \(\omega\)-pushdown automata
• On the complexity of infinite advice strings

This page was built for publication: A Hierarchy of Automaticω-Words having a Decidable MSO Theory

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