KIT | KIT-Bibliothek | Impressum
Open Access Logo
URN: urn:nbn:de:swb:90-AAA3305946

Accepting grammars and systems

Bordihn, Henning; Fernau, Henning


We investigate several kinds of regulated rewriting (programmed,
matrix, with regular control, ordered, 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.

In some cases, accepting mode turns out to be just as powerful as
generating mode, e.g. within the grammars of the Chomsky
hierarchy, within random context, regular control, L systems,
uniformly limited L systems, scattered context. Most of these
equivalences can be proved using a metatheorem on so-called
context condition grammars. In case of matrix grammars and
programmed grammars without appearance checking, a straightforward
construction leads to the desired equivalence result.
Interestingly, accepting devices are (strictly) more powerful than
their generating counterparts in case of ordered grammars,
programmed and matrix grammars with appearance checking (even
programmed grammarsm with unconditional transfer), and 1lET0L
systems. More precisely, if we admit erasing productions, we ... mehr

Zugehörige Institution(en) am KIT Informatik für Ingenieure und Naturwissenschaftler (Inf. für Ing. u. Naturwiss.)
Publikationstyp Buch
Jahr 1994
Sprache Englisch
Identifikator KITopen ID: 330594
Erscheinungsvermerk Karlsruhe 1994. (Interner Bericht. Fakultät für Informatik, Universität Karlsruhe. 1994,9.)
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page