论文标题
在SC和LogDCFL之间：对数空间确定性辅助深度-K存储自动机接受的语言家族
Between SC and LOGDCFL: Families of Languages Accepted by Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata
论文作者
论文摘要
从对数空间多一的减少（$ \ mathrm {l} $ - m- reductions）（称为logdcfl）下的确定性无上下文语言的关闭已从并行可计算性的方面进行了深入研究，因为它位于$ \ mathrm {l} $和$ \ mathrm {ac}^{1} \ cap \ mathrm {sc}^2 $。通过使用访问控制的存储录像带从下降堆栈中替换存储设备，我们引入了单向确定性深度 - $ K $存储自动机（$ k $ -sda）的计算模型，其磁带单元在第一个$ k $ accesses中被自由修改，然后永远变为空白。这些$ k $ -sda的自然会诱导语言家族$ k \ mathrm {sda} $。与$ \ mathrm {logdcfl} $类似，我们研究了$ k \ mathrm {sda} $ in $ k \ mathrm {sda} $ of $ k \ mathrm {sda} $的关闭$ \ mathrm {log} k \ mathrm {sda} $。我们证明了$ \ mathrm {dcfl} \ subseteq k \ mathrm {sda} \ subseteq \ subseteq \ mathrm {sc}^k $，通过显着扩展了库克的早期结果（1979）的$ \ \ \ \ \ m mathrm {dcfl} {dcfl} \ subseteq \ subSeteq \ subseteq \ sebseteq \ mathrm {sc} $。 $ \ mathrm {log} k \ mathrm {sda} $的整个层次均为所有$ k \ geq1 $。直接结果，我们获得了Hibbard有限自动机的相同模拟界限。我们进一步表征了$ \ mathrm {log} k \ mathrm {sda} $在新机器模型的角度，称为对数空间确定性辅助深度 - $ k $ k $存储自动机，以多项式时间运行。这些计算机与多项式的双向多头确定性深度 - $ K $存储自动机一样强大。我们还提供了``通用''$ \ mathrm {log} k \ mathrm {sda} $ - $ \ mathrm {l} $下的完整语言 - 通过构造所有$ k $ sda的双向通用模拟器，通过构造双向通用模拟器来工作。
The closure of deterministic context-free languages under logarithmic-space many-one reductions ($\mathrm{L}$-m-reductions), known as LOGDCFL, has been studied in depth from an aspect of parallel computability because it is nicely situated between $\mathrm{L}$ and $\mathrm{AC}^{1}\cap\mathrm{SC}^2$. By replacing a memory device from pushdown stacks with access-controlled storage tapes, we introduce a computational model of one-way deterministic depth-$k$ storage automata ($k$-sda's) whose tape cells are freely modified during the first $k$ accesses and then become blank forever. These $k$-sda's naturally induce the language family $k\mathrm{SDA}$. Similarly to $\mathrm{LOGDCFL}$, we study the closure $\mathrm{LOG}k\mathrm{SDA}$ of all languages in $k\mathrm{SDA}$ under $\mathrm{L}$-m-reductions. We demonstrate that $\mathrm{DCFL}\subseteq k\mathrm{SDA}\subseteq \mathrm{SC}^k$ by significantly extending Cook's early result (1979) of $\mathrm{DCFL}\subseteq \mathrm{SC}^2$. The entire hierarch of $\mathrm{LOG}k\mathrm{SDA}$ for all $k\geq1$ therefore lies between $\mathrm{LOGDCFL}$ and $\mathrm{SC}$. As an immediate consequence, we obtain the same simulation bounds for Hibbard's limited automata. We further characterize $\mathrm{LOG}k\mathrm{SDA}$ in terms of a new machine model, called logarithmic-space deterministic auxiliary depth-$k$ storage automata that run in polynomial time. These machines are as powerful as a polynomial-time two-way multi-head deterministic depth-$k$ storage automata. We also provide a ``generic'' $\mathrm{LOG}k\mathrm{SDA}$-complete language under $\mathrm{L}$-m-reductions by constructing a two-way universal simulator working for all $k$-sda's.
