Two optimal parallel algorithms on the commutation class of a word

作     者：Schott, R Spehner, JC 

作者机构：Univ Haute Alsace Fac Sci & Tech Lab MAGE F-68093 Mulhouse France Univ Nancy 1 LORIA F-54506 Vandoeuvre Les Nancy France Univ Nancy 1 IECN F-54506 Vandoeuvre Les Nancy France 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2004年第324卷第1期

页      面：107-131页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：automaton commutation class optimal parallel algorithm partially commutative monoid 

摘      要：The free partially commutative monoid M(A, 0) defined by a set of commutation relations 0 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. The main results presented in this paper are the following: A characterization of the minimal automaton A(Theta)(w) for C-Theta(w) with the help of the new notion of Theta-dissection. A parallel algorithm which computes the minimal automaton A(Theta)(w). This algorithm is optimal if the size of A is constant. An optimal parallel algorithm for testing if a word belongs to the commutation class C-Theta(w). Our approach differs completely from the methods (based on Foata s normal form) used by Cerin and Petit (Application de la theorie des traces A l implantation et A la mesure d algorithmes de distribution, These Universite Paris 11, Centre d Orsay, 1993 Proc. 6th Internal. Parallel Processing Symp. (IPPS), IEEE Press, New York, 1992, pp. 374-379;Proc. MFCS 93, Lecture Notes in Computer Science, Vol. 711, Springer, Berlin, 1993, pp. 332-341) for solving similar problems. Under some assumptions the first algorithm achieves an optimal speedup. The second algorithm achieves also an optimal speedup and 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 is in O(n) and does not depend on the size of the alphabet A as for the classical sequential algorithm. (C) 2004 Elsevier B.V. All rights reserved.