Technical Report TR-2006-03

BibliographyKufleitner, Manfred: Polynomials, Fragments of Temporal Logic and the Variety DA over Traces.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Technical Report Computer Science No. 2006/03.
17 pages, english.
CR-SchemaF.4.1 (Mathematical Logic)
F.4.3 (Formal Languages)
KeywordsMazurkiewicz traces; trace languages; polynomial closure; temporal logic
Abstract

We show that some language theoretic and logical characterizations of recognizable word languages whose syntactic monoid is in the variety DA also hold over traces. To this aim we give algebraic characterizations for the language operations of generating the polynomial closure and generating the unambiguous polynomial closure over traces.

We also show that there exist natural fragments of local temporal logic that describe this class of languages corresponding to DA. All characterizations are known to hold for words.

Full text and
other links
PDF (176591 Bytes)
PostScript (362575 Bytes)
Contactkufleitner@fmi.uni-stuttgart.de
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Entry dateFebruary 7, 2006
   Publ. Computer Science