Volker Diekert
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Volker Diekert has a total of 10 co-authors. Here are the top co-authors by number of shared publications:
- Paul Gastin
Université Paris 7
2 shared publications - Antoine Petit
LSV, CNRS UMR 8643 & ENS de Cachan, 61, Av. du Président Wilson, 94235 Cachan Cedex, France
1 shared publication Béatrice
1 shared publicationBérard
1 shared publication- Christian Hagenah
Inst. für Informatik Universität Stuttgart Breitwiesenstr. 20-22 D-70565 Stuttgart
1 shared publication - Claudio Gutierrez
University of Chile, Santiago, Chile
1 shared publication
Latest Publications
- 24 October 2007
- Published by Springer Nature in Theory of Computing Systems
- Vol. 43 (2) , 99
Foreword
- 1 January 2004
- Published by Springer Nature in Theory of Computing Systems
- Vol. 37 (1) , 133-156
Existential and Positive Theories of Equations in Graph Products
- 1 January 2004
- Published by Springer Nature in Theory of Computing Systems
- Vol. 37 (1) , 133-156
Existential and Positive Theories of Equations in Graph Products
- 14 February 2002
- Published by Springer Nature
- p. 26-38
Safety and Liveness Properties for Real Traces and a Direct Translation from LTL to Monoids
- 14 February 2002
- Published by Springer Nature
- p. 26-38
Safety and Liveness Properties for Real Traces and a Direct Translation from LTL to Monoids
- Open Access
The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete
It is known that the existential theory of equations in free groups is decidable. This is a famous result of Makanin. On the other hand it has been shown that the scheme of his algorithm is not primitive recursive. In this paper we present an algorithm that works in polynomial space, even in the more general setting where each variable has a rational constraint, that is, the solution has to respect a specification given by a regular word language. Our main result states that the existential theory of equations in free groups with rational constraints is PSPACE-complete. We obtain this result as a corollary of the corresponding statement about free monoids with involution.
Open AccessThe Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete
It is known that the existential theory of equations in free groups is decidable. This is a famous result of Makanin. On the other hand it has been shown that the scheme of his algorithm is not primitive recursive. In this paper we present an algorithm that works in polynomial space, even in the more general setting where each variable has a rational constraint, that is, the solution has to respect a specification given by a regular word language. Our main result states that the existential theory of equations in free groups with rational constraints is PSPACE-complete. We obtain this result as a corollary of the corresponding statement about free monoids with involution.
- 1 July 1998
- Published by Springer Nature in Acta Informatica
- Vol. 35 (7) , 567-593
Approximating traces
- 1 July 1998
- Published by Springer Nature in Acta Informatica
- Vol. 35 (7) , 567-593
Approximating traces
- 1 January 1998
- Published by SAGE Publications in Fundamenta Informaticae
- Vol. 36 (2-3) , 145-182
Characterization of the Expressive Power of Silent Transitions in Timed Automata
Timed automata are among the most widely studied models for real-time systems. Silent transitions, i.e., ϵ-transitions, have already been proposed in the original paper on timed automata by Alur and Dill [3]. We show that the class TLϵ of timed languages recognized by automata with ϵ-transitions, is more robust and more expressive than the corresponding class TL without ϵ-transitions. We then focus on ϵ-transitions without reset, i.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 ϵ-transitions without reset and then the remaining ones. Then, we prove that a timed automaton such that no ϵ-transition which resets clocks lies on any directed cycle, can be effectively transformed into a timed automaton without ϵ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 ϵ-transition, which resets some clock, on a cycle and which is not equivalent to any ϵ-free timed automaton. To show this, we develop a promising new technique based on the notion of precise action. This paper presents a synthesis of the two conference communications [9] and [13].
- 1 January 1998
- Published by SAGE Publications in Fundamenta Informaticae
- Vol. 36 (2-3) , 145-182
Characterization of the Expressive Power of Silent Transitions in Timed Automata
Timed automata are among the most widely studied models for real-time systems. Silent transitions, i.e., ϵ-transitions, have already been proposed in the original paper on timed automata by Alur and Dill [3]. We show that the class TLϵ of timed languages recognized by automata with ϵ-transitions, is more robust and more expressive than the corresponding class TL without ϵ-transitions. We then focus on ϵ-transitions without reset, i.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 ϵ-transitions without reset and then the remaining ones. Then, we prove that a timed automaton such that no ϵ-transition which resets clocks lies on any directed cycle, can be effectively transformed into a timed automaton without ϵ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 ϵ-transition, which resets some clock, on a cycle and which is not equivalent to any ϵ-free timed automaton. To show this, we develop a promising new technique based on the notion of precise action. This paper presents a synthesis of the two conference communications [9] and [13].
- 7 November 1994
- Published by Elsevier in Theoretical Computer Science
- Vol. 134 (1) , 87-105
A partial trace semantics for Petri nets
- 7 November 1994
- Published by Elsevier in Theoretical Computer Science
- Vol. 134 (1) , 87-105
A partial trace semantics for Petri nets