On the Complexity of Undecidable Problems in Automata Theory
- 1 January 1969
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 16 (1) , 160-167
- https://doi.org/10.1145/321495.321507
Abstract
Some general results about hierarchies of undecidable problems in automata theory are given, and studies are described which show how properties of sets accepted by automata (i.e. languages) change from decidable to undecidable problems as the computational power of the automata is increased. This work also yields unified techniques which characterize for different languages large classes of undecidable problems.Keywords
This publication has 5 references indexed in Scilit:
- Nonerasing stack automataJournal of Computer and System Sciences, 1967
- A Machine-Independent Theory of the Complexity of Recursive FunctionsJournal of the ACM, 1967
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965
- Hierarchies of memory limited computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1965
- Memory bounds for recognition of context-free and context-sensitive languagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1965