# Time and Space Complexity of Inside-Out Macro Grammars

Asveld, Peter R.J. (1980) Time and Space Complexity of Inside-Out Macro Grammars. [Report]

 Preview
PDF
3856Kb
 Abstract: Starting form Fischer's IO Standard Form Theorem we show that for each inside-out (or IO-) macro language there exists a -free IO macro grammar with the following property: for each in there is a derivation of of length at most linear in the length of . Then we construct a nondeterministic log-space bounded auxiliary pushdown automaton which accepts 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 . Item Type: Report Faculty: Electrical Engineering, Mathematics and Computer Science (EEMCS) Research Group: Link to this item: http://purl.utwente.nl/publications/66021 Export this item as: BibTeXEndNoteHTML CitationReference Manager

Repository Staff Only: item control page