EVA STAR Trefferanzeige

Volltext Volltext.pdf1.pdf (178 KB)
URN (f├╝r Zitat) http://nbn-resolving.org/urn:nbn:de:swb:90-AAA398943
Titel Observations on grammar and language families.
Autor Fernau, Henning
Institution Fakult├Ąt f├╝r Informatik (INFORMATIK)
Informatik f├╝r Ingenieure und Naturwissenschaftler (Inf. f├╝r Ing. u. Naturwiss.)
Dokumenttyp Buch
Jahr 1994
Erscheinungsvermerk Karlsruhe 1994. (Interner Bericht. Fakult├Ąt f├╝r Informatik, Universit├Ąt Karlsruhe. 1994,22.)
In this report, we emphasize the differences of grammar families
and their properties versus language families and their
properties. To this end, we investigate grammar families from an
abstract standpoint, developping a new framework of reasoning. In
particular when considering decidability questions, special care
must be taken when trying to use decidability results (which are,
in the first place, properties of grammar families) in order to
establish results (e.g. hierarchy results) on language families.

We illustrate this by inspecting some theorems and their proofs in
the field of regulated rewriting. In this way, we also correct the
formulation of an important theorem of Hinz and Dassow.

As an exercise, we show that there is no `effective' grammatical
characterization of the family of recursive languages. Moreover,
we show how to prove the strictness of the Chomsky hierarchy using
decidability properties only. Most of the material of this report
will be published in `fundamenta informaticae'.