Decision problems for Turing machines
DOI10.1016/J.IPL.2009.09.002zbMATH Open1206.68115OpenAlexW1995105191MaRDI QIDQ990079FDOQ990079
Authors: Olivier Finkel, Dominique Lecomte 
Publication date: 2 September 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2009.09.002
Recommendations
- Decision problems and round-off machines
- On decision problems for parameterized machines
- On the complexity of decision problems for some classes of machines and applications
- Decision Problems of Finite Automata Design and Related Arithmetics
- scientific article; zbMATH DE number 1114344
- Intractability of decision problems for finite-memory automata
- scientific article; zbMATH DE number 459363
- scientific article; zbMATH DE number 2096708
- scientific article; zbMATH DE number 4769
computational complexityformal languagestheory of computationdecision problemsTuring machines\(\omega \)-languagesanalytical hierarchy
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Turing machines and related notions (03D10)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Descriptive set theory
- A Glimm-Effros Dichotomy for Borel Equivalence Relations
- \(\omega\)-computations on Turing machines
- Classical recursion theory. Vol. II
- Nondeterministic Ω-Computations and the Analytical Hierarchy
- Title not available (Why is that?)
- Title not available (Why is that?)
- \(X\)-automata on \(\omega\)-words
- Rekursive Folgenmengen I
- Index sets in computable analysis
- On the power of reading the whole infinite input tape
- Title not available (Why is that?)
- Title not available (Why is that?)
- Index sets for ω‐languages
Cited In (6)
- Infinity problems and countability problems for \(\omega \)-automata
- Highly Undecidable Problems For Infinite Computations
- On some decision problems in programming
- Three applications to rational relations of the high undecidability of the infinite Post correspondence problem in a regular \(\omega\)-language
- On the complexity of stream equality
- Polishness of some topologies related to word or tree automata
This page was built for publication: Decision problems for Turing machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q990079)
