Time and space complexity of inside-out macro languages
- 1 January 1981
- journal article
- research article
- Published by Taylor & Francis in International Journal of Computer Mathematics
- Vol. 10 (1) , 3-14
- https://doi.org/10.1080/00207168108803261
Abstract
Starting from Fischer's IO Standard Form Theorem we show that for each inside-out (or IO) macro language L there exists a λ-free IO-macro grammar with the following property: for each x in L there is a derivation of x of length at most linear in the length of x. Then we construct a nondeterministic log-space bounded auxiliary pushdown automaton which accepts L in polynomial time. Therefore the IO-macro languages are (many-one) log-space reducible to the context-free languages. Consequently, the membership problem for IO-macro languages can be solved deterministically in polynomial time and in space (log n)2.Keywords
This publication has 12 references indexed in Scilit:
- Space-bounded complexity classes and iterated deterministic substitutionInformation and Control, 1980
- Bounded nesting in macro grammarsInformation and Control, 1979
- Extended linear macro grammars, iteration grammars, and register programsActa Informatica, 1979
- On the Tape Complexity of Deterministic Context-Free LanguagesJournal of the ACM, 1978
- IO and OI. IJournal of Computer and System Sciences, 1977
- Recognition of deterministic ETOL languages in logarithmic spaceInformation and Control, 1977
- The complexity of the membership problem for some extensions of context-free languagest†International Journal of Computer Mathematics, 1977
- On the complexity of finite, pushdown, and stack automataTheory of Computing Systems, 1976
- Characterizations of Pushdown Machines in Terms of Time-Bounded ComputersJournal of the ACM, 1971
- Indexed Grammars—An Extension of Context-Free GrammarsJournal of the ACM, 1968