On the complexity of \(\omega\)-type Turing acceptors

DOI10.1016/0304-3975(80)90049-3zbMath0432.68040OpenAlexW67599404MaRDI QIDQ1138912

Rina S. Cohen, Arie Y. Gold

Publication date: 1980

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(80)90049-3

zbMATH Keywords

complexity classesinfinite computationsTuring acceptors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Alternation and \(\omega\)-type Turing acceptors, Somewhat finite approaches to infinite sentences., Real functions and numbers defined by Turing machines, Init and Anf operating on \(\omega\)-languages, Computability and realizability for interactive computations

Cites Work

• A Mathematical Theory of Communication
• Theories of automata on \(\omega\)-tapes: a simplified approach
• A decidability result for deterministic \(\omega\)-context-free languages
• Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages
• Theory of \(\omega\)-languages. II: A study of various models of \(\omega\)- type generation and recognition
• \(\omega\)-computations on Turing machines
• \(\omega\)-computations on deterministic pushdown machines
• On ω-sets associated with context-free languages
• Decision problems forω-automata
• Testing and generating infinite sequences by a finite automaton
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item