Between SC and LOGDCFL: families of languages accepted by polynomial-time logarithmic-space deterministic auxiliary depth-\(k\) storage automata

DOI10.1007/978-3-030-89543-3_14OpenAlexW3209167006MaRDI QIDQ2695283

Tomoyuki Yamakami

Publication date: 30 March 2023

Full work available at URL: https://doi.org/10.1007/978-3-030-89543-3_14

zbMATH Keywords

parallel computationdeterministic context-free languageSCauxiliary storage automatadepth-\(k\) storage automatalogarithmic-space many-one reductionLOGDCFLmulti-head storage automata

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Related Items (1)

Nondeterministic auxiliary depth-bounded storage automata and semi-unbounded fan-in cascading circuits (extended abstract)

Cites Work

• Behavioral strengths and weaknesses of various models of limited automata
• On non-determinacy in simple computing devices
• Limited Automata and Context-Free Languages
• The recognition of deterministic CFLs in small time and space
• Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
• On the Tape Complexity of Deterministic Context-Free Languages
• LIMITED AUTOMATA AND REGULAR LANGUAGES
• Deterministic context free languages
• Stack automata and compiling
• A generalization of context-free determinism
• One-way stack automata
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

This page was built for publication: Between SC and LOGDCFL: families of languages accepted by polynomial-time logarithmic-space deterministic auxiliary depth-\(k\) storage automata