|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc010202,
author = {Henning Bordihn and Henning Fernau},
title = {Accepting Grammars and Systems via Context Condition Grammars},
journal = jalc,
year = 1996,
volume = 1,
number = 2,
pages = {97--112},
keywords = {formal languages, regulated and parallel rewriting,
accepting and generating rewriting systems},
abstract = {We investigate several kinds of regulated
rewriting (matrix, ordered, programmed,
and variants thereof) and of parallel rewriting mechanisms
(Lindenmayer systems, uniformly limited Lindenmayer systems,
limited Lindenmayer systems and scattered context grammars)
as accepting devices, in contrast with the usual generating
mode.\par
In a lot of cases, accepting mode turns out to be exactly
as powerful as generating mode. These equivalences can be
proved using a theorem on so-called context condition
grammars. Interestingly, accepting devices are (strictly)
more powerful than their generating counterparts in case of
non-erasing ordered, programmed, and matrix grammars with
appearance checking (even programmed grammars with
unconditional transfer), and 1lEPT0L systems,
where we arrive at new characterizations of the
context-sensitive languages. If we admit erasing productions,
we get new characterizations of the recursively enumerable
languages.\par
Moreover, we supplement some hierarchies presented in
literature.}
}