### Abstract

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | University of Twente, Department of Applied Mathematics |

Number of pages | 30 |

Publication status | Published - 1975 |

### Keywords

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

### Cite this

*Controlled Iteration Grammars and Hyper-AFL's*. Enschede: University of Twente, Department of Applied Mathematics.

}

*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.

Research output: Book/Report › Report › Other 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 -