Two optimal parallel algorithms on the commutation class of a word

Abstract : The free partially commutative monoid $M(A,\Theta)$ defined by a set of commutation relations $\Theta$ on an alphabet $A$ can be viewed as a model for concurrent computing: indeed, the independence or the simultaneity of two actions can be interpreted by the commutation of two letters that encode them. In this context, the commutation class $C_{\Theta}(w)$ of a word $w$ of the free monoid $A^{*}$ plays a crucial role. In this paper we present an optimal parallel algorithm which computes the minimal automaton of the commutation class of a given word and an optimal parallel algorithm for testing if a word belongs to this commutation class. The prominent original new features of our approach are the notions of $\Theta$-dissection of a word, reference word and the use of an automaton whose construction is based on maps. It differs completely from the methods (based on Foata's normal form) used by C. Cérin and A. Petit \cite{CEa, CEb, CP} for solving similar problems. The second algorithm has a time complexity in $O(log(n))$ if the number of processors is in $O(n)$ where $n$ is the length of the word $w$. The total number of operations of our parallel algorithm is in $O(n)$ and does not depend on the size of the alphabet $A$ as for the classical sequential algorithm. \end{abstract}
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2004, 324 (1), pp.107-131
Liste complète des métadonnées

https://hal.inria.fr/inria-00099996
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:13:14
Dernière modification le : mardi 17 avril 2018 - 11:48:04

Identifiants

  • HAL Id : inria-00099996, version 1

Citation

René Schott, Jean-Claude Spehner. Two optimal parallel algorithms on the commutation class of a word. Theoretical Computer Science, Elsevier, 2004, 324 (1), pp.107-131. 〈inria-00099996〉

Partager

Métriques

Consultations de la notice

105