Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

Time and Space Complexity of Inside-Out Macro Languages

Share/Save/Bookmark

Asveld, Peter R.J. (1981) Time and Space Complexity of Inside-Out Macro Languages. International Journal of Computer Mathematics, 10 (1). pp. 3-14. ISSN 0020-7160

[img]
Preview
PDF
3856Kb
Abstract:Starting from Fischer's IO Standard Form Theorem we show that for each inside-out (or IO-) macro language $L$, there is 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$.
Item Type:Article
Copyright:© 1981 Taylor & Francis
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65997
Official URL:http://dx.doi.org/10.1080/00207168108803261
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page