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

DOI10.1016/0022-0000(78)90036-3zbMath0386.03018OpenAlexW1967376291MaRDI 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

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Related Items (21)

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Finite automata, definable sets, and regular expressions over \(\omega^n\)- tapes