Time and space complexity of inside-out macro languages

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)².

Keywords:

• Inside-out macro grammar
• complexity of membership problem
• (many-one) log-space reducibility
• nondeterministic log-space bounded auxiliary pushdown automaton

C R. Categories:

• 5.23
• 5.25