\(\omega\)-computations on Turing machines
From MaRDI portal
Publication:1242685
DOI10.1016/0304-3975(78)90002-6zbMath0368.68057OpenAlexW1969470083MaRDI QIDQ1242685
Publication date: 1978
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(78)90002-6
Related Items
The Wadge Hierarchy of Petri Nets ω-Languages, Somewhat finite approaches to infinite sentences., Infinite games specified by 2-tape automata, On the High Complexity of Petri Nets $$\omega $$-Languages, On the complexity of \(\omega\)-type Turing acceptors, Sequential mappings of $\omega $-languages, Computation as an unbounded process, On the topological complexity of \(\omega\)-languages of non-deterministic Petri nets, ON RECOGNIZABLE LANGUAGES OF INFINITE PICTURES, Supertasks do not increase computational power, THREE APPLICATIONS TO RATIONAL RELATIONS OF THE HIGH UNDECIDABILITY OF THE INFINITE POST CORRESPONDENCE PROBLEM IN A REGULAR ω-LANGUAGE, \(X\)-automata on \(\omega\)-words, Infinite behaviour of Petri nets, Decision problems for Turing machines, Polishness of some topologies related to word or tree automata, 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, A note on accelerated Turing machines, Finite automata, definable sets, and regular expressions over \(\omega^n\)- tapes, Highly Undecidable Problems For Infinite Computations, Locally finite ω-languages and effective analytic sets have the same topological complexity, Index sets in computable analysis, Some problems in automata theory which depend on the models of set theory, Real functions and numbers defined by Turing machines, Init and Anf operating on \(\omega\)-languages, Alternating finite automata on \(\omega\)-words, Computability and realizability for interactive computations, The exact complexity of the infinite Post Correspondence Problem, On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words, Effectively closed sets and graphs of computable real functions.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Theories of automata on \(\omega\)-tapes: a simplified approach
- 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 deterministic pushdown machines
- On ω-sets associated with context-free languages
- On the Computational Complexity of Algorithms
- Decision problems forω-automata
- Testing and generating infinite sequences by a finite automaton
- Decidability of Second-Order Theories and Automata on Infinite Trees
