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 (Bericht)
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: xmlui.dri2xhtml.METS-1.0.item-dc-rights_value_ubt-nopod
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)