TY - BOOK

T1 - Time and Space Complexity of Inside-Out Macro Languages

AU - Asveld, P.R.J.

PY - 1980

Y1 - 1980

N2 - 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$.

AB - 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$.

KW - Inside-out macro grammar

KW - Nondeterministic log-space bounded auxiliary pushdown automaton

KW - Complexity of membership problem

KW - (Many-one) log-space reducibility

KW - HMI-SLT: Speech and Language Technology

M3 - Report

T3 - CWI report

BT - Time and Space Complexity of Inside-Out Macro Languages

PB - Mathematical Centre, Deptartment of Computer Science

CY - Amsterdam

ER -