Time and space complexity of inside-out macro languages

DOI10.1080/00207168108803261MaRDI QIDQ3922197zbMATH OpenOpenAlexFDO

Authors 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

complexity of membership problemlog-space reducibilitynondeterministic log-space bounded auxiliary pushdown automaton

Mathematics Subject Classification ID

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

Cites work

• Bounded nesting in macro grammars
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Extended linear macro grammars, iteration grammars, and register programs
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• Indexed Grammars—An Extension of Context-Free Grammars
• IO and OI. I
• On the complexity of finite, pushdown, and stack automata
• On the Tape Complexity of Deterministic Context-Free Languages
• Recognition of deterministic ETOL languages in logarithmic space
• Space-bounded complexity classes and iterated deterministic substitution
• The complexity of the membership problem for some extensions of context-free languagest†

Cited in

(4)

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

This page was built for publication: Time and space complexity of inside-out macro languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3922197)