Between SC and LOGDCFL: families of languages accepted by logarithmic-space deterministic auxiliary depth-k storage automata

Abstract

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{A}\mathrm{C}}^1\cap {\mathrm{S}\mathrm{C}}^2$. By replacing a memory device of pushdown automata with an access-controlled storage tape, 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{S}\mathrm{D}\mathrm{A}$. Similarly to $\mathrm{L}\mathrm{O}\mathrm{G}\mathrm{D}\mathrm{C}\mathrm{F}\mathrm{L}$, we study the closure $\mathrm{L}\mathrm{O}\mathrm{G}k\mathrm{S}\mathrm{D}\mathrm{A}$ of all languages in $k\mathrm{S}\mathrm{D}\mathrm{A}$ under $\mathrm{L}$-m-reductions. We demonstrate that $\mathrm{D}\mathrm{C}\mathrm{F}\mathrm{L}\subseteq k\mathrm{S}\mathrm{D}\mathrm{A}\subseteq {\mathrm{S}\mathrm{C}}^k$ by significantly extending Cook's early result (1979) of $\mathrm{D}\mathrm{C}\mathrm{F}\mathrm{L}\subseteq {\mathrm{S}\mathrm{C}}^2$. The entire hierarch of $\mathrm{L}\mathrm{O}\mathrm{G}k\mathrm{S}\mathrm{D}\mathrm{A}$ for all $k\ge 1$ therefore lies between $\mathrm{L}\mathrm{O}\mathrm{G}\mathrm{D}\mathrm{C}\mathrm{F}\mathrm{L}$ and $\mathrm{S}\mathrm{C}$. As an immediate consequence, we obtain the same simulation bounds for Hibbard's limited automata. We further characterize $\mathrm{L}\mathrm{O}\mathrm{G}k\mathrm{S}\mathrm{D}\mathrm{A}$ 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{L}\mathrm{O}\mathrm{G}k\mathrm{S}\mathrm{D}\mathrm{A}$-complete language under $\mathrm{L}$-m-reductions by constructing a two-way universal simulator working for all k-sda's.

Keywords:

• Parallel computation
• deterministic context-free language
• LOGDCFL
• auxiliary storage automata
• multi-head storage automata
• limited automata

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 A read-only tape is called read once if, whenever it reads a tape symbol (except for ε-moves, if any), it must move to the next unread cell.

2 This claim comes from the fact that Hibbard's rewriting systems can be forced to satisfy the blank-skipping property without compromising their computational power [25].

3 The use of stationary move is made in this exposition only for convenience sake. It is also possible to define k-sda's using ε-moves in place of stationary moves.