The atnext/atprevious hierarchy on the starfree languages

DSpace Repository


Dateien:
Aufrufstatistik

URI: http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-14838
http://hdl.handle.net/10900/48686
Dokumentart: Report (Bericht)
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
License: xmlui.dri2xhtml.METS-1.0.item-dc-rights_value_ubt-nopod
Show full item record

Abstract:

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)