Author name cluster

V. Diekert

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

I&C Journal 1995 Journal Article

Rational and Recognizable Complex Trace Languages

V. Diekert
P. Gastin
A. Petit

Mazurkiewicz defined traces as an algebraic model of finite concurrent processes. In order to model non-terminating processes a good notion of infinite traces was needed, which finally led to the notion of complex traces. For complex traces an associative concatenation and an ω-iteration are defined. This paper defines and investigates rational and recognizable complex trace languages. We prove various closure results such as the closure under boolean operations (for recognizable languages), concatenation, and left and right quotients by recognizable sets. Then we study sufficient conditions ensuring the recognizability of the finite and infinite iterations of complex trace languages. We introduce a generalization of the notion of concurrent iteration which leads to the main result of the paper: the generalization of Kleene′s and Ochmański′s theorems to complex trace languages.

Details DOI

I&C Journal 1994 Journal Article

On Confluent Semi-commutations: Decidability and Complexity Results

V. Diekert
E. Ochmanski
K. Reinhardt

The subject of this paper is the confluence of finite semi-commutation systems. Confluence of such systems is proved to be decidable property. Existence of a finite complete presentation of a trace monoid using rules only from another given trace monoid is proved to be reducible to the existence of a confluent semi-commutation system. Complexity results related to the preceding problems are proved: deciding the existence of finite complete presentations is Σ P 2-complete, whereas deciding confluence of semi-commutation systems is Co-NP-complete. Additionally, an open problem about trace synchronizations is solved: The local checking property is Co-NP-complete.

Details DOI