Universität Stuttgart

Permanent URI for this communityhttps://elib.uni-stuttgart.de/handle/11682/1

Browse

Filters

20063

Settings

Subject: search.filters.subject.004Start date: 2006End date: 2006Institute: search.filters.UBSInstitut.Institut für Formale Methoden der InformatikAuthor: search.filters.author.Kufleitner, Manfred

Search Results

Now showing 1 - 3 of 3
  • Thumbnail Image
    ItemOpen Access
    The expressive power of simple logical fragments over traces
    (2006) Horsch, Martin; Kufleitner, Manfred
    We compare the expressive power of some first-order fragments and of two simple temporal logics over Mazurkiewicz traces. Over words, most of these fragments have the same expressive power whereas over traces we show that the ability of formulating concurrency increases the expressive power. We also show that over so-called dependence structures it is impossible to formulate concurrency with the first-order fragments under consideration. Although the first-order fragments $\Delta_n[<]$ and $FO^2[<]$ over partial orders both can express concurrency of two actions, we show that in general they are incomparable over traces. For $FO^2[<]$ we give a characterization in terms of temporal logic by allowing an operator for parallelism.
  • Thumbnail Image
    ItemOpen Access
    Logical fragments for Mazurkiewicz traces : expressive power and algebraic characterizations
    (2006) Kufleitner, Manfred; Diekert, Volker (Prof. Dr.)
    Mazurkiewicz trace are a model for concurrency. They can be seen as a generalization of words by introducing partial commutation between specific letters. Several logical and language-theoretic characterizations of the variety of monoids DA are known for words. We show which of them also hold for traces and which of them do not hold. An important tool for this task are Ehrenfeucht-Fraisse games. For several logical fragments, we introduce characterizations in terms of these games. They are used to separate logical fragments over traces that have the same expressive power over words. An essential property is, whether one can express concurrency within a fragment or not.
  • Thumbnail Image
    ItemOpen Access
    Polynomials, fragments of temporal logic and the variety DA over traces
    (2006) Kufleitner, Manfred
    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.