Controlled Iteration Grammars and Hyper-AFL's

P.R.J. Asveld

    Research output: Book/ReportReportOther research output

    Abstract

    We study $K$-iteration grammars equiped with a control on the application sequence of the substitutions, called $(\Gamma,K)$-iteration grammars. In fact, the control is a language over the indices of the substitutions, prescribing the specific order in which one has to apply the different substitutions ($\Gamma$ is a family of control languages). We show the follwing results: (1) If the family $K$ contains all finite languages, then regular control does not increase the generating power of $K$-iteration grammars. (2) If the families $\Gamma$ and $K$ satisfy some rather simple conditions, then for each $(\Gamma,K)$-iteration grammar, we are able to construct an equivalent propagating $(\Gamma,K)$-iteration grammar. (3) The restrictions on the families $\Gamma$ and $K$ such that the family $(\Gamma,K){\rm ITER}$ of $\Gamma$-controlled $K$-iteration languages becomes a hyper-AFL. (4) The conditions on the families $\Gamma$ and $K$ such that the following holds: $(\Gamma,K){\rm ITER}^{(m)}=(\Gamma,K){\rm ITER}$ for each $m\geq2$. As a simple consequence we obtain: all Lindenmayer-AFL's $(K){\rm ITER}^{(2)}$, $(K){\rm ITER}^{(3)}$, ... , $(K){\rm ITER}^{(m)}$, ... , $(K){\rm ITER}$ are hyper-AFL and moreover they are all identically the same: $(K){\rm ITER}^{(m)}=(K){\rm ITER}$ for each $m\geq2$.
    Original languageUndefined
    Place of PublicationEnschede
    PublisherUniversity of Twente, Department of Applied Mathematics
    Number of pages30
    Publication statusPublished - 1975

    Keywords

    • EWI-3668
    • HMI-SLT: Speech and Language Technology

    Cite this

    Asveld, P. R. J. (1975). Controlled Iteration Grammars and Hyper-AFL's. Enschede: University of Twente, Department of Applied Mathematics.
    Asveld, P.R.J. / Controlled Iteration Grammars and Hyper-AFL's. Enschede : University of Twente, Department of Applied Mathematics, 1975. 30 p.
    @book{df7bf827ce3a4db8a4ef20fd3df3c651,
    title = "Controlled Iteration Grammars and Hyper-AFL's",
    abstract = "We study $K$-iteration grammars equiped with a control on the application sequence of the substitutions, called $(\Gamma,K)$-iteration grammars. In fact, the control is a language over the indices of the substitutions, prescribing the specific order in which one has to apply the different substitutions ($\Gamma$ is a family of control languages). We show the follwing results: (1) If the family $K$ contains all finite languages, then regular control does not increase the generating power of $K$-iteration grammars. (2) If the families $\Gamma$ and $K$ satisfy some rather simple conditions, then for each $(\Gamma,K)$-iteration grammar, we are able to construct an equivalent propagating $(\Gamma,K)$-iteration grammar. (3) The restrictions on the families $\Gamma$ and $K$ such that the family $(\Gamma,K){\rm ITER}$ of $\Gamma$-controlled $K$-iteration languages becomes a hyper-AFL. (4) The conditions on the families $\Gamma$ and $K$ such that the following holds: $(\Gamma,K){\rm ITER}^{(m)}=(\Gamma,K){\rm ITER}$ for each $m\geq2$. As a simple consequence we obtain: all Lindenmayer-AFL's $(K){\rm ITER}^{(2)}$, $(K){\rm ITER}^{(3)}$, ... , $(K){\rm ITER}^{(m)}$, ... , $(K){\rm ITER}$ are hyper-AFL and moreover they are all identically the same: $(K){\rm ITER}^{(m)}=(K){\rm ITER}$ for each $m\geq2$.",
    keywords = "EWI-3668, HMI-SLT: Speech and Language Technology",
    author = "P.R.J. Asveld",
    year = "1975",
    language = "Undefined",
    publisher = "University of Twente, Department of Applied Mathematics",

    }

    Asveld, PRJ 1975, Controlled Iteration Grammars and Hyper-AFL's. University of Twente, Department of Applied Mathematics, Enschede.

    Controlled Iteration Grammars and Hyper-AFL's. / Asveld, P.R.J.

    Enschede : University of Twente, Department of Applied Mathematics, 1975. 30 p.

    Research output: Book/ReportReportOther research output

    TY - BOOK

    T1 - Controlled Iteration Grammars and Hyper-AFL's

    AU - Asveld, P.R.J.

    PY - 1975

    Y1 - 1975

    N2 - We study $K$-iteration grammars equiped with a control on the application sequence of the substitutions, called $(\Gamma,K)$-iteration grammars. In fact, the control is a language over the indices of the substitutions, prescribing the specific order in which one has to apply the different substitutions ($\Gamma$ is a family of control languages). We show the follwing results: (1) If the family $K$ contains all finite languages, then regular control does not increase the generating power of $K$-iteration grammars. (2) If the families $\Gamma$ and $K$ satisfy some rather simple conditions, then for each $(\Gamma,K)$-iteration grammar, we are able to construct an equivalent propagating $(\Gamma,K)$-iteration grammar. (3) The restrictions on the families $\Gamma$ and $K$ such that the family $(\Gamma,K){\rm ITER}$ of $\Gamma$-controlled $K$-iteration languages becomes a hyper-AFL. (4) The conditions on the families $\Gamma$ and $K$ such that the following holds: $(\Gamma,K){\rm ITER}^{(m)}=(\Gamma,K){\rm ITER}$ for each $m\geq2$. As a simple consequence we obtain: all Lindenmayer-AFL's $(K){\rm ITER}^{(2)}$, $(K){\rm ITER}^{(3)}$, ... , $(K){\rm ITER}^{(m)}$, ... , $(K){\rm ITER}$ are hyper-AFL and moreover they are all identically the same: $(K){\rm ITER}^{(m)}=(K){\rm ITER}$ for each $m\geq2$.

    AB - We study $K$-iteration grammars equiped with a control on the application sequence of the substitutions, called $(\Gamma,K)$-iteration grammars. In fact, the control is a language over the indices of the substitutions, prescribing the specific order in which one has to apply the different substitutions ($\Gamma$ is a family of control languages). We show the follwing results: (1) If the family $K$ contains all finite languages, then regular control does not increase the generating power of $K$-iteration grammars. (2) If the families $\Gamma$ and $K$ satisfy some rather simple conditions, then for each $(\Gamma,K)$-iteration grammar, we are able to construct an equivalent propagating $(\Gamma,K)$-iteration grammar. (3) The restrictions on the families $\Gamma$ and $K$ such that the family $(\Gamma,K){\rm ITER}$ of $\Gamma$-controlled $K$-iteration languages becomes a hyper-AFL. (4) The conditions on the families $\Gamma$ and $K$ such that the following holds: $(\Gamma,K){\rm ITER}^{(m)}=(\Gamma,K){\rm ITER}$ for each $m\geq2$. As a simple consequence we obtain: all Lindenmayer-AFL's $(K){\rm ITER}^{(2)}$, $(K){\rm ITER}^{(3)}$, ... , $(K){\rm ITER}^{(m)}$, ... , $(K){\rm ITER}$ are hyper-AFL and moreover they are all identically the same: $(K){\rm ITER}^{(m)}=(K){\rm ITER}$ for each $m\geq2$.

    KW - EWI-3668

    KW - HMI-SLT: Speech and Language Technology

    M3 - Report

    BT - Controlled Iteration Grammars and Hyper-AFL's

    PB - University of Twente, Department of Applied Mathematics

    CY - Enschede

    ER -

    Asveld PRJ. Controlled Iteration Grammars and Hyper-AFL's. Enschede: University of Twente, Department of Applied Mathematics, 1975. 30 p.