Time and space complexity of inside-out macro languages : (preprint)
P.R.J. Asveld · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1980
Starting from Fischer's IO Standard Form Theorem we show that for each inside-out (or IO-) macro language L there exists a 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 Lin polynomial time.Therefore the IO-macro languages are (many-one) logspace 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 •