The atnext/atprevious hierarchy on the starfree languages

DSpace Repository


Dokumentart: Report
Date: 2004
Source: WSI ; 2004 ; 11
Language: English
Faculty: 7 Mathematisch-Naturwissenschaftliche Fakultät
Department: Sonstige - Informations- und Kognitionswissenschaften
DDC Classifikation: 004 - Data processing and computer science
Keywords: Temporale Logik , Dot-Depth-Hierarchie
Show full item record


The temporal logic operators atnext and atprevious are alternatives for the operators until and since. P atnext Q has the meaning: at the next position in the future where Q holds it holds P. We define an asymmetric but natural notion of depth for the expressions of this linear temporal logic. The sequence of classes at_n of languages expressible via such depth-n expressions gives a parametrization of the starfree regular languages which we call the atnext/atprevious hierarchy, or simply at hierarchy. It turns out that the at hierarchy equals the hierarchy given by the n-fold weakly iterated block product of DA. It is shown that the at hierarchy is situated properly between the until/since and the dot-depth hierarchy.

This item appears in the following Collection(s)