|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc010304,
author = {Gheorghe P\u{a}un and Grzegorz Rozenberg and Arto Salomaa},
title = {Pattern Grammars},
journal = jalc,
year = 1996,
volume = 1,
number = 3,
pages = {219--235},
keywords = {pattern, pattern grammar, Chomsky hierarchy,
closure properties, pure grammars},
abstract = {We consider rewriting systems based on production rules of
the form $u \rightarrow v$, where $u$ and $v$ are patterns.
Using such a rule means to find in the string to be
rewritten a substring $x$ which matches with the pattern $u$
and to replace it with a string obtained by
``interpreting'' $v$ according to the restrictions
imposed by the matching of $u$ with $x$. Free, maximal, and
minimal use of left-hand patterns are considered. The
generative capacity of the obtained grammars is
investigated. A series of directions for further research
are also mentioned.}
}