Stack languages and log n space
作者：
Highlights：
•
摘要
We consider the space complexity of stack languages. The main result is: if a language is accepted by a deterministic (nondeterministic) one-way stack automaton then it is the image under a nonerasing homomorphism of a language accepted by a deterministic (nondeterministic) Turing machine that operates within space log n.
论文关键词：
论文评审过程：Received 4 October 1976, Revised 16 March 1977, Available online 3 December 2003.
论文官网地址：https://doi.org/10.1016/0022-0000(78)90010-7
