Wyniki wyszukiwania - BazTech

1

The Krohn-Rhodes Theorem and Local Divisors

Diekert V., Kufleitner M., Steinberg B.

Fundamenta Informaticae

|

2012

|

Vol. 116, nr 1-4

65-77

EN

We give a new proof of the Krohn-Rhodes theorem using local divisors. The proof provides nearly as good a decomposition in terms of size as the holonomy decomposition of Eilenberg, avoids induction on the size of the state set, and works exclusively with monoids with the base case of the induction being that of a group.

2

On First-Order Fragments for Mazurkiewicz Traces

Diekert V., Horsch M., Kufleitner M.

Fundamenta Informaticae

|

2007

|

Vol. 80, nr 1-3

1-29

EN

Mazurkiewicz traces form a model for concurrency. Temporal logic and first-order logic are important tools in order to deal with the abstract behavior of such systems. Since typical properties can be described by rather simple logical formulas one is interested in logical fragments. One focus of this paper is unary temporal logic and first-order logic in two variables. Over words, this corresponds to the variety of finite monoids called DA. However, over Mazurkiewicz traces it is crucial whether traces are given as dependence graphs or as partial orders (over words these notions coincide). The main technical contribution is a generalization of important characterizations of DA from words to dependence graphs, whereas the use of partial orders leads to strictly larger classes. As a consequence we can decide whether a first-order formula over dependence graphs is equivalent to a first-order formula in two variables. The corresponding result for partial orders is not known. This difference between dependence graphs and partial orders also affects the complexity of the satisfiability problems for the fragments under consideration: for first-order formulas in two variables we prove an NEXPTIME upper bound, whereas the corresponding problem for partial orders leads to EXPSPACE. Furthermore, we give several separation results for the alternation hierarchy for first-order logic. It turns out that even for those levels at which one can express the partial order relation in terms of dependence graphs, the fragments over partial orders have more expressive power.

3

Characterization of the expressive power of silent transitions in timed automata

Berard B., Petit A., Diekert V., Gastin P.

Fundamenta Informaticae

|

1998

|

Vol. 36, nr 2,3

145-182

EN

Timed automata are among the most widely studied models for real-time systems. Silent transitions, i.e., e-transitions, have already been proposed in the original paper on timed automata by Alur and Dill. We show that class TLe of timed languages recognized by automata with e-transitions, is more robust and more expressive than the corresponding class TL without e-transitions. We then focus on e-transitions without reset, i.e. e-transitions which do not reset clocks. We propose an algorithm to construct, given a timed automaton, an equivalent one without such transitions. This algorithm is in two steps, it first suppresses the cycles of e-transitions without reset and then the remaining ones. Then, we prove that a timed automaton such that no e-transition which resets clocks lies on any directed cycle, can be effectively transformed into a timed automaton without e-transitions. Interestingly, this main result holds under the assumption of non-Zenoness and it is false otherwise. To complete the picture, we exhibit a simple timed automaton with an e-transition, which resets some clock, on a cycle and which is not equivalent to any e-free timed automaton. To show this, we develop a promising new technique based on the notion of precise action.