@book{05be91c8554943768c23c98a2f40492d,

title = "Time and Space Complexity of Inside-Out Macro Languages",

abstract = "Starting form Fischer's IO Standard Form Theorem we show that for each inside-out (or IO-) macro language $L$ there exists a $\lambda$-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 = "Inside-out macro grammar, Nondeterministic log-space bounded auxiliary pushdown automaton, Complexity of membership problem, (Many-one) log-space reducibility, HMI-SLT: Speech and Language Technology",

author = "P.R.J. Asveld",

year = "1980",

language = "English",

series = "CWI report",

publisher = "Mathematical Centre",

number = "141/80",

}