Time- and tape-bounded turing acceptors and AFLs

作者：

Highlights：

•

摘要

Complexity classes of formal languages defined by time- and tape-bounded Turing acceptors are studied. Sufficient conditions for these classes to be AFLs are given. Further, it is shown that a time-bounded nondeterministic Turing acceptor need have only two storage tapes.

论文关键词：

论文评审过程：Received 23 February 1970, Available online 27 December 2007.

论文官网地址：https://doi.org/10.1016/S0022-0000(70)80031-9