The dot-depth hierarchy versus iterated block products of DA

DSpace Repository


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
Show full item record


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)