A Simulation Result for Simultaneously Bounded AuxPDAs

スポンサーリンク

概要

• 論文の詳細を見る

• Let S(n) be a space constructible function such that S(n)≧log n. In this paper, we show that AuxSpTu (S(n),T(n))⫅NSPACE(S(n)・logT(n)), where AuxSpTu (S(n),T(n)) is the class of languages accepted by nondeterministic auxiliary pushdown automata operating simultaneously in O(S(n)) space and O(T(n)) turns of the auxiliary tape head.

• 一般社団法人電子情報通信学会の論文
• 1994-06-25

著者

• Nishino Tetsuro

  School Of Information Science Japan Advanced Institute Of Science And Technology

関連論文

• On the Negation-Limited Circuit Complexity of Clique Functions
• The Emptiness Problem for Lexical-Functional Grammars is Undecidable
• A Simulation Result for Simultaneously Bounded AuxPDAs
• On the Number of Negations Needed to Compute Parity Functions

スポンサーリンク