Pattern Control on Derivations in Context-Free Rewriting
| Autor: | Bottoni, Paolo, Labella, Anna, Mussio, Piero, Păun, Gheorghe |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 1998 |
| DOI: | 10.25596/jalc-1998-003 |
| Popis: | Starting from a grammatical approach to the task of producing variations of given music themes, where the patterns of the obtained themes are prescribed in advance, we define grammars with the derivation controlled by patterns. Usual context-free grammars and pure context-free grammars are considered, with various types of control: with patterns associated to each rule or only checking the last word in a derivation, with one pattern in each case or with several patterns which have to be simultaneously observed, etc. Mainly the generative power of the obtained grammars is examined. Some open problems naturally occurring in this framework are mentioned. (An intriguing one concerns the question whether or not the hierarchy of languages obtained as simultaneous interpretations of n patterns is infinite; we have only found that two patterns are stronger than one.) Journal of Automata, Languages and Combinatorics, Volume 3, Number 1, 1998, 3-28 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|