Time and Space Complexity of Inside-Out Macro Languages

Peter R.J. Asveld

    Research output: Contribution to journalArticleAcademicpeer-review

    11 Citations (Scopus)
    15 Downloads (Pure)

    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$.
    Original languageEnglish
    Pages (from-to)3-14
    Number of pages12
    JournalInternational journal of computer mathematics
    Volume10
    Issue number1
    DOIs
    Publication statusPublished - 1981

    Keywords

    • HMI-SLT: Speech and Language Technology
    • MSC-68Q45
    • MSC-68Q42
    • Inside-out macro grammar
    • Complexity of membership problem
    • (Many-one) log-space reducibility
    • Nondeterministic log-space bounded auxiliary pushdown automaton

    Fingerprint Dive into the research topics of 'Time and Space Complexity of Inside-Out Macro Languages'. Together they form a unique fingerprint.

    Cite this