Nondeterministic auxiliary depth-bounded storage automata and semi-unbounded fan-in cascading circuits (extended abstract)
From MaRDI portal
Publication:6168931
DOI10.1007/978-3-031-22105-7_6OpenAlexW4313351085MaRDI QIDQ6168931
Publication date: 10 August 2023
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-031-22105-7_6
Cites Work
- Unnamed Item
- Intersection and union hierarchies of deterministic context-free languages and pumping lemmas
- Tree-size bounded alternation
- On uniform circuit complexity
- Properties that characterize LOGCFL
- Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits
- Behavioral strengths and weaknesses of various models of limited automata
- Between SC and LOGDCFL: families of languages accepted by polynomial-time logarithmic-space deterministic auxiliary depth-\(k\) storage automata
- On the Tape Complexity of Deterministic Context-Free Languages
- LIMITED AUTOMATA AND REGULAR LANGUAGES
- Deterministic context free languages
- A generalization of context-free determinism
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
