Space Lower Bounds for Maze Threadability on Restricted Machines
- 1 August 1980
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 9 (3), 636-652
- https://doi.org/10.1137/0209048
Abstract
No abstract availableKeywords
This publication has 4 references indexed in Scilit:
- Random walks, universal traversal sequences, and the complexity of maze problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Maze recognizing automata and nondeterministic tape complexityJournal of Computer and System Sciences, 1973
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970
- Classes of languages and linear-bounded automataInformation and Control, 1964