Between SC and LOGDCFL: families of languages accepted by logarithmic-space deterministic auxiliary depth-k storage automata. Issue 1 (2nd January 2023)

• Record Type: Journal Article
• Authors: Yamakami, Tomoyuki
• Is Part Of: International journal of computer mathematics. Volume 8:Issue 1(2023)
• Page Start: 1
• Page End: 31
• Publication Date: 2023-01-02
• Subjects: Parallel computation -- deterministic context-free language -- LOGDCFL -- auxiliary storage automata -- multi-head storage automata -- limited automata; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2023.2166872
• Languages: English
• ISSNs: 2379-9927

Abstract

Abstract : The closure of deterministic context-free languages under logarithmic-space many-one reductions ( L -m-reductions), known as LOGDCFL, has been studied in depth from an aspect of parallel computability because it is nicely situated between L and A C 1 ∩ S 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 S D A . Similarly to L O G D C F L, we study the closure L O G k S D A of all languages in k S D A under L -m-reductions. We demonstrate that D C F L ⊆ k S D A ⊆ S C k by significantly extending Cook's early result (1979) of D C F L ⊆ S C 2 . The entire hierarch of L O G k S D A for all k ≥ 1 therefore lies between L O G D C F L and S C . As an immediate consequence, we obtain the same simulation bounds for Hibbard's limited automata. We further characterize L O G k S D 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' L O G k S D A -complete language under L -m-reductions by constructing a two-way universal simulator working for all k -sda's.