-computations on Turing machines
From MaRDI portal
Publication:1242685
DOI10.1016/0304-3975(78)90002-6zbMATH Open0368.68057OpenAlexW1969470083MaRDI QIDQ1242685FDOQ1242685
Authors: Rina S. Cohen, Arie Y. Gold 
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
Cites Work
- On the Computational Complexity of Algorithms
- Title not available (Why is that?)
- Decidability of Second-Order Theories and Automata on Infinite Trees
- Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages
- Title not available (Why is that?)
- Testing and generating infinite sequences by a finite automaton
- Theories of automata on \(\omega\)-tapes: a simplified approach
- Decision problems forω-automata
- \(\omega\)-computations on deterministic pushdown machines
- On ω-sets associated with context-free languages
- Theory of \(\omega\)-languages. II: A study of various models of \(\omega\)- type generation and recognition
- Title not available (Why is that?)
Cited In (30)
- Infinite behaviour of Petri nets
- Computation as an unbounded process
- ON RECOGNIZABLE LANGUAGES OF INFINITE PICTURES
- Highly Undecidable Problems For Infinite Computations
- Decision problems for Turing machines
- On the topological complexity of \(\omega\)-languages of non-deterministic Petri nets
- Computability and realizability for interactive computations
- Sequential mappings of $\omega $-languages
- Index sets in computable analysis
- Locally finite \(\omega\)-languages and effective analytic sets have the same topological complexity
- The exact complexity of the infinite Post Correspondence Problem
- \(X\)-automata on \(\omega\)-words
- Theory of \(\omega\)-languages. II: A study of various models of \(\omega\)- type generation and recognition
- Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages
- Infinite games specified by 2-tape automata
- Three applications to rational relations of the high undecidability of the infinite Post correspondence problem in a regular \(\omega\)-language
- Alternating finite automata on \(\omega\)-words
- Supertasks do not increase computational power
- Real functions and numbers defined by Turing machines
- On the complexity of \(\omega\)-type Turing acceptors
- Finite automata, definable sets, and regular expressions over \(\omega^n\)- tapes
- Somewhat finite approaches to infinite sentences.
- Init and Anf operating on \(\omega\)-languages
- Effectively closed sets and graphs of computable real functions.
- On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
- On the high complexity of Petri nets \(\omega \)-languages
- Polishness of some topologies related to word or tree automata
- Some problems in automata theory which depend on the models of set theory
- The Wadge hierarchy of Petri nets \(\omega\)-languages
- A note on accelerated Turing machines
This page was built for publication: \(\omega\)-computations on Turing machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1242685)
