On the complexity of undecidable problems in automata theory
- 1 January 1967
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 112-116
- https://doi.org/10.1109/focs.1967.23
Abstract
This paper describes some general results about hierarchies of undecidable problems in automata theory, and studies how properties of sets accepted by automata change from decidable to undecidable problems as the memory capacity of the automaton is increased.Keywords
This publication has 4 references indexed in Scilit:
- 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