Two optimal parallel algorithms on the commutation class of a word
Identifieur interne :
000626 ( PascalFrancis/Corpus );
précédent :
000625;
suivant :
000627
Two optimal parallel algorithms on the commutation class of a word
Auteurs : René Schott ;
Jean-Claude SpehnerSource :
-
Theoretical computer science [ 0304-3975 ] ; 2004.
RBID : Pascal:04-0519357
Descripteurs français
- Pascal (Inist)
- Algorithme optimal,
Algorithme parallèle,
Monoïde libre,
Relation commutation,
Calcul automatique,
Simultanéité,
Lettre alphabet,
Forme normale,
Automate,
Traitement parallèle,
Complexité temps,
Longueur mot,
Méthode séquentielle,
Informatique théorique,
Automate minimal,
Algorithme séquentiel.
English descriptors
- KwdEn :
- Automaton,
Commutation relation,
Computer theory,
Computing,
Free monoid,
Letter,
Normal form,
Optimal algorithm,
Parallel algorithm,
Parallel processing,
Sequential method,
Simultaneity,
Time complexity,
Word length.
Abstract
The free partially commutative monoid M(A, Θ) defined by a set of commutation relations Θ 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Θ(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Θ(w) for CΘ(w) with the help of the new notion of Θ-dissection. - A parallel algorithm which computes the minimal automaton AΘ(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Θ (w). Our approach differs completely from the methods (based on Foata's normal form) used by Cérin and Petit (Application de la théorie des traces à l'implantation et à la mesure d'algorithmes de distribution, Thèse Université Paris 11, Centre d'Orsay, 1993; Proc. 6th Intemat. 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.
Notice en format standard (ISO 2709)
Pour connaître la documentation sur le format Inist Standard.
| pA |
| A01 | 01 | 1 | | @0 0304-3975 |
|---|
| A02 | 01 | | | @0 TCSCDI |
|---|
| A03 | | 1 | | @0 Theor. comput. sci. |
|---|
| A05 | | | | @2 324 |
|---|
| A06 | | | | @2 1 |
|---|
| A08 | 01 | 1 | ENG | @1 Two optimal parallel algorithms on the commutation class of a word |
|---|
| A09 | 01 | 1 | ENG | @1 Words, languages and combinatorics: 3rd International Colloquium, Kyoto, Japan, March 14-18, 2000 (selected and revised papers) |
|---|
| A11 | 01 | 1 | | @1 SCHOTT (René) |
|---|
| A11 | 02 | 1 | | @1 SPEHNER (Jean-Claude) |
|---|
| A12 | 01 | 1 | | @1 ITO (Masami) @9 ed. |
|---|
| A14 | 01 | | | @1 LORIA and IECN, Universiré Henri Poincaré @2 54506 Vandoeuvre-lès-Nancy @3 FRA @Z 1 aut. |
|---|
| A14 | 02 | | | @1 Laboratoire MAGE, Faculté des Sciences et Techniques, Université de Haute Alsace @2 68093, Mulhouse @3 FRA @Z 2 aut. |
|---|
| A15 | 01 | | | @1 Faculty of Science, Kyoto Sangyo University, Kamigamo-Motoyama, Kita-ku @2 Kyoto 603 @3 JPN @Z 1 aut. |
|---|
| A20 | | | | @1 107-131 |
|---|
| A21 | | | | @1 2004 |
|---|
| A23 | 01 | | | @0 ENG |
|---|
| A43 | 01 | | | @1 INIST @2 17243 @5 354000120225890060 |
|---|
| A44 | | | | @0 0000 @1 © 2004 INIST-CNRS. All rights reserved. |
|---|
| A45 | | | | @0 13 ref. |
|---|
| A47 | 01 | 1 | | @0 04-0519357 |
|---|
| A60 | | | | @1 P @2 C |
|---|
| A61 | | | | @0 A |
|---|
| A64 | 01 | 1 | | @0 Theoretical computer science |
|---|
| A66 | 01 | | | @0 NLD |
|---|
| C01 | 01 | | ENG | @0 The free partially commutative monoid M(A, Θ) defined by a set of commutation relations Θ 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Θ(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Θ(w) for CΘ(w) with the help of the new notion of Θ-dissection. - A parallel algorithm which computes the minimal automaton AΘ(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Θ (w). Our approach differs completely from the methods (based on Foata's normal form) used by Cérin and Petit (Application de la théorie des traces à l'implantation et à la mesure d'algorithmes de distribution, Thèse Université Paris 11, Centre d'Orsay, 1993; Proc. 6th Intemat. 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. |
|---|
| C02 | 01 | X | | @0 001D02A05 |
|---|
| C02 | 02 | X | | @0 001D02A03 |
|---|
| C03 | 01 | X | FRE | @0 Algorithme optimal @5 17 |
|---|
| C03 | 01 | X | ENG | @0 Optimal algorithm @5 17 |
|---|
| C03 | 01 | X | SPA | @0 Algoritmo óptimo @5 17 |
|---|
| C03 | 02 | X | FRE | @0 Algorithme parallèle @5 18 |
|---|
| C03 | 02 | X | ENG | @0 Parallel algorithm @5 18 |
|---|
| C03 | 02 | X | SPA | @0 Algoritmo paralelo @5 18 |
|---|
| C03 | 03 | X | FRE | @0 Monoïde libre @5 20 |
|---|
| C03 | 03 | X | ENG | @0 Free monoid @5 20 |
|---|
| C03 | 03 | X | SPA | @0 Monoide libre @5 20 |
|---|
| C03 | 04 | X | FRE | @0 Relation commutation @5 21 |
|---|
| C03 | 04 | X | ENG | @0 Commutation relation @5 21 |
|---|
| C03 | 04 | X | SPA | @0 Relación conmutación @5 21 |
|---|
| C03 | 05 | X | FRE | @0 Calcul automatique @5 24 |
|---|
| C03 | 05 | X | ENG | @0 Computing @5 24 |
|---|
| C03 | 05 | X | SPA | @0 Cálculo automático @5 24 |
|---|
| C03 | 06 | X | FRE | @0 Simultanéité @5 26 |
|---|
| C03 | 06 | X | ENG | @0 Simultaneity @5 26 |
|---|
| C03 | 06 | X | SPA | @0 Simultaneidad @5 26 |
|---|
| C03 | 07 | X | FRE | @0 Lettre alphabet @5 27 |
|---|
| C03 | 07 | X | ENG | @0 Letter @5 27 |
|---|
| C03 | 07 | X | SPA | @0 Letra alfabeto @5 27 |
|---|
| C03 | 08 | X | FRE | @0 Forme normale @5 29 |
|---|
| C03 | 08 | X | ENG | @0 Normal form @5 29 |
|---|
| C03 | 08 | X | SPA | @0 Forma normal @5 29 |
|---|
| C03 | 09 | X | FRE | @0 Automate @5 35 |
|---|
| C03 | 09 | X | ENG | @0 Automaton @5 35 |
|---|
| C03 | 09 | X | SPA | @0 Autómata @5 35 |
|---|
| C03 | 10 | X | FRE | @0 Traitement parallèle @5 36 |
|---|
| C03 | 10 | X | ENG | @0 Parallel processing @5 36 |
|---|
| C03 | 10 | X | SPA | @0 Tratamiento paralelo @5 36 |
|---|
| C03 | 11 | X | FRE | @0 Complexité temps @5 41 |
|---|
| C03 | 11 | X | ENG | @0 Time complexity @5 41 |
|---|
| C03 | 11 | X | SPA | @0 Complejidad tiempo @5 41 |
|---|
| C03 | 12 | X | FRE | @0 Longueur mot @5 43 |
|---|
| C03 | 12 | X | ENG | @0 Word length @5 43 |
|---|
| C03 | 12 | X | SPA | @0 Longitud palabra @5 43 |
|---|
| C03 | 13 | X | FRE | @0 Méthode séquentielle @5 44 |
|---|
| C03 | 13 | X | ENG | @0 Sequential method @5 44 |
|---|
| C03 | 13 | X | SPA | @0 Método secuencial @5 44 |
|---|
| C03 | 14 | X | FRE | @0 Informatique théorique @5 45 |
|---|
| C03 | 14 | X | ENG | @0 Computer theory @5 45 |
|---|
| C03 | 14 | X | SPA | @0 Informática teórica @5 45 |
|---|
| C03 | 15 | X | FRE | @0 Automate minimal @4 INC @5 70 |
|---|
| C03 | 16 | X | FRE | @0 Algorithme séquentiel @4 INC @5 71 |
|---|
| N21 | | | | @1 292 |
|---|
| N44 | 01 | | | @1 OTO |
|---|
| N82 | | | | @1 OTO |
|---|
|
|---|
| pR |
| A30 | 01 | 1 | ENG | @1 International Colloquium on Words, Languages and Combinaritics @2 3 @3 Kyoto JPN @4 2000-03-14 |
|---|
|
|---|
Format Inist (serveur)
| NO : | PASCAL 04-0519357 INIST |
|---|
| ET : | Two optimal parallel algorithms on the commutation class of a word |
|---|
| AU : | SCHOTT (René); SPEHNER (Jean-Claude); ITO (Masami) |
|---|
| AF : | LORIA and IECN, Universiré Henri Poincaré/54506 Vandoeuvre-lès-Nancy/France (1 aut.); Laboratoire MAGE, Faculté des Sciences et Techniques, Université de Haute Alsace/68093, Mulhouse/France (2 aut.); Faculty of Science, Kyoto Sangyo University, Kamigamo-Motoyama, Kita-ku/Kyoto 603/Japon (1 aut.) |
|---|
| DT : | Publication en série; Congrès; Niveau analytique |
|---|
| SO : | Theoretical computer science; ISSN 0304-3975; Coden TCSCDI; Pays-Bas; Da. 2004; Vol. 324; No. 1; Pp. 107-131; Bibl. 13 ref. |
|---|
| LA : | Anglais |
|---|
| EA : | The free partially commutative monoid M(A, Θ) defined by a set of commutation relations Θ 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Θ(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Θ(w) for CΘ(w) with the help of the new notion of Θ-dissection. - A parallel algorithm which computes the minimal automaton AΘ(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Θ (w). Our approach differs completely from the methods (based on Foata's normal form) used by Cérin and Petit (Application de la théorie des traces à l'implantation et à la mesure d'algorithmes de distribution, Thèse Université Paris 11, Centre d'Orsay, 1993; Proc. 6th Intemat. 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. |
|---|
| CC : | 001D02A05; 001D02A03 |
|---|
| FD : | Algorithme optimal; Algorithme parallèle; Monoïde libre; Relation commutation; Calcul automatique; Simultanéité; Lettre alphabet; Forme normale; Automate; Traitement parallèle; Complexité temps; Longueur mot; Méthode séquentielle; Informatique théorique; Automate minimal; Algorithme séquentiel |
|---|
| ED : | Optimal algorithm; Parallel algorithm; Free monoid; Commutation relation; Computing; Simultaneity; Letter; Normal form; Automaton; Parallel processing; Time complexity; Word length; Sequential method; Computer theory |
|---|
| SD : | Algoritmo óptimo; Algoritmo paralelo; Monoide libre; Relación conmutación; Cálculo automático; Simultaneidad; Letra alfabeto; Forma normal; Autómata; Tratamiento paralelo; Complejidad tiempo; Longitud palabra; Método secuencial; Informática teórica |
|---|
| LO : | INIST-17243.354000120225890060 |
|---|
| ID : | 04-0519357 |
|---|
Links to Exploration step
Pascal:04-0519357
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Two optimal parallel algorithms on the commutation class of a word</title>
<author><name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name>
<affiliation><inist:fA14 i1="01"><s1>LORIA and IECN, Universiré Henri Poincaré</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14><author><name sortKey="Spehner, Jean Claude" sort="Spehner, Jean Claude" uniqKey="Spehner J" first="Jean-Claude" last="Spehner">Jean-Claude Spehner</name>
<affiliation><inist:fA14 i1="02"><s1>Laboratoire MAGE, Faculté des Sciences et Techniques, Université de Haute Alsace</s1>
<s2>68093, Mulhouse</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14><publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">04-0519357</idno>
<date when="2004">2004</date>
<idno type="stanalyst">PASCAL 04-0519357 INIST</idno>
<idno type="RBID">Pascal:04-0519357</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000626</idno>
</publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Two optimal parallel algorithms on the commutation class of a word</title>
<author><name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name>
<affiliation><inist:fA14 i1="01"><s1>LORIA and IECN, Universiré Henri Poincaré</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14><author><name sortKey="Spehner, Jean Claude" sort="Spehner, Jean Claude" uniqKey="Spehner J" first="Jean-Claude" last="Spehner">Jean-Claude Spehner</name>
<affiliation><inist:fA14 i1="02"><s1>Laboratoire MAGE, Faculté des Sciences et Techniques, Université de Haute Alsace</s1>
<s2>68093, Mulhouse</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14><series><title level="j" type="main">Theoretical computer science</title>
<title level="j" type="abbreviated">Theor. comput. sci.</title>
<idno type="ISSN">0304-3975</idno>
<imprint><date when="2004">2004</date>
</imprint><seriesStmt><title level="j" type="main">Theoretical computer science</title>
<title level="j" type="abbreviated">Theor. comput. sci.</title>
<idno type="ISSN">0304-3975</idno>
</seriesStmt><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Automaton</term>
<term>Commutation relation</term>
<term>Computer theory</term>
<term>Computing</term>
<term>Free monoid</term>
<term>Letter</term>
<term>Normal form</term>
<term>Optimal algorithm</term>
<term>Parallel algorithm</term>
<term>Parallel processing</term>
<term>Sequential method</term>
<term>Simultaneity</term>
<term>Time complexity</term>
<term>Word length</term>
</keywords><keywords scheme="Pascal" xml:lang="fr"><term>Algorithme optimal</term>
<term>Algorithme parallèle</term>
<term>Monoïde libre</term>
<term>Relation commutation</term>
<term>Calcul automatique</term>
<term>Simultanéité</term>
<term>Lettre alphabet</term>
<term>Forme normale</term>
<term>Automate</term>
<term>Traitement parallèle</term>
<term>Complexité temps</term>
<term>Longueur mot</term>
<term>Méthode séquentielle</term>
<term>Informatique théorique</term>
<term>Automate minimal</term>
<term>Algorithme séquentiel</term>
</keywords><front><div type="abstract" xml:lang="en">The free partially commutative monoid M(A, Θ) defined by a set of commutation relations Θ 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<sub>Θ</sub>
(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<sub>Θ</sub>
(w) for C<sub>Θ</sub>
(w) with the help of the new notion of Θ-dissection. - A parallel algorithm which computes the minimal automaton A<sub>Θ</sub>
(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<sub>Θ </sub>
(w). Our approach differs completely from the methods (based on Foata's normal form) used by Cérin and Petit (Application de la théorie des traces à l'implantation et à la mesure d'algorithmes de distribution, Thèse Université Paris 11, Centre d'Orsay, 1993; Proc. 6th Intemat. 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.</div><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0304-3975</s0>
</fA01><fA02 i1="01"><s0>TCSCDI</s0>
</fA02><fA03 i2="1"><s0>Theor. comput. sci.</s0>
</fA03><fA05><s2>324</s2>
</fA05><fA08 i1="01" i2="1" l="ENG"><s1>Two optimal parallel algorithms on the commutation class of a word</s1>
</fA08><fA09 i1="01" i2="1" l="ENG"><s1>Words, languages and combinatorics: 3rd International Colloquium, Kyoto, Japan, March 14-18, 2000 (selected and revised papers)</s1>
</fA09><fA11 i1="01" i2="1"><s1>SCHOTT (René)</s1>
</fA11><fA11 i1="02" i2="1"><s1>SPEHNER (Jean-Claude)</s1>
</fA11><fA12 i1="01" i2="1"><s1>ITO (Masami)</s1>
<s9>ed.</s9>
</fA12><fA14 i1="01"><s1>LORIA and IECN, Universiré Henri Poincaré</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</fA14><fA14 i1="02"><s1>Laboratoire MAGE, Faculté des Sciences et Techniques, Université de Haute Alsace</s1>
<s2>68093, Mulhouse</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</fA14><fA15 i1="01"><s1>Faculty of Science, Kyoto Sangyo University, Kamigamo-Motoyama, Kita-ku</s1>
<s2>Kyoto 603</s2>
<s3>JPN</s3>
<sZ>1 aut.</sZ>
</fA15><fA20><s1>107-131</s1>
</fA20><fA21><s1>2004</s1>
</fA21><fA23 i1="01"><s0>ENG</s0>
</fA23><fA43 i1="01"><s1>INIST</s1>
<s2>17243</s2>
<s5>354000120225890060</s5>
</fA43><fA44><s0>0000</s0>
<s1>© 2004 INIST-CNRS. All rights reserved.</s1>
</fA44><fA45><s0>13 ref.</s0>
</fA45><fA47 i1="01" i2="1"><s0>04-0519357</s0>
</fA47><fA60><s1>P</s1>
<s2>C</s2>
</fA60><fA64 i1="01" i2="1"><s0>Theoretical computer science</s0>
</fA64><fA66 i1="01"><s0>NLD</s0>
</fA66><fC01 i1="01" l="ENG"><s0>The free partially commutative monoid M(A, Θ) defined by a set of commutation relations Θ 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<sub>Θ</sub>
(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<sub>Θ</sub>
(w) for C<sub>Θ</sub>
(w) with the help of the new notion of Θ-dissection. - A parallel algorithm which computes the minimal automaton A<sub>Θ</sub>
(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<sub>Θ </sub>
(w). Our approach differs completely from the methods (based on Foata's normal form) used by Cérin and Petit (Application de la théorie des traces à l'implantation et à la mesure d'algorithmes de distribution, Thèse Université Paris 11, Centre d'Orsay, 1993; Proc. 6th Intemat. 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.</s0><fC02 i1="01" i2="X"><s0>001D02A05</s0>
</fC02><fC02 i1="02" i2="X"><s0>001D02A03</s0>
</fC02><fC03 i1="01" i2="X" l="FRE"><s0>Algorithme optimal</s0>
<s5>17</s5>
</fC03><fC03 i1="01" i2="X" l="ENG"><s0>Optimal algorithm</s0>
<s5>17</s5>
</fC03><fC03 i1="01" i2="X" l="SPA"><s0>Algoritmo óptimo</s0>
<s5>17</s5>
</fC03><fC03 i1="02" i2="X" l="FRE"><s0>Algorithme parallèle</s0>
<s5>18</s5>
</fC03><fC03 i1="02" i2="X" l="ENG"><s0>Parallel algorithm</s0>
<s5>18</s5>
</fC03><fC03 i1="02" i2="X" l="SPA"><s0>Algoritmo paralelo</s0>
<s5>18</s5>
</fC03><fC03 i1="03" i2="X" l="FRE"><s0>Monoïde libre</s0>
<s5>20</s5>
</fC03><fC03 i1="03" i2="X" l="ENG"><s0>Free monoid</s0>
<s5>20</s5>
</fC03><fC03 i1="03" i2="X" l="SPA"><s0>Monoide libre</s0>
<s5>20</s5>
</fC03><fC03 i1="04" i2="X" l="FRE"><s0>Relation commutation</s0>
<s5>21</s5>
</fC03><fC03 i1="04" i2="X" l="ENG"><s0>Commutation relation</s0>
<s5>21</s5>
</fC03><fC03 i1="04" i2="X" l="SPA"><s0>Relación conmutación</s0>
<s5>21</s5>
</fC03><fC03 i1="05" i2="X" l="FRE"><s0>Calcul automatique</s0>
<s5>24</s5>
</fC03><fC03 i1="05" i2="X" l="ENG"><s0>Computing</s0>
<s5>24</s5>
</fC03><fC03 i1="05" i2="X" l="SPA"><s0>Cálculo automático</s0>
<s5>24</s5>
</fC03><fC03 i1="06" i2="X" l="FRE"><s0>Simultanéité</s0>
<s5>26</s5>
</fC03><fC03 i1="06" i2="X" l="ENG"><s0>Simultaneity</s0>
<s5>26</s5>
</fC03><fC03 i1="06" i2="X" l="SPA"><s0>Simultaneidad</s0>
<s5>26</s5>
</fC03><fC03 i1="07" i2="X" l="FRE"><s0>Lettre alphabet</s0>
<s5>27</s5>
</fC03><fC03 i1="07" i2="X" l="ENG"><s0>Letter</s0>
<s5>27</s5>
</fC03><fC03 i1="07" i2="X" l="SPA"><s0>Letra alfabeto</s0>
<s5>27</s5>
</fC03><fC03 i1="08" i2="X" l="FRE"><s0>Forme normale</s0>
<s5>29</s5>
</fC03><fC03 i1="08" i2="X" l="ENG"><s0>Normal form</s0>
<s5>29</s5>
</fC03><fC03 i1="08" i2="X" l="SPA"><s0>Forma normal</s0>
<s5>29</s5>
</fC03><fC03 i1="09" i2="X" l="FRE"><s0>Automate</s0>
<s5>35</s5>
</fC03><fC03 i1="09" i2="X" l="ENG"><s0>Automaton</s0>
<s5>35</s5>
</fC03><fC03 i1="09" i2="X" l="SPA"><s0>Autómata</s0>
<s5>35</s5>
</fC03><fC03 i1="10" i2="X" l="FRE"><s0>Traitement parallèle</s0>
<s5>36</s5>
</fC03><fC03 i1="10" i2="X" l="ENG"><s0>Parallel processing</s0>
<s5>36</s5>
</fC03><fC03 i1="10" i2="X" l="SPA"><s0>Tratamiento paralelo</s0>
<s5>36</s5>
</fC03><fC03 i1="11" i2="X" l="FRE"><s0>Complexité temps</s0>
<s5>41</s5>
</fC03><fC03 i1="11" i2="X" l="ENG"><s0>Time complexity</s0>
<s5>41</s5>
</fC03><fC03 i1="11" i2="X" l="SPA"><s0>Complejidad tiempo</s0>
<s5>41</s5>
</fC03><fC03 i1="12" i2="X" l="FRE"><s0>Longueur mot</s0>
<s5>43</s5>
</fC03><fC03 i1="12" i2="X" l="ENG"><s0>Word length</s0>
<s5>43</s5>
</fC03><fC03 i1="12" i2="X" l="SPA"><s0>Longitud palabra</s0>
<s5>43</s5>
</fC03><fC03 i1="13" i2="X" l="FRE"><s0>Méthode séquentielle</s0>
<s5>44</s5>
</fC03><fC03 i1="13" i2="X" l="ENG"><s0>Sequential method</s0>
<s5>44</s5>
</fC03><fC03 i1="13" i2="X" l="SPA"><s0>Método secuencial</s0>
<s5>44</s5>
</fC03><fC03 i1="14" i2="X" l="FRE"><s0>Informatique théorique</s0>
<s5>45</s5>
</fC03><fC03 i1="14" i2="X" l="ENG"><s0>Computer theory</s0>
<s5>45</s5>
</fC03><fC03 i1="14" i2="X" l="SPA"><s0>Informática teórica</s0>
<s5>45</s5>
</fC03><fC03 i1="15" i2="X" l="FRE"><s0>Automate minimal</s0>
<s4>INC</s4>
<s5>70</s5>
</fC03><fC03 i1="16" i2="X" l="FRE"><s0>Algorithme séquentiel</s0>
<s4>INC</s4>
<s5>71</s5>
</fC03><fN21><s1>292</s1>
</fN21><fN44 i1="01"><s1>OTO</s1>
</fN44><fN82><s1>OTO</s1>
</fN82><pR><fA30 i1="01" i2="1" l="ENG"><s1>International Colloquium on Words, Languages and Combinaritics</s1>
<s2>3</s2>
<s3>Kyoto JPN</s3>
<s4>2000-03-14</s4>
</fA30><server><NO>PASCAL 04-0519357 INIST</NO>
<ET>Two optimal parallel algorithms on the commutation class of a word</ET>
<AU>SCHOTT (René); SPEHNER (Jean-Claude); ITO (Masami)</AU>
<AF>LORIA and IECN, Universiré Henri Poincaré/54506 Vandoeuvre-lès-Nancy/France (1 aut.); Laboratoire MAGE, Faculté des Sciences et Techniques, Université de Haute Alsace/68093, Mulhouse/France (2 aut.); Faculty of Science, Kyoto Sangyo University, Kamigamo-Motoyama, Kita-ku/Kyoto 603/Japon (1 aut.)</AF>
<DT>Publication en série; Congrès; Niveau analytique</DT>
<SO>Theoretical computer science; ISSN 0304-3975; Coden TCSCDI; Pays-Bas; Da. 2004; Vol. 324; No. 1; Pp. 107-131; Bibl. 13 ref.</SO>
<LA>Anglais</LA>
<EA>The free partially commutative monoid M(A, Θ) defined by a set of commutation relations Θ 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<sub>Θ</sub>
(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<sub>Θ</sub>
(w) for C<sub>Θ</sub>
(w) with the help of the new notion of Θ-dissection. - A parallel algorithm which computes the minimal automaton A<sub>Θ</sub>
(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<sub>Θ </sub>
(w). Our approach differs completely from the methods (based on Foata's normal form) used by Cérin and Petit (Application de la théorie des traces à l'implantation et à la mesure d'algorithmes de distribution, Thèse Université Paris 11, Centre d'Orsay, 1993; Proc. 6th Intemat. 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.</EA><CC>001D02A05; 001D02A03</CC>
<FD>Algorithme optimal; Algorithme parallèle; Monoïde libre; Relation commutation; Calcul automatique; Simultanéité; Lettre alphabet; Forme normale; Automate; Traitement parallèle; Complexité temps; Longueur mot; Méthode séquentielle; Informatique théorique; Automate minimal; Algorithme séquentiel</FD>
<ED>Optimal algorithm; Parallel algorithm; Free monoid; Commutation relation; Computing; Simultaneity; Letter; Normal form; Automaton; Parallel processing; Time complexity; Word length; Sequential method; Computer theory</ED>
<SD>Algoritmo óptimo; Algoritmo paralelo; Monoide libre; Relación conmutación; Cálculo automático; Simultaneidad; Letra alfabeto; Forma normal; Autómata; Tratamiento paralelo; Complejidad tiempo; Longitud palabra; Método secuencial; Informática teórica</SD>
<LO>INIST-17243.354000120225890060</LO>
<ID>04-0519357</ID>
</server>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000626 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000626 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Corpus
|type= RBID
|clé= Pascal:04-0519357
|texte= Two optimal parallel algorithms on the commutation class of a word
}}
| This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022 |  |
