Finite automata, definable sets, and regular expressions over \(\omega^n\)- tapes

DOI10.1016/0022-0000(78)90036-3zbMath0386.03018MaRDI QIDQ1249573

Yaacov Choueka

Publication date: 1978

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

Full work available at URL: https://doi.org/10.1016/0022-0000(78)90036-3

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03D05: Automata and formal grammars in connection with logical questions

03B25: Decidability of theories and sets of sentences

Related Items

Automata, Semigroups and Recognizability of Words on Ordinals, TRANSFINITE EQUATIONS IN TRANSFINITE STRINGS, Axiomatizing omega and omega-op powers of words, OPERATIONAL CHARACTERIZATION OF SCATTERED MCFLs, On Reachability Games of Ordinal Length, A KLEENE THEOREM FOR LANGUAGES OF WORDS INDEXED BY LINEAR ORDERINGS, ON CONTEXT-FREE LANGUAGES OF SCATTERED WORDS, Long words: The theory of concatenation and \(\omega\)-power, First-order separation over countable ordinals, Büchi context-free languages, On Müller context-free grammars, Test sets for equality of terms in the additive structure of ordinals augmented with right multiplication by \(\omega\), Factorization forests for infinite words and applications to countable scattered linear orderings, Automata on linear orderings, Finite automata and ordinals, The equational theory of regular words, Star-free sets of words on ordinals, Complementation of rational sets on scattered linear orderings of finite rank, MSO-definable Properties of Muller Context-Free Languages Are Decidable, Automata on Ordinals and Linear Orders, REASONING ABOUT TRANSFINITE SEQUENCES

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Theories of automata on \(\omega\)-tapes: a simplified approach
• The monadic second order theory of all countable ordinals
• \(\omega\)-computations on Turing machines
• On ω-sets associated with context-free languages
• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
• Decision methods in the theory of ordinals
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees