English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The closure of deterministic context-free languages under logarithmic-spacemany-one reductions ($\mathrm{L}$-m-reductions), known as LOGDCFL, has beenstudied in depth from an aspect of parallel computability because it is nicelysituated between $\mathrm{L}$ and $\mathrm{AC}^{1}\cap\mathrm{SC}^2$. Byreplacing a memory device from pushdown stacks with access-controlled storagetapes, we introduce a computational model of one-way deterministic depth-$k$storage automata ($k$-sda's) whose tape cells are freely modified during thefirst $k$ accesses and then become blank forever. These $k$-sda's naturallyinduce the language family $k\mathrm{SDA}$. Similarly to $\mathrm{LOGDCFL}$, westudy 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 significantlyextending 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$ thereforelies between $\mathrm{LOGDCFL}$ and $\mathrm{SC}$. As an immediate consequence,we obtain the same simulation bounds for Hibbard's limited automata. We furthercharacterize $\mathrm{LOG}k\mathrm{SDA}$ in terms of a new machine model,called logarithmic-space deterministic auxiliary depth-$k$ storage automatathat run in polynomial time. These machines are as powerful as apolynomial-time two-way multi-head deterministic depth-$k$ storage automata. Wealso provide a ``generic'' $\mathrm{LOG}k\mathrm{SDA}$-complete language under$\mathrm{L}$-m-reductions by constructing a two-way universal simulator workingfor all $k$-sda's.

Between SC and LOGDCFL: Families of Languages Accepted by Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata