TY - BOOK
T1 - Abstract Grammars Based on Transductions (Revised version)
AU - Asveld, P.R.J.
PY - 1989
Y1 - 1989
N2 - We study an abstract grammatical model in which the effect (or application) of a production - determined by a so-called transduction - plays the main part rather than the notion of production itself. Under appropriately chosen assumptions on the underlying family $T$ of transductions, we establish elementary, decidability, and complexity properties of the corresponding family $L(T)$ of languages generated by $T$-grammars. These results are special instances of slightly more general properties of so-called $\Gamma$-controlled $T$-grammars, since regular control does not increase the generating power of $T$-grammars (In a $\Gamma$-controlled $T$-grammar we restrict the iteration of $T$-transductions to those sequences of transductions that belong to a given control language, taken from a family $\Gamma$ of control languages).
AB - We study an abstract grammatical model in which the effect (or application) of a production - determined by a so-called transduction - plays the main part rather than the notion of production itself. Under appropriately chosen assumptions on the underlying family $T$ of transductions, we establish elementary, decidability, and complexity properties of the corresponding family $L(T)$ of languages generated by $T$-grammars. These results are special instances of slightly more general properties of so-called $\Gamma$-controlled $T$-grammars, since regular control does not increase the generating power of $T$-grammars (In a $\Gamma$-controlled $T$-grammar we restrict the iteration of $T$-transductions to those sequences of transductions that belong to a given control language, taken from a family $\Gamma$ of control languages).
KW - HMI-SLT: Speech and Language Technology
M3 - Report
T3 - Memoranda Informatica
BT - Abstract Grammars Based on Transductions (Revised version)
PB - University of Twente, Department of Computer Science
CY - Enschede
ER -