Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

Abstract grammars based on transductions

Share/Save/Bookmark

Asveld, Peter R.J. (1991) Abstract grammars based on transductions. Theoretical Computer Science, 81 (2). pp. 269-288. ISSN 0304-3975

[img]
Preview
PDF
1768Kb
Abstract: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 ${\cal T}$ of transductions, we establish elementary, decidability, and complexity properties of the corresponding family ${\cal L}({\cal T})$ of languages generated by $\cal T$-grammars. These results are special instances of slightly more general properties of so-called $\Gamma$-controlled $\cal T$-grammars, since regular control does not increase the generating power of $\cal T$-grammars. In a $\Gamma$-controlled $\cal T$-grammar we restrict the iteration of $\cal T$-transductions to those sequences of transductions that belong to a given control language, taken from a family $\Gamma$ of control languages.
Item Type:Article
Copyright:© 1991 Elsevier Science
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Link to this item:http://purl.utwente.nl/publications/66708
Official URL:http://dx.doi.org/10.1016/0304-3975(91)90195-8
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page