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

zbMATH Keywords

computational complexityformal languagestheory of computationdecision problemsTuring machines\(\omega \)-languagesanalytical hierarchy

Mathematics Subject Classification ID

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)

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

Cites Work

• scientific article; zbMATH DE number 512868 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 1458676 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 1836415 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• A Glimm-Effros Dichotomy for Borel Equivalence Relations
• Classical recursion theory. Vol. II
• Descriptive set theory
• Index sets for ω‐languages
• Index sets in computable analysis
• Nondeterministic Ω-Computations and the Analytical Hierarchy
• On the power of reading the whole infinite input tape
• Rekursive Folgenmengen I
• \(X\)-automata on \(\omega\)-words
• \(\omega\)-computations on Turing machines

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)