Universität Stuttgart

Now showing 1 - 6 of 6

Open Access
Fragments of first-order logic over infinite words
(2009) Diekert, Volker; Kufleitner, Manfred
We give topological and algebraic characterizations as well as language theoretic descriptions of the following subclasses of first-order logic for omega-languages: Sigma2, FO2, the intersection of FO2 and Sigma2, and Delta2 (and by duality Pi2 and the intersection of FO2 and Pi2). These descriptions extend the respective results for finite words. In particular, we relate the above fragments to language classes of certain (unambiguous) polynomials. An immediate consequence is the decidability of the membership problem of these classes, but this was shown before by Wilke and Bojanczyk and is therefore not our main focus. The paper is about the interplay of algebraic, topological, and language theoretic properties.
Open 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.
Open Access
A proof of the factorization forest theorem
(2007) Kufleitner, Manfred
We show that for every homomorphism $\Gamma^+ \to S$ where $S$ is a finite semigroup there exists a factorization forest of height $\leq 3 \abs{S}$. The proof is based on Green's relations.
Open 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.
Open 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.
Open Access
On smoothed analysis of quicksort and hoare's find
(2009) Fouz, Mahmoud; Kufleitner, Manfred; Manthey, Bodo; Zeini Jahromi, Nima
We provide a smoothed analysis of Hoare's find algorithm and we revisit the smoothed analysis of quicksort. Hoare's find algorithm - often called quickselect - is an easy-to-implement algorithm for finding the k-th smallest element of a sequence. While the worst-case number of comparisons that Hoare's find needs is quadratic, the average-case number is linear. We analyze what happens between these two extremes by providing a smoothed analysis of the algorithm in terms of two different perturbation models: additive noise and partial permutations. In the first model, an adversary specifies a sequence of n numbers in the interval [0,1], and then each number is perturbed by adding a random number drawn from the interval [0,d]. In this setting, we give a tight bound for the number of comparisons in expectation of Hoare's find algorithm if the adversary may also specify the element that we would like to find. Furthermore, we consider the number of comparisons for finding the median. Again, we give tight bounds for the number of comparison in expectation. In the second model, each element is marked with probability p and then a random permutation is applied to the marked elements. We also provide a tight bound for the expected number of comparisons for this second model. Finally, we provide lower bounds for the smoothed number of comparisons of quicksort and Hoare's find for the median-of-three pivot rule, which usually yields faster algorithms than always selecting the first element: The pivot is the median of the first, middle, and last element of the sequence. We show that median-of-three does not yield a significant improvement over the classic rule: the lower bounds for the classic rule carry over to median-of-three.

Universität Stuttgart

Browse

Filters

Settings

Sort By

Results per page

Search Results