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.