The use of lists in the study of undecidable problems in automata theory

DOI10.1016/S0022-0000(71)80007-7MaRDI QIDQ2551463zbMATH OpenOpenAlexFDO

Authors J. Hartmanis, Forbes D. Lewis

Publication date 1971

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0022-0000(71)80007-7

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10) Undecidability and degrees of sets of sentences (03D35)

Cites work

• Computing degrees of unsolvability
• Creative sets
• General Problems of Formal Grammars
• Gödel numberings of partial recursive functions
• scientific article; zbMATH DE number 3131080 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3302285 (Why is no real title available?)
• Number theoretic concepts and recursive well-orderings
• Recursive Predicates and Quantifiers
• Recursively enumerable sets of positive integers and their decision problems

Cited in

(4)

• Some lowness properties and computational complexity sequences
• Index sets and presentations of complexity classes
• A second step towards complexity-theoretic analogs of Rice's Theorem
• P-selectivity: Intersections and indices

This page was built for publication: The use of lists in the study of undecidable problems in automata theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2551463)