The dot-depth hierarchy versus iterated block products of DA

DSpace Repository

The dot-depth hierarchy versus iterated block products of DA

Borchert, Bernd
Dateien:
Thumbnail
131. KB
PDF
URI: http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-14397
http://hdl.handle.net/10900/48667
Dokumentart: Report
Date: 2004
Source: WSI ; 2004 ; 9
Language: English
Faculty: 7 Mathematisch-Naturwissenschaftliche Fakultät
Department: Sonstige - Informations- und Kognitionswissenschaften
DDC Classifikation: 004 - Data processing and computer science
Keywords: Reguläre Sprache , Dot-Depth-Hierarchie
License: http://tobias-lib.uni-tuebingen.de/doku/lic_ubt-nopod.php?la=de http://tobias-lib.uni-tuebingen.de/doku/lic_ubt-nopod.php?la=en
Show full item record

Abstract:

Like the sequence of the classes of the dot-depth hierarchy the sequence of classes given by the n-fold iterated block product of DA has the class of starfree regular languages as its limit. It is shown that this DA-block-product hierarchy grows more slowly than the dot-depth hierarchy: in fact already Sigma-2 of the dot-depth hierarchy contains properness witnesses for all levels of the DA-block-product hierarchy.

This item appears in the following Collection(s)