|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc030101,
author = {Paolo Bottoni and Anna Labella and Piero Mussio
and Gheorghe P\u{a}un},
title = {Pattern Control on Derivations in Context-Free Rewriting},
journal = jalc,
year = 1998,
volume = 3,
number = 1,
pages = {3--28},
keywords = {patterns, regulated rewriting, Chomsky hierarchy,
pure grammars},
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.)}
}