TY - BOOK

T1 - Controlled Iteration Grammars and Full Hyper-AFL's (revised and extended version).

AU - Asveld, P.R.J.

N1 - Research partly supported by Netherlands Organization for the Advancement of Pure Research (ZWO).

PY - 1976

Y1 - 1976

N2 - We investigate derivation-controlled $K$-iteration grammars, called $(\Gamma,K)$-iteration grammars, where $\Gamma$ stands for a family of control languages. The control consists of a language in the family $\Gamma$ over the indices ("names") of the substitutions, prescribing the specific order in which one has to apply the substitutions. We show that under certain restrictions on the families $\Gamma$ and $K$ (which we tried to keep as simple as possible) the following holds.
(1) Regular control does not increase the generating power of $K$-iteration grammars. (2) For each $(\Gamma,K)$-iteration grammar there exists an equivalent propagating $(\Gamma,K)$-iteration grammer. (3) The family of $(\Gamma,K)$-iteration languages is a full hyper-AFL. (4) For each arbitrary $(\Gamma,K)$-iteration grammar there exists an equivalent $(\Gamma,K)$-iteration grammar with exactly two substitutions.
Finally, we discusssome consequences and additional properties of (uncontrolled) $K$-iteration grammars and controlled (deterministic) ETOL systems and their languages.

AB - We investigate derivation-controlled $K$-iteration grammars, called $(\Gamma,K)$-iteration grammars, where $\Gamma$ stands for a family of control languages. The control consists of a language in the family $\Gamma$ over the indices ("names") of the substitutions, prescribing the specific order in which one has to apply the substitutions. We show that under certain restrictions on the families $\Gamma$ and $K$ (which we tried to keep as simple as possible) the following holds.
(1) Regular control does not increase the generating power of $K$-iteration grammars. (2) For each $(\Gamma,K)$-iteration grammar there exists an equivalent propagating $(\Gamma,K)$-iteration grammer. (3) The family of $(\Gamma,K)$-iteration languages is a full hyper-AFL. (4) For each arbitrary $(\Gamma,K)$-iteration grammar there exists an equivalent $(\Gamma,K)$-iteration grammar with exactly two substitutions.
Finally, we discusssome consequences and additional properties of (uncontrolled) $K$-iteration grammars and controlled (deterministic) ETOL systems and their languages.

KW - EWI-3675

KW - HMI-SLT: Speech and Language Technology

M3 - Report

BT - Controlled Iteration Grammars and Full Hyper-AFL's (revised and extended version).

PB - University of Twente

CY - Enschede

ER -