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.)
Pattern Control on Derivation in Context-Free Rewriting / Bottoni, Paolo Gaspare; Labella, Anna; P., Mussio; G., Paun. - In: JOURNAL OF AUTOMATA, LANGUAGES AND COMBINATORICS. - ISSN 1430-189X. - STAMPA. - 3:1(1998), pp. 3-28.
Pattern Control on Derivation in Context-Free Rewriting
BOTTONI, Paolo Gaspare;LABELLA, Anna;
1998
Abstract
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.)I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.