Time and space complexity of inside-out macro languages

DOI10.1080/00207168108803261zbMath0468.68089OpenAlexW2148476405MaRDI QIDQ3922197

Peter R. J. Asveld

Publication date: 1981

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207168108803261

zbMATH Keywords

log-space reducibilitycomplexity of membership problemnondeterministic log-space bounded auxiliary pushdown automaton

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Pattern selector grammars and several parsing algorithms in the context- free style, Abstract grammars based on transductions, Polynomial-time inverse computation for accumulative functions with multiple data traversals, Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity

Cites Work

• Unnamed Item
• Unnamed Item
• IO and OI. I
• Extended linear macro grammars, iteration grammars, and register programs
• Bounded nesting in macro grammars
• Space-bounded complexity classes and iterated deterministic substitution
• On the complexity of finite, pushdown, and stack automata
• Recognition of deterministic ETOL languages in logarithmic space
• On the Tape Complexity of Deterministic Context-Free Languages
• The complexity of the membership problem for some extensions of context-free languagest†
• Indexed Grammars—An Extension of Context-Free Grammars
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers