\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{KMLNR80}

\bibitem[Abe77]{abe77}
E.~Abe.
\newblock {\em Hopf algebras}.
\newblock Cambridge University Press, 1977.

{\sl{}}

\bibitem[AD79]{ak79}
A.V. Anisimov and Knuth D.E.
\newblock Inhomogeneous sorting.
\newblock {\em International Journal of Computer and Information Sciences},
  8:255--260, 1979.


\bibitem[AG91]{ag91}
C.~\`Alvarez and J.~Gabarr\'o.
\newblock The parallel complexity of two problems on concurrency.
\newblock {\em Information Processing Letters}, 38:61--70, 1991.

{\sl{}}

\bibitem[AH89]{ah89}
I.J. Aalbersberg and H.J. Hoogeboom.
\newblock Characterizations of the decidability of some problems for regular
  trace languages.
\newblock {\em Mathematical Systems Theory}, 22:1--19, 1989.

{\sl{}}

\bibitem[AR85]{ar85}
IJ.~J. Aalbersberg and G.~Rozenberg.
\newblock Traces, dependency graphs and {DNLC} grammars.
\newblock {\em Discrete Applied Mathematics}, 11:299--306, 1985.

{\sl{}Using dep-graphs a relationship between trace theory and the theory of
  graph grammars is established. In particular, it is demonstrated how regular
  dep-graph languages can be generated by regular DNLC grammars.}

\bibitem[AR86]{ar86}
J.~Aalbersberg and G.~Rozenberg.
\newblock Theory of traces.
\newblock Report 86-16, University of Leiden (The Netherlands), Vakgroep
  Informatica, 1986.

{\sl{}}

\bibitem[AR88]{ar88}
I.J. Aalbersberg and G.~Rozenberg.
\newblock Theory of traces.
\newblock {\em Theoretical Computer Science}, 60:1--82, 1988.

{\sl{}}

\bibitem[Arn85]{arn85}
A.~Arnold.
\newblock A syntactic congruence for rational $\omega$-languages.
\newblock {\em Theoretical Computer Science}, 39:333--335, 1985.

{\sl{}The syntactic congruence of a rational language $L$ of infinite words is
  defined. It is proved that this congruence is the largest congruence which
  saturates $L$.}

\bibitem[Arn91]{arn91}
A.~Arnold.
\newblock An extension of the notions of traces and asynchronous automata.
\newblock {\em R.A.I.R.O. --- Informatique {T}h{\'e}orique et Applications},
  25:355--393, 1991.


\bibitem[AW86]{aw86}
I.J. Aalbersberg and E.~Welzl.
\newblock Trace languages defined by regular string languages.
\newblock {\em R.A.I.R.O. --- Informatique {T}h{\'e}orique et Applications},
  20:103--119, 1986.

{\sl{}}

\bibitem[BA82]{ben82}
M.~Ben-Ari.
\newblock {\em Principles of Concurrent Programming}.
\newblock Prentice-Hall International, Inc., Englewood Cliffs, 1982.

{\sl{}}

\bibitem[BBMS81]{bbms81}
A.~Bertoni, A.~Brambilla, G.~Mauri, and N.~Sabadini.
\newblock An application of the theory of free partially commutative monoids:
  asymptotic densities of trace languages.
\newblock In J.~Gruska et~al., editors, {\em Proceedings of the 10th Symposium
  on Mathematical Foundations of Computer Science (MFCS'81), Strbske' Pleso
  (CSFR) 1981}, number 118 in Lecture Notes in Computer Science, pages
  205--215, Berlin-Heidelberg-New York, 1981. Springer.

{\sl{}The paper frames trace languages in the theory of free partially
  commutative monoids. Using the Foata normal form, a canonical representation
  of traces can be computed in linear time. The generating function of the
  number of traces of given length is derived from the Moebius function.
  Finally, the class of recognizable trace languages is introduced and it is
  characterized the class of independence alphabets whose recognizable
  languages have rational asymptotic densities.}

\bibitem[BC86]{br86}
J.~Berstel and Reutenauer C.
\newblock {\em Rational series and their languages}.
\newblock Springer, 1986.

{\sl{}}

\bibitem[BD87]{bd87}
E.~Best and R.~Devillers.
\newblock Sequential and concurrent behaviour in {P}etri net theory.
\newblock {\em Theoretical Computer Science}, 55:87--136, 1987.

{\sl{}This paper aims at obtaining formal results about the relationship
  between various classes of processes and occurrence sequences in net theory.
  From trace point of view, this paper presents also an equivalence relation on
  infinite words which turns out to define exactly real traces.}

\bibitem[BDG88]{bdg88}
J.~L. Balc\'azar, J.~D\'iaz, and Gabarr\'o.
\newblock {\em Structural Complexity {\rm {I}}}.
\newblock Number~11 in EATCS Monographs on Theoretical Computer Science.
  Springer, Berlin-Heidelberg-New York, 1988.

{\sl{}}

\bibitem[Bed87]{bed87}
M.~Bednarczyk.
\newblock {\em Categories of Asynchronous Transition Systems}.
\newblock PhD thesis, University of Sussex, 1987.
\newblock Available as Report 1/88, School of Cognitive and Computing Sciences,
  University of Sussex.

{\sl{}}

\bibitem[Ber66]{ber66}
A.J. Bernstein.
\newblock Analysis of programs for parallel processing.
\newblock {\em IEEE Trans. Comp.}, EC-15(5):757--762, 1966.


\bibitem[Ber79]{ber79}
J.~Berstel.
\newblock {\em Transductions and context-free languages}.
\newblock Teubner Studienb{\"u}cher, Stuttgart, 1979.

{\sl{}This book presents a theory of formal languages with main emphasis on
  rational and recognizable languages, rational transductions and families of
  context-free languages.}

\bibitem[BF87]{bf87}
E.~Best and C.~Fernandez.
\newblock Notations and terminology on {P}etri net theory.
\newblock Arbeitspapiere der {GMD} 195, Gesellschaft f{\"u}r Mathematik und
  Datenverarbeitung, Bonn, 1987.

{\sl{}}

\bibitem[BG89]{bg89}
A.~Bertoni and M.~Goldwurm.
\newblock On the prefixes of a random trace and the membership problem for
  context-free trace languages.
\newblock In L.~Huguet and A.~Poli, editors, {\em Applied Algebra, Algebraic
  Algorithms and Error- Correcting Codes (Proceedings AAECC 5), Menorca (Spain)
  June15-19, 1987}, number 356 in Lecture Notes in Computer Science, pages
  35--59, Berlin-Heidelberg-New York, 1989. Springer.

{\sl{}The paper presents some probabilistic estimations of the number of
  prefixes of a trace, under the assumption that all words of given length are
  equiprobable. In particular it evaluates all moments of such a random
  variable. These bounds are then applied to the average case analysis of an
  algorithm for membership problem of context-free trace languages.}

\bibitem[BGS88]{bgs88}
A.~Bertoni, M.~Goldwurm, and N.~Sabadini.
\newblock Analysis of a class of algorithms for problems on trace languages.
\newblock In Th. Beth and M.~Clausen, editors, {\em Applicable Algebra,
  Error-Correcting Codes, Combinatorics and Computer Algebra (Proceedings AAECC
  4), {Karls\-ruhe} (FRG) September 23-26,1986}, number 307 in Lecture Notes in
  Computer Science, pages 202--214, Berlin-Heidelberg-New York, 1988. Springer.

{\sl{}A class of algorithms for solving problems on f.p.c.m.'s is described
  using a general procedure scheme. Such a class includes algorithms for the
  membership problem of rational trace languages and for other problems. It is
  shown that the time complexity depends on the number of prefixes of the input
  trace. Such a quantity is then evaluated in the average case under two
  different probabilistic assumptions.}

\bibitem[BL81]{bl81}
A.M. Ballantyne and D.S. Lankford.
\newblock New decision algorithms for finitely presented commutative
  semigroups.
\newblock {\em Comput. and Maths. with Appls.}, 7:159--165, 1981.

{\sl{}}

\bibitem[BL87]{bl87}
R.~Book and H.-N. Liu.
\newblock Rewriting systems and word problems in a free partially commutative
  monoid.
\newblock {\em Information Processing Letters}, 26:29--32, 1987.

{\sl{}}

\bibitem[BMP90]{bmp90}
P.~Bonizzoni, G.~Mauri, and G.~Pighizzini.
\newblock About infinite traces.
\newblock In V.~Diekert, editor, {\em Proceedings of the {ASMICS} workshop
  {F}ree {P}artially {C}ommutative {M}onoids, {K}ochel am {S}ee, {O}ktober
  1989}, {R}eport {TUM-I9002}, {T}echnical {U}niversity of {M}unich, pages
  1--10, 1990.

{\sl{}This paper generalizes the notion of Foata normal form to real traces.
  Using this Foata normal form, the set of real traces is provided with a
  metric and is proved to be complete.}

\bibitem[BMPS91]{bmps91}
P.~Bonizzoni, G.~Mauri, G.~Pighizzini, and N.~Sabadini.
\newblock Recognizing sets of labelled acyclic graphs.
\newblock Technical report, Dip. Scienze dell'Informazione, Universit{\`a} di
  Milano, 1991.
\newblock To appear in Proceedings Workshop on Trees (Nivat, M. and Podelski A.
  ed's), Le Touquet (France), June 1990.

{\sl{}}

\bibitem[BMS82a]{bms82caap}
A.~Bertoni, G.~Mauri, and N.~Sabadini.
\newblock Context-free trace languages.
\newblock In {\em Proceedings 7th Coll. on Trees in Algebra and Programming
  (CAAP), Lille (France)}, pages 32--42, 1982.

{\sl{}}

\bibitem[BMS82b]{bms82icalp}
A.~Bertoni, G.~Mauri, and N.~Sabadini.
\newblock Equivalence and membership problems for regular trace languages.
\newblock In {\em Proc. 9th ICALP}, number 140 in Lecture Notes in Computer
  Science, pages 61--71, Berlin-Heidelberg-New York, 1982. Springer.

{\sl{}It is proved that the non uniform version of Membership problem for
  rational trace languages is solvable in polynomial time, while the uniform
  version is NP-complete. Furthermore, it is shown that the equivalence problem
  is undecidable in general, and decidable if the independence is transitive.}

\bibitem[BMS82c]{bms82can}
A.~Bertoni, G.~Mauri, and N.~Sabadini.
\newblock A hierarchy of regular trace languages and some combinatorial
  applications.
\newblock In A.~Ballester, D.~Cardus, and E.~Trillas, editors, {\em Proceedings
  2nd World Conf. on Mathematics at the service of man, Las Palmas (Canary
  Island) Spain}, pages 146--153. Universidad Politecnica de Las Palmas, 1982.

{\sl{}It is shown that for nonempty independence relation the class of
  recognizable languages is properly contained in the class of rational
  languages. Moreover, a hierarchy of subclasses of rational trace languages is
  introduced, showing that if the independence is not transitive the inclusions
  among classes are proper. Finally, some results on asymptotic densities of
  deterministic languages are presented using formal power series techniques.}

\bibitem[BMS83]{bms83}
A.~Bertoni, G.~Mauri, and N.~Sabadini.
\newblock Concurrency and commutativity.
\newblock Technical report, Istituto di Cibernetica, Universit{\`a} di Milano,
  1983.
\newblock Presented at the Workshop on Petri nets, Varenna (Italy), 1982.

{\sl{}The class of recognizable languages is compared with the class of
  languages that describe the behaviours of labelled- C/E Petri nets. It shows
  that every language generated by a C/E net is recognizable, and the converse
  is established for acyclic dependence graphs.}

\bibitem[BMS85]{bms85}
A.~Bertoni, G.~Mauri, and N.~Sabadini.
\newblock Unambiguous regular trace languages.
\newblock In G.~Demetrovics, J.~Katona and A.~Salomaa, editors, {\em
  Proceedings Coll. on Algebra, Combinatorics and Logic in Computer Science},
  volume~42 of {\em Colloquia Mathematica Soc. J. Bolyai}, pages 113--123.
  North Holland, Amsterdam, 1985.

{\sl{}It is shown that for every independence alphabet the classes of
  deterministic and unambiguous trace languages coincide, and contain the class
  of recognizable languages. Furthermore, deterministic and rational languages
  coincide iff the independence is transitive, while deterministic and
  recognizable languages coincide iff the independence is empty.}

\bibitem[BMS89]{bms89}
A.~Bertoni, G.~Mauri, and N.~Sabadini.
\newblock {M}embership problems for regular and context free trace languages.
\newblock {\em Information and Computation}, 82:135--150, 1989.

{\sl{}Algorithms for the membership problems of rational and context-free trace
  languages are described and some polynomial bounds on their worst-case time
  complexities are given. The problems are shown to be NP-complete in the
  uniform case, that is whenever a grammar generating the language is part of
  the input.}

\bibitem[BNS91]{bns91}
L.~Bernardiniello, G.~Nifosi, and N.~Sabadini.
\newblock A comparison between asynchronous automata and superposed automata
  net systems.
\newblock Technical report, Dip. Scienze dell'Informazione, Universit{\`a} di
  Milano, May 1991.
\newblock Presented at the ASMICS general meeting held in Menaggio (Italy),
  February 1991.

{\sl{}}

\bibitem[Bou68]{bou68}
N.~Bourbaki.
\newblock {\em General Topology}.
\newblock Addison Wesley, Reading, Mass., 1968.

{\sl{}}

\bibitem[Bou72]{bou72}
N.~Bourbaki.
\newblock {\em Alg\`ebres et groupes de Lie}, volume 2, 3.
\newblock CCLS, 1972.

{\sl{}Chapter 2 is a good presentation of free Lie algebras.}

\bibitem[BPPR79]{bppr79}
J.~Berstel, D.~Perrin, J.F. Perrot, and A.~Restivo.
\newblock Sur le th\'eor\`eme du d\'efaut.
\newblock {\em Journal of Algebra}, 60:179--189, 1979.

{\sl{}}

\bibitem[BPS88]{bps88}
D.~Bruschi, G.~Pighizzini, and N.~Sabadini.
\newblock On the existence of the minimum asynchronous automaton and on
  decision problems for unambiguous regular trace languages.
\newblock In R.~Cori and M.~Wirsing, editors, {\em Proceedings 5th STACS},
  number 294 in Lecture Notes in Computer Science, pages 334--346,
  Berlin-Heidelberg-New York, 1988. Springer.
\newblock To appear in {\it Information and Computation}.

{\sl{}The paper presents a characterization of the independence alphabets for
  which every recognizable language admits a unique minimum asynchronous
  automaton. The equivalence problem for unambiguous languages is considered,
  showing that for a suitable nontransitive independence relation the problem
  can be decided in polynomial time.}

\bibitem[Bra76]{bra76}
W.~Brauer.
\newblock $\omega$-automata and their languages.
\newblock In A.~Mazurkiewicz, editor, {\em Proceedings of the 5th Symposium on
  Mathematical Foundations of Computer Science (MFCS'76), Gdansk (Poland)
  1976}, number~45 in Lecture Notes in Computer Science, pages 12--22,
  Berlin-Heidelberg-New York, 1976. Springer.

{\sl{}}

\bibitem[BS88]{bs88}
A.~Bertoni and N.~Sabadini.
\newblock Generating functions of trace languages.
\newblock {\em Bulletin of the European Association for Theoretical Computer
  Science (EATCS)}, 35:106--112, June 1988.

{\sl{}It is proved that the generating functions of rational trace languages
  are rational if and only if the independence relation is transitive.
  Furthermore, it is given a characterization of the nontransitive independence
  alphabets $(\Sigma,I)$ for which every trace language in $R_2(\Sigma,I)$
  admits an algebraic generating function.}

\bibitem[BS92]{bms92}
P.~Bertoni, A.~Massazza and N.~Sabadini.
\newblock Holonomic generating functions and context-free languages.
\newblock {\em International Journal of Foundations of Computer Science},
  3(2):181--191, 1992.

{\sl{}}

\bibitem[CES86]{ces86}
E.M. Clarke, E.A. Emerson, and A.P. Sistla.
\newblock Automatic verification of finite state concurrent systems using
  temporal logic specifications: A practical approach.
\newblock {\em ACM Transactions on Programming Languages and Systems},
  8(2):244--263, 1986.

{\sl{}Model checking of a CTL formula against a transition graph is introduced.
  An algorithm is presented that iteratively labels the nodes of the graph with
  progressively larger subformulas.}

\bibitem[CF69]{cf69}
P.~Cartier and D.~Foata.
\newblock {\em Probl\`emes combinatoires de commutation et r{\'e}arrangements}.
\newblock Number~85 in Lecture Notes in Mathematics. Springer,
  Berlin-Heidelberg-New York, 1969.

{\sl{}}

\bibitem[CFL58]{cfl58}
K.T. Chen, R.H. Fox, and R.C. Lyndon.
\newblock Free differential calculus, {IV}.
\newblock {\em Ann. of Maths.}, 68(1):81--95, 1958.

{\sl{}In this paper, Lyndon words are defined for the first time in connexion
  with basic commutators of the free group.}

\bibitem[CG91]{cg91}
M.~Clerbout and D.~Gonzalez.
\newblock Atomic semi commutations.
\newblock Technical Report {I}. {T}. 216, Laboratoire d' Informatique
  fondamentale de Lille, {UFR} d'{IEEA}, Batiment {M}3, F-59655 Villeneuve d'
  Ascq {CEDEX}, 1991.

{\sl{}}

\bibitem[CGL{\etalchar{+}}91]{cgl+91}
M.~Clerbout, D.~Gonzalez, M.~Latteux, E.~Ochma{\'n}ski, Y.~Roos, and P.A.
  Wacrenier.
\newblock Recognizable morphisms on semi commutations.
\newblock unpublished, 1991.

\bibitem[Cho86]{cho86}
C.~Choffrut.
\newblock Free partially commutative monoids.
\newblock Technical Report 86/20, {LITP}, Universit\'e Paris~7 (France), 1986.

{\sl{}}

\bibitem[CL84]{cl84}
M.~Clerbout and M.~Latteux.
\newblock Partial commutations and faithful rational transductions.
\newblock {\em Theoretical Computer Science}, 34:241--254, 1984.

{\sl{}}

\bibitem[CL87]{cl87}
M.~Clerbout and M.~Latteux.
\newblock Semi-{C}ommutations.
\newblock {\em Information and Computation}, 73:59--74, 1987.

{\sl{}}

\bibitem[Cle84]{cle84}
M.~Clerbout.
\newblock {\em Commutations partielles et familles de langages}.
\newblock Th{\'e}se, Universit{\'e} de Lille (France), 1984.

{\sl{}}

\bibitem[CLR90]{clr90}
M.~Clerbout, M.~Latteux, and Y.~Roos.
\newblock Decomposition of partial commutations.
\newblock In M.S. Paterson, editor, {\em Proceedings of the 17th International
  Colloquium on Automata Languages and Programming (ICALP'90), Warwick
  (England) 1990}, number 443 in Lecture Notes in Computer Science, pages
  501--511, Berlin-Heidelberg-New York, 1990. Springer.

{\sl{}}

\bibitem[CLRZ92]{clrz92}
M.~Clerbout, M.~Latteux, Y.~Roos, and W.~Zielonka.
\newblock Semi-commutations and rational expressions.
\newblock In Werner Kuich, editor, {\em Proceedings of the 19th International
  Colloquium on Automata Languages and Programming (ICALP'92), Vienna (Austria)
  1992}, volume 623 of {\em Lecture Notes in Computer Science}, pages 113--125,
  Berlin-Heidelberg-New York, 1992. Springer.

{\sl{}}

\bibitem[CM85]{cm85}
R.~Cori and Y.~M{\'e}tivier.
\newblock Recognizable subsets of some partially abelian monoids.
\newblock {\em Theoretical Computer Science}, 35:179--189, 1985.

{\sl{}The first part of the paper concerns the question of recognizability of
  the infinite iteration $X^*$ of a set $X$ of traces. is examined. In the
  second part the properties of commutators of traces are examined.}

\bibitem[CM87]{cm87}
R.~Cori and Y.~M{\'e}tivier.
\newblock Approximation d' une trace, automates asynchrones et ordre des
  evenement dans les systemes repartis.
\newblock Technical Report 1-8708, UER de Mathematiques et d' Informatique,
  Universit{\'e} de Bordeaux I, 1987.

{\sl{}}

\bibitem[CM88]{cm88}
R.~Cori and Y.~M{\'e}tivier.
\newblock Approximation of a trace, asynchronous automata and the ordering of
  events in a distributed system.
\newblock In {\em Proceedings of the 15th International Colloquium on Automata,
  Languages and Programming (ICALP'88)}, number 317 in LNCS, pages 147--161.
  Springer, 1988.


\bibitem[CMZ90]{cmz90}
R.~Cori, Y.~M{\'e}tivier, and W.~Zielonka.
\newblock Applications of trace approximation to asynchronous automata and
  message passing with bounded time-stamps in asynchronous networks.
\newblock Technical report, Univ. Bordeaux, 1990.

{\sl{}}

\bibitem[CMZ93]{cmz93}
R.~Cori, Y.~M{\'e}tivier, and W.~Zielonka.
\newblock {A}synchronous mappings and asynchronous cellular automata.
\newblock {\em Information and Computation}, 106:159--202, 1993.

{\sl{}A new improved construction of finite deterministic asynchronous automata
  is presented.}

\bibitem[Cou90]{cou90}
Bruno Courcelle.
\newblock Graph rewriting: and algebraic and logic approach.
\newblock In Jan van Leeuwen, editor, {\em Handbook of Theoretical Computer
  Science}, volume~B, pages 193--242. Elsevier, Amsterdam, 1990.

{\sl{}}

\bibitem[CP67]{cp67}
A.~Clifford and G.~Preston.
\newblock {\em The algebraic theory of semigroups}, volume 1,2.
\newblock American Mathematical Society, 1961,1967.

{\sl{}}

\bibitem[CP85]{cp85}
R.~Cori and D.~Perrin.
\newblock Automates et commutations partielles.
\newblock {\em R.A.I.R.O. --- Informatique {T}h{\'e}orique et Applications},
  19:21--32, 1985.

{\sl{}}

\bibitem[CR87]{cr87}
M.~Chrobak and W.~Rytter.
\newblock Unique decipherability for partially commutative alphabets.
\newblock {\em Fundamenta Informaticae}, X:323--336, 1987.

{\sl{}}

\bibitem[CR92]{cr92}
M.~Clerbout and Y.~Roos.
\newblock Semicommutations and algebraic languages.
\newblock {\em Theoretical Computer Science}, 103:39--49, 1992.
\newblock Short version in Proceedings of STACS'90.

{\sl{}}

\bibitem[CS63]{cs63}
N.~Chomsky and M.P. Sch{\"u}tzenberger.
\newblock The algebraic theory of context-free languages.
\newblock In {\em Comp. Prog. and Formal Systems}, pages 118--161, Amsterdam,
  1963. North-Holland.

{\sl{}}

\bibitem[CSLR88]{csl88}
R.~Cori, E.~Sopena, M.~Latteux, and Y.~Roos.
\newblock 2-asynchronous automata.
\newblock {\em Theoretical Computer Science}, 61:93--102, 1988.


\bibitem[Dau88]{dau88}
Max Dauchet.
\newblock Termination of rewriting is undecidable in the one-rule case.
\newblock In M.~Chytil et~al., editors, {\em Proceedings of the 13th Symposium
  on Mathematical Foundations of Computer Science (MFCS'88), Carlsbad (CSSR)
  1988}, number 324 in Lecture Notes in Computer Science, pages 262--288,
  Berlin-Heidelberg-New York, 1988. Springer.

{\sl{}}

\bibitem[DE92]{de92}
Volker Diekert and Werner Ebinger, editors.
\newblock {\em {\it {I}nfinite {T}races. {P}roceedings of a workshop of the
  {ESPRIT} {B}asic {R}esearch {A}ction {N}o 3166: {A}lgebraic and {S}yntactic
  {M}ethods in {C}omputer {S}cience {(ASMICS)}, {T}{\"u}bingen, Germany,
  1992}}, Bericht 4/92. Universit{\"a}t Stuttgart, Fakult{\"a}t Informatik,
  1992.

{\sl{}}

\bibitem[DGP91]{dgp91}
V.~Diekert, P.~Gastin, and A.~Petit.
\newblock Recognizable complex trace languages.
\newblock In A.~Tarlecki, editor, {\em Proceedings of the 16th Symposium on
  Mathematical Foundations of Computer Science (MFCS'91), Kazimierz Dolny
  (Poland) 1991}, number 520 in Lecture Notes in Computer Science, pages
  131--140, Berlin-Heidelberg-New York, 1991. Springer.


\bibitem[DGP92]{dgp92}
V.~Diekert, P.~Gastin, and A.~Petit.
\newblock Rational and recognizable complex trace languages.
\newblock Tech. {R}ep. {LITP} 92.39, Universit\'e Paris~6 (France), 1992.
\newblock To appear in Inform.\ and Comp.


\bibitem[Dic80]{dic80}
W.~Dicks.
\newblock An exact sequence for rings of polynomials in partly commuting
  indeterminates.
\newblock {\em Journ. of Pure and Applied Algebra}, 22:215--228, 1980.

{\sl{}}

\bibitem[Die87]{die87}
V.~Diekert.
\newblock On the {K}nuth-{B}endix completion for concurrent processes.
\newblock In Th. Ottmann, editor, {\em Proceedings of the 14th International
  Colloquium on Automata Languages and Programming (ICALP'87), Karlsruhe (FRG)
  1987}, number 267 in Lecture Notes in Computer Science, pages 42--53,
  Berlin-Heidelberg-New York, 1987. Springer.
\newblock Appeared also in a revised version in {\it Theoret. Comp. Science\/},
  66:117-136, 1989.

{\sl{}}

\bibitem[Die88]{die88}
V.~Diekert.
\newblock Transitive orientations, {M\"o}bius functions and complete
  semi-{T}hue systems for free partially commutative monoids.
\newblock In T.~Lepist{\"o} et~al., editors, {\em Proceedings of the 15th
  International Colloquium on Automata Languages and Programming (ICALP'88),
  Tampere (Finnland) 1988}, number 317 in Lecture Notes in Computer Science,
  pages 176--187, Berlin-Heidelberg-New York, 1988. Springer.

{\sl{}}

\bibitem[Die89]{die89}
V.~Diekert.
\newblock Word problems over traces which are solvable in linear time.
\newblock In B.~Monien et~al., editors, {\em Proceedings of the 6th Annual
  Symposium on Theoretical Aspects of Computer Science (STACS'89), Paderborn
  (FRG) 1989}, number 349 in Lecture Notes in Computer Science, pages 168--180,
  Berlin-Heidelberg-New York, 1989. Springer.
\newblock Revised and extended version in {\it Theoret. Comp. Science\/} 74
  (1990) 3-18.

{\sl{}}

\bibitem[Die90a]{die90stacs}
V.~Diekert.
\newblock Combinatorial rewriting on traces.
\newblock In C.~Choffrut et~al., editors, {\em Proceedings of the 7th Annual
  Symposium on Theoretical Aspects of Computer Science (STACS'90), Rouen
  (France) 1990}, number 415 in Lecture Notes in Computer Science, pages
  138--151, Berlin-Heidelberg-New York, 1990. Springer.

{\sl{}}

\bibitem[Die90b]{die90}
V.~Diekert.
\newblock {\em Combinatorics on Traces}.
\newblock Number 454 in Lecture Notes in Computer Science. Springer,
  Berlin-Heidelberg-New York, 1990.

{\sl{}}

\bibitem[Die90c]{die90bull}
V.~Diekert.
\newblock Research topics in the theory of free partially commutative monoids.
\newblock {\em Bulletin of the European Association for Theoretical Computer
  Science (EATCS)}, 40:479--491, Feb 1990.

{\sl{}}

\bibitem[{Die}90d]{die90asmics}
V.~{Diekert, editor}.
\newblock {\it {F}ree {P}artially {C}ommutative {M}onoids}. {P}roceedings of a
  workshop of the {ESPRIT} {B}asic {R}esearch {A}ction {N}o 3166: {A}lgebraic
  and {S}yntactic {M}ethods in {C}omputer {S}cience {(ASMICS)}, {K}ochel am
  {S}ee, {B}avaria, {FRG} (1989).
\newblock {R}eport {TUM-I}9002, Technical University Munich, 1990.

{\sl{}}

\bibitem[Die91]{die91}
V.~Diekert.
\newblock On the concatenation of infinite traces.
\newblock In Choffrut C. et~al., editors, {\em Proceedings of the 8th Annual
  Symposium on Theoretical Aspects of Computer Science (STACS'91), Hamburg
  1991}, number 480 in Lecture Notes in Computer Science, pages 105--117,
  Berlin-Heidelberg-New York, 1991. Springer.
\newblock Appeared also in Theoretical Computer Science\ref{die93concat}.

{\sl{}}

\bibitem[Die92]{die92ma}
V.~Diekert.
\newblock Mathematical aspects of trace theory.
\newblock {\em Mitt. Math. Ges. Hamburg}, 12:1171--1181, 1992.
\newblock Special issue of the tricentenary.

{\sl{}}

\bibitem[Die93a]{die93mfcs}
V.~Diekert.
\newblock Complex and complex-like traces.
\newblock In A.~Borzyszkowski et~al., editor, {\em Proc.\ of the 18th
  Mathematical Foundations of Computer Science (MFCS~93), Gdansk (Polen) 1993},
  number 711 in Lecture Notes in Computer Science, pages 68--82,
  Berlin-Heidelberg-New York, 1993. Springer.
\newblock Invited Lecture.

{\sl{}}

\bibitem[Die93b]{die93moebius}
V.~Diekert.
\newblock M{\"o}bius functions and confluent semi-commutations.
\newblock {\em Theoretical Computer Science}, 108:25--43, 1993.

{\sl{}}

\bibitem[Die93c]{die93concat}
V.~Diekert.
\newblock On the concatenation of infinite traces.
\newblock {\em Theoretical Computer Science}, 113:35--54, 1993.
\newblock Special issue STACS~91.

{\sl{}}

\bibitem[Die93d]{die93fct}
V.~Diekert.
\newblock Rewriting, semi-commutations, and m{\"o}bius functions.
\newblock In Z.~{\'E}sik, editor, {\em Proc.\ of the 9th Fundamentals of
  Computation Theory (FCT~93), Szeged (Hungary) 1993}, number 710 in Lecture
  Notes in Computer Science, pages 1--15, Berlin-Heidelberg-New York, 1993.
  Springer.
\newblock Invited Lecture.

{\sl{}}

\bibitem[Die94]{die94}
V.~Diekert.
\newblock A partial trace semantics for {P}etri nets.
\newblock {\em Theoretical Computer Science}, 1994.
\newblock To appear in the special issue of ICWLC~92, Kyoto (Japan) 1992.


\bibitem[Dij74]{dij74}
E.W. Dijkstra.
\newblock Self-stabilizing systems in spite of distributed control.
\newblock {\em Communications of ACM}, 17(11):643--644, 1974.


\bibitem[Dil50]{dil50}
R.P. Dilworth.
\newblock A decomposition theorem for partially ordered sets.
\newblock {\em Annals of Mathematics}, 51:161--166, 1950.

{\sl{}}

\bibitem[DJ90]{dj90}
N.~Dershowitz and J.P. Jouannaud.
\newblock Rewrite systems.
\newblock In Jan van Leeuwen, editor, {\em Handbook of Theoretical Computer
  Science}, volume~B, pages 243--320. Elsevier, Amsterdam, 1990.

{\sl{}}

\bibitem[DK90a]{dk90}
G.~Duchamp and D.~Krob.
\newblock The lower central series of the free partially commutative group.
\newblock Technical Report 90.64, LITP, Paris, 1990.

{\sl{}}

\bibitem[DK90b]{dk90lncs}
G.~Duchamp and D.~Krob.
\newblock Partially commutative formal power series.
\newblock In I.~Guessarian, editor, {\em Semantics of Systems of Concurrent
  Processes}, volume 469 of {\em Lecture Notes in Computer Science}, pages
  256--276, Berlin-Heidelberg-New York, 1990. Springer.

{\sl{}This paper is a short survey of elimination theory for the trace monoid.
  Partially commutative recognizable series are especially studied.}

\bibitem[DK91a]{dk91c}
G.~Duchamp and D.~Krob.
\newblock Computing with {P.B.W.} in enveloping algebras.
\newblock In G.~Jacob and Lamnabhi-Lagarrigue F., editors, {\em Algebraic
  Computing in Control}, volume 165 of {\em Lecture Notes in Computer Science},
  pages 223--240, Berlin-Heidelberg-New York, 1991. Springer.

{\sl{}This paper extends a result of Melan\c con and Reutenauer and gives an
  algorithm for computing nilpotent structural approximations of an analytic
  dynamical system whose command Lie algebra is partially commutative.}

\bibitem[DK91b]{dk91a}
G.~Duchamp and D.~Krob.
\newblock Factorisations dans le mono{\"{\i}}de partiellement commutatif libre.
\newblock {\em C.R.A.S. Paris, S\'erie I}, 312(1):189--192, 1991.

{\sl{}This paper is a survey without proofs of elimination results for the
  different partially commutative structures.}

\bibitem[DK91c]{dk91b}
G.~Duchamp and D.~Krob.
\newblock Lazard's factorizations of free partially commutative monoids.
\newblock In J.~Leach-Albert, B.~Monien, and M.~Rodriguez~Artalejo, editors,
  {\em Automata, Languages and Programming -- Proceedings of 18th ICALP},
  volume 510 of {\em Lecture Notes in Computer Science}, pages 242--253,
  Berlin-Heidelberg-New York, 1991. Springer.

{\sl{}This paper presents elimination theory for the trace monoid. Several
  algorithms for computing $Z$-codes are given. Lyndon traces are defined for
  the first time in the elimination context.}

\bibitem[DK92a]{dk92c}
G.~Duchamp and D.~Krob.
\newblock The central lower series of the free partially commutative group.
\newblock {\em Semigroup Forum}, 45:385--394, 1992.

{\sl{}A basic commutator calculus for the trace group is proposed here. It is
  also proved that the quotients of the lower central series of the trace group
  are free abelian groups and hence that the trace group is totally orderable.}

\bibitem[DK92b]{dk92a}
G.~Duchamp and D.~Krob.
\newblock The free partially commutative {L}ie algebra : bases and ranks.
\newblock {\em Advances in Maths.}, 95(1):92--126, 1992.

{\sl{}This paper is the first one to deal with elimination theory. It
  generalizes the classical Lazard's elimination theorem in the context of
  partially commutative Lie algebras and gives an effective way for computing
  bases of such Lie algebras.}

\bibitem[DK92c]{dk92b}
G.~Duchamp and D.~Krob.
\newblock On the partially commutative shuffle product.
\newblock {\em Theoretical Computer Science}, 96:405--410, 1992.

{\sl{}This paper gives recursive formulas for computing the shuffle product of
  two traces.}

\bibitem[DK93a]{dk93a}
G.~Duchamp and D.~Krob.
\newblock Free partially commutative structures.
\newblock {\em Journal of Algebra}, 156(2):318--361, 1993.

{\sl{}Elimination results are given for free partially commutative groups,
  monoids, Lie algebras and associative algebras in a systematic way.
  Optimality decomposition results are also proved.}

\bibitem[DK93b]{dk93b}
G.~Duchamp and D.~Krob.
\newblock Partially commutative {M}agnus transformations.
\newblock {\em Int. Journ. of Alg. and Comput.}, 3(1):15--41, 1993.

{\sl{}The partially commutative Magnus transformation is proved to be
  injective. Several applications are given (p-adic Hall topology, least root
  in trace groups, commutators in trace groups).}

\bibitem[DM93]{dm93}
V.~Diekert and A.~Muscholl.
\newblock Deterministic asynchronous automata for infinite traces.
\newblock In P.~Enjalbert, A.~Finkel, and K.~W. Wagner, editors, {\em
  Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer
  Science (STACS'93), W{\"u}rzburg 1993}, number 665 in Lecture Notes in
  Computer Science, pages 617--628, Berlin-Heidelberg-New York, 1993. Springer.

{\sl{}}

\bibitem[Dor87]{dor87}
D.Z. Dorovic.
\newblock A generalization of {W}itt's formulae.
\newblock {\em Journal of Algebra}, 11:262--278, 1987.

{\sl{}}

\bibitem[DOR91]{dor91}
V.~Diekert, E.~Ochma{\'n}ski, and K.~Reinhardt.
\newblock On confluent semi-commutation systems -- decidability and complexity
  results.
\newblock In J.~Leach~Albert et~al., editors, {\em Proceedings of the 18th
  International Colloquium on Automata Languages and Programming (ICALP'91),
  Madrid (Spain) 1991}, number 510 in Lecture Notes in Computer Science, pages
  229--241, Berlin-Heidelberg-New York, 1991. Springer.
\newblock An extended version to appear in Information and Computation.

{\sl{}}

\bibitem[Dro]{dro}
C.~Droms.
\newblock Residual nilpotence of graph groups.
\newblock Non published.

\bibitem[Dro85]{dro85}
C.~Droms.
\newblock Graph groups, coherence and three-manifolds.
\newblock {\em Journal of Algebra}, 106(2):484--489, 1985.

{\sl{}}

\bibitem[Dro87a]{dro87pams}
C.~Droms.
\newblock Isomorphisms of graph groups.
\newblock {\em Proc. Amer. Math. Soc.}, 100:407--408, 1987.

{\sl{}It is shown that two graph groups are isomorphic iff the dependance
  alphabets are isomorphic.}

\bibitem[Dro87b]{dro87ja}
C.~Droms.
\newblock Subgroup of graph groups.
\newblock {\em Journal of Algebra}, 110:519--522, 1987.

{\sl{}The author classifies the trace groups for which every subgroup is still
  isomorphic to a graph group.}

\bibitem[Dro90]{dro90}
M.~Droste.
\newblock Concurrency, automata and domains.
\newblock In M.S. Paterson, editor, {\em Proceedings of the 17th International
  Colloquium on Automata Languages and Programming (ICALP'90), Warwick
  (England) 1990}, number 443 in Lecture Notes in Computer Science, pages
  195--208, Berlin-Heidelberg-New York, 1990. Springer.

{\sl{}}

\bibitem[DRar]{dr94}
V.~Diekert and G.~Rozenberg, editors.
\newblock {\em Book of Traces}.
\newblock World Scientific, Singapore, to appear.

{\sl{}}

\bibitem[DT92]{dt92}
G.~Duchamp and J.Y. Thibon.
\newblock Simple orderings for free partially commutative groups.
\newblock {\em Int. Journ. of Alg. and Comput.}, 2(3):351--355, 1992.

{\sl{}Using the partially commutative Magnus transformation, effective total
  orders on the trace group are constructed.}

\bibitem[Dub85]{dub85}
C.~Duboc.
\newblock Some properties of commutations in free partially commutative
  monoids.
\newblock {\em Information Processing Letters}, 20:1--4, 1985.

{\sl{}}

\bibitem[Dub86a]{dub86}
C.~Duboc.
\newblock Commutations dans les monoides libres: un cadre th{\'e}orique pour
  l{\'e}tude du parallelisme.
\newblock Th{\`e}se, Facult{\'e} des Sciences de l'Universit{\'e} de Rouen,
  1986.

{\sl{}}

\bibitem[Dub86b]{dub86tcs2}
C.~Duboc.
\newblock Mixed product and asynchronous automata.
\newblock {\em Theoretical Computer Science}, 48:183--199, 1986.

{\sl{}}

\bibitem[Dub86c]{dub86tcs1}
C.~Duboc.
\newblock On some equations in free partially commutative monoids.
\newblock {\em Theoretical Computer Science}, 46:159--174, 1986.

{\sl{}}

\bibitem[Duc87]{duc87}
G.~Duchamp.
\newblock {\em Algorithmes sur les polyn\^omes en variables non commutatives}.
\newblock Th\`ese de doctorat, Universit\'e Paris 7, 1987.

{\sl{}Several algorithms concerning partially comutative polynomials are
  proposed and discussed here.}

\bibitem[Duc89]{duc89}
G.~Duchamp.
\newblock On the free partially commutative {L}ie algebra.
\newblock Technical report 89-74, {LITP} -- Universit\'e Paris 7, 1989.

{\sl{}The partially commutative free Lie algebra is proved to be a free
  $\Z$-module (using however a noneffective method).}

\bibitem[DV84]{dv84}
M.P. Delest and G.~Viennot.
\newblock Algebraic languages and polyominoes enumeration.
\newblock {\em Theoretical Computer Science}, 34:169--206, 1984.

{\sl{}}

\bibitem[DV89]{dv89}
V.~Diekert and W.~Vogler.
\newblock On the synchronization of traces.
\newblock {\em Mathematical Systems Theory}, 22:161--175, 1989.
\newblock A preliminary extended abstract appeared at MFCS~88, Lecture Notes in
  Computer Science {\rm 324} (1988) 271-279.

{\sl{}}

\bibitem[Ebi92]{ebi92}
Werner Ebinger.
\newblock On logical definability of $\omega$-trace languages.
\newblock In Volker Diekert and Werner Ebinger, editors, {\em {P}roceedings
  {ASMICS} {W}orkshop {I}nfinite {T}races, {T}{\"u}bingen}, Bericht 4/92, pages
  106--122. Universit{\"a}t Stuttgart, Fakult{\"a}t Informatik, 1992.

{\sl{}}

\bibitem[EH85]{eh85}
E.A. Emerson and J.Y. Halpern.
\newblock Decision procedures and expressiveness in the temporal logic of
  branching time.
\newblock {\em Journal of Computer and System Sciences}, 30:1--24, 1985.

{\sl{}}

\bibitem[EH86]{eh86}
E.A. Emerson and J.Y. Halpern.
\newblock Sometimes and ``not never'' revisited: On branching versus linear
  time temporal logic.
\newblock {\em Journal of the Association of Computing Machinery},
  33(1):151--178, 1986.

{\sl{}}

\bibitem[EHR]{ehr93b}
A.~Ehrenfeucht, H.J. Hoogeboom, and G.~Rozenberg.
\newblock Combinatorial properties of dependence graphs.
\newblock To be published in Information and Computation; 1994.

\bibitem[EHR93]{ehr93a}
A.~Ehrenfeucht, H.J. Hoogeboom, and G.~Rozenberg.
\newblock On the structure of recognizable languages of dependence graphs.
\newblock {\em R.A.I.R.O. --- Informatique {T}h{\'e}orique et Applications},
  27:7--22, 1993.

{\sl{}}

\bibitem[Eil74]{eil74}
S.~Eilenberg.
\newblock {\em Automata, Languages and Machines}, volume~A.
\newblock Academic Press, New York and London, 1974.

{\sl{}}

\bibitem[EL87]{el87}
E.A. Emerson and C.L. Lei.
\newblock Modalities for model checking: Branching time logics strikes back.
\newblock {\em Science of Computer Programming}, 8:275--306, 1987.

{\sl{}}

\bibitem[EM65]{em65}
C.C. Elgot and J.E. Mezei.
\newblock On relations defined by generalized finite automata.
\newblock {\em IBM J. Research and Development}, 9:47--68, 1965.

{\sl{}}

\bibitem[EM93]{em93}
Werner Ebinger and Anca Muscholl.
\newblock Logical definability on infinite traces.
\newblock In Andrzej Lingas, Rolf Karlsson, and Svante Carlsson, editors, {\em
  Proceedings of the 20th International Colloquium on Automata Languages and
  Programming (ICALP'93), Lund (Sweden) 1993}, number 700 in Lecture Notes in
  Computer Science, pages 335--346, Berlin-Heidelberg-New York, 1993. Springer.

{\sl{}}

\bibitem[ER87]{er87}
A.~Ehrenfeucht and G.~Rozenberg.
\newblock On the structure of dependence graphs.
\newblock In K.~Voss, H.J. Genrich, and G.~Rozenberg, editors, {\em Concurrency
  and Nets}, pages 141--170, Berlin-Heidelberg-New York, 1987. Springer.

{\sl{}}

\bibitem[ES69]{es69}
S.~Eilenberg and M.P. Sch{\"u}tzenberger.
\newblock Rational sets in commutative monoids.
\newblock {\em Journal of Algebra}, 13:173--191, 1969.

{\sl{}}

\bibitem[ES88]{es88}
E.A. Emerson and J.~Srinivasan.
\newblock Branching time temporal logic.
\newblock In G.~Rozenberg J.~W.~de Bakker, W.-P. de~Roever, editor, {\em Linear
  Time, Branching Time and Partial Order in Logics and Models for Concurrency},
  number 354 in Lecture Notes in Computer Science, pages 123--172,
  Berlin-Heidelberg-New York, 1988. Springer.

{\sl{}}

\bibitem[Fau87]{fau87}
H.~Fauconnier.
\newblock S\'emantique asynchrone et comportements infinis en {CSP}.
\newblock {\em Theoretical Computer Science}, 54:277--298, 1987.

{\sl{}The first aim of this paper is to abstract finite and infinite behaviours
  of CSP programs by equivalence class of words. It turns out that the
  equivalence on words introduced is precisely the equivalence which defines
  real traces. Then, some problems concerning fairness are addressed.}

\bibitem[Fis86]{fis86}
W.~Fischer.
\newblock {\"U}ber erkennbare und rationale {M}engen in freien partiell
  kommutativen {M}onoiden.
\newblock Report {FBI-HH-B}-121/86, Fach\-be\-reich Informatik der
  Universit{\"a}t Hamburg, Hamburg, 1986.
\newblock (Diplomarbeit 1985).

{\sl{}}

\bibitem[Fla87]{fla87}
P.~Flajolet.
\newblock Analytic models and ambiguity of context-free languages.
\newblock {\em Theoretical Computer Science}, 49:283--309, 1987.

{\sl{}}

\bibitem[Fli72]{fli72}
M.~Fliess.
\newblock {\em Sur certaines familles de s\'eries formelles}.
\newblock Th\`ese d'etat, Universit\'e Paris 7, 1972.

{\sl{}}

\bibitem[Fli74]{fli74}
M.~Fliess.
\newblock Matrices de {H}ankel.
\newblock {\em J. Math. Pures et Appl.}, 53:197--224, 1974.

{\sl{}}

\bibitem[FR68]{fr68}
P.C. Fischer and A.L. Rosenberg.
\newblock Multitape non writing automata.
\newblock {\em Journal of Computer and System Sciences}, 2:88--101, 1968.

{\sl{}}

\bibitem[FR84]{fr84}
M.P. Fl{\'e} and G.~Roucairol.
\newblock Multiserialization of iterated transactions.
\newblock {\em Information Processing Letters}, 18:243--247, 1984.

{\sl{}}

\bibitem[FR85a]{fr85}
M.P. Fl{\'e} and G.~Roucairol.
\newblock Fair serializability of iterated transactions using fifo-nets.
\newblock In G.~Rozenberg, editor, {\em Advances in Petri Nets}, number 188 in
  Lecture Notes in Computer Science, pages 154--168. Springer,
  Berlin-Heidelberg-New York, 1985.

{\sl{}}

\bibitem[FR85b]{fr85tcs}
M.P. Fl{\'e} and G.~Roucairol.
\newblock Maximal serializability of iterated transactions.
\newblock {\em Theoretical Computer Science}, 38:1--16, 1985.

{\sl{}This paper presents one of the first implicit definition of infinite
  traces. This definition is given through the study of serializability of
  infinite behaviours of a system of transactions.}

\bibitem[Gas87]{gas87}
P.~Gastin.
\newblock {\em Un mod\`ele distribu\'e}.
\newblock Th{\`e}se, {LITP}, Universit\'e Paris~7 (France), 1987.

{\sl{}This thesis introduces and studies a model for finite and infinite
  CSP-like distributed systems. A behaviour is represented by a vector of
  sequential behaviours together with synchronizations. The finite part of this
  model turns out to be isomorphic to the monoid of finite traces. Then, the
  definition and some basic properties of real traces are given.}

\bibitem[Gas90a]{gas90}
P.~Gastin.
\newblock Infinite traces.
\newblock In I.~Guessarian, editor, {\em Proceedings of the Spring School of
  Theoretical Computer Science on Semantics of Systems of Concurrent
  Processes}, number 469 in Lecture Notes in Computer Science, pages 277--308,
  Berlin-Heidelberg-New York, 1990. Springer.

{\sl{}This paper generalizes to real traces Levi's lemma and the Foata normal
  form. The set of real traces provided with the prefix partial order is proved
  to be a coherently complete Poset. A metric on real traces is introduced. It
  is proved that the metric space of real traces is complete and that the
  concatenation is continuous whenever it is defined. Finally, the family of
  recognizable languages of real traces is introduced and is proved to be
  closed under the boolean operations (union, intersection and complement) and
  under concatenation. Recognizable real trace languages are characterized by a
  syntactic congruence.}

\bibitem[Gas90b]{gas90tcs}
P.~Gastin.
\newblock Un mod\`ele asynchrone pour les syst\`emes distribu\'es.
\newblock {\em Theoretical Computer Science}, 74:121--162, 1990.

{\sl{}This paper introduced and study a model for finite and infinite CSP-like
  distributed systems. A behaviour is represented by a vector of sequential
  behaviours together with synchronizations. The finite part of this model
  turns out to be isomorphic to the monoid of finite traces. Then, the
  definition and some basic properties of real traces are given.}

\bibitem[Gas91]{gas91}
P.~Gastin.
\newblock Recognizable and rational trace languages of finite and infinite
  traces.
\newblock In Choffrut C. et~al., editors, {\em Proceedings of the 8th Annual
  Symposium on Theoretical Aspects of Computer Science (STACS'91), Hamburg
  1991}, number 480 in Lecture Notes in Computer Science, pages 89--104,
  Berlin-Heidelberg-New York, 1991. Springer.

{\sl{}This paper is devoted to the study of recognizable and rational languages
  of real traces. Recognizable languages are characterized by means of a
  syntactic congruence. The family of Recognizable languages is closed under
  union, intersection, complement and concatenation. Contrary to the finite
  iteration, the infinite iteration of a single finite trace is always
  recognizable. Rational trace languages are defined and it is proved that all
  rational real trace language may be obtained with a simple rational
  expression.}

\bibitem[GKP92]{gkp92}
U.~Goltz, R.~Kuiper, and W.~Penczek.
\newblock Propositional temporal logics and equivalences.
\newblock In W.R. Claveland, editor, {\em Proceedings of Third International
  Conference on Concurrency Theory CONCUR'92}, number 630 in Lecture Notes in
  Computer Science, pages 222--235, Berlin-Heidelberg-New York, 1992. Springer.

{\sl{}The equivalences induced on models by temporal logics interpreted on
  occurrence transition systems generated by prime event structures are
  compared. The induced equivalences are also compared to directly defined
  equivalences, e.g., bisimulations, pomset trace equivalence and others. It is
  shown which of the induced equivalences are preserved under action
  refinement.}

\bibitem[God90]{god90}
P.~Godefroid.
\newblock Using partial orders to improve automatic verification methods.
\newblock In {\em Proceedings of Computer-Aided Verification Workshop, Rutgers,
  New Jersey, 1990}, number 531 in Lecture Notes in Computer Science, pages
  176--185, Berlin-Heidelberg-New York, 1990. Springer.


\bibitem[Gol88]{gol88}
M.~Goldwurm.
\newblock {\em Formal series methods in algorithm analysis of problems of
  languages}.
\newblock PhD thesis, Universit{\`a} di Milano, May 1988.

{\sl{}}

\bibitem[Gol90a]{gol90k}
M.~Goldwurm.
\newblock Evaluations of the number of prefixes of traces : an application to
  algorithm analysis.
\newblock In V.~Diekert, editor, {\em Proceedings of the {ASMICS} workshop
  {F}ree {P}artially {C}ommutative {M}onoids, {K}ochel am {S}ee, {O}ktober
  1989}, {R}eport {TUM-I9002}, {T}echnical {U}niversity of {M}unich, pages 68--
  80, 1990.

{\sl{}}

\bibitem[Gol90b]{gol90ijfcs}
M.~Goldwurm.
\newblock Some limit distributions in analysis of algorithms for problems on
  trace languages.
\newblock {\em International Journal of Foundations of Computer Science},
  1(3):265--276, 1990.
\newblock Also appeared in Proceedings 3rd Italian Conference of Theoretical
  Computer Science, World Scientific 1989, 285-298.

{\sl{}The limit distribution of the number of prefixes of traces of fixed
  length is obtained for any f.p.c.m. given by the direct product of free
  monoids over disjoint alphabets. It can be either a chi-square or a normal
  distribution according whether the sizes of the alphabets are equal.}

\bibitem[Gol92]{gol92}
M.~Goldwurm.
\newblock Probabilistic estimation of the number of prefixes of a trace.
\newblock {\em Theoretical Computer Science}, 92:249--268, 1992.

{\sl{}Asymptotic expressions of the average number of prefixes of a trace of
  given length are obtained under the assumption that all representative
  strings are equiprobable. Similar evaluations are obtained for the variance
  of the same random variable.}

\bibitem[Gon93]{gon93}
D.~Gonzalez.
\newblock {\em D{\'e}composition de semi-commutations}.
\newblock Th{\`e}se, Universit{\'e} des Sciences et Technologies de Lille
  (France), 1993.

{\sl{}}

\bibitem[GOPR92]{gopr92}
P.~Gastin, E.~Ochma{\'n}ski, A.~Petit, and B.~Rozoy.
\newblock Decidability of the star problem in a$^{*}\times $\{b\}$^{*}$.
\newblock {\em Information Processing Letters}, 44:65--71, 1992.


\bibitem[GP92a]{gp92icalp}
Paul Gastin and Antoine Petit.
\newblock Asynchronous automata for infinite traces.
\newblock In W.~Kuich, editor, {\em Proceedings of the 19th International
  Colloquium on Automata Languages and Programming (ICALP'92), Vienna (Austria)
  1992}, number 623 in Lecture Notes in Computer Science, pages 583--594,
  Berlin-Heidelberg-New York, 1992. Springer.

{\sl{}A characterization of recognizable languages of infinite traces using
  asynchronous cellular automata (which carry the intuitive idea of finite
  state concurrent machines) is provided. To this purpose, effective
  constructions for $c-$rational operations on these automata, which are of
  independent interest, are given.}

\bibitem[GP92b]{gp92mfcs}
Paul Gastin and Antoine Petit.
\newblock Poset properties of complex traces.
\newblock In I.~M. Havel and V.~Koubek, editors, {\em Proceedings of the 17th
  Symposium on Mathematical Foundations of Computer Science (MFCS'92), Prague,
  (Czechoslovakia), 1992}, number 629 in Lecture Notes in Computer Science,
  pages 255--263, Berlin-Heidelberg-New York, 1992. Springer.

{\sl{}This paper investigates PoSet properties of the set of infinite
  dependence graphs and of the set of complex traces provided with the prefix
  partial order relation. The set of infinite dependence graphs is bounded
  complete and (prime) algebraic. The set of complex traces is coherently
  (whence directed) complete, but in general, it is not algebraic.}

\bibitem[GPZ91]{gpz91}
P.~Gastin, A.~Petit, and W.~Zielonka.
\newblock A {K}leene theorem for infinite trace languages.
\newblock In J.~Leach~Albert et~al., editors, {\em Proceedings of the 18th
  International Colloquium on Automata Languages and Programming (ICALP'91),
  Madrid (Spain) 1991}, number 510 in Lecture Notes in Computer Science, pages
  254--266, Berlin-Heidelberg-New York, 1991. Springer.

{\sl{}The first paper which generalizes Kleene's and Ochma\'nski's theorems to
  real traces. It is proved that the families of $c-$rational and of
  recognizable languages of real traces coincide. The proofs use the links
  between recognizable languages of real traces and recognizable languages of
  infinite words.}

\bibitem[GPZ92]{gpz92}
P.~Gastin, A.~Petit, and W.~Zielonka.
\newblock An extension of {K}leene's and {O}chma{\'n}ski's theorems to infinite
  traces.
\newblock Tech. {R}ep. {LITP} 92.56, Universit\'e Paris~6 (France), 1992.
\newblock To appear in Theoretical Computer Science.

{\sl{}The basic families of recognizable sets and of rational sets of infinite
  traces are investigated. The main result is an extension of Kleene's and
  Ochma{\'n}ski's theorems to the domain of infinite traces. Using recognizing
  and weakly recognizing morphisms, and a generalization of the
  Sch{\"u}tzenberger product of monoids, various closure properties of
  recognizable trace languages are proved. Moreover, normal form
  representations for recognizable and rational sets of infinite traces are
  established.}

\bibitem[GR93]{gr93}
P.~Gastin and B.~Rozoy.
\newblock The poset of infinitary traces.
\newblock {\em Theoretical Computer Science}, 120:101--121, 1993.

{\sl{}The set of real traces provided with the prefix partial order is proved
  to be a coherently complete prime algebraic domain, whence a Scott-domain. A
  representation theorem between the class of posets of real traces and a
  subclass of labeled prime event structures is established.}

\bibitem[Gra81]{gra81}
J.~Grabowsky.
\newblock On partial languages.
\newblock {\em Ann. Soc. Math. Pol.}, IV.2:428--498, 1981.

{\sl{}}

\bibitem[GRS80]{grs80}
R.L. Graham, B.L. Rothschild, and J.H. Spencer.
\newblock {\em Ramsey Theory}.
\newblock John Wiley \& Sons, New York, 1980.

{\sl{}A reference book on Ramsey theory.}

\bibitem[GRS91]{grs91}
Giovanna Guaiana, Antonio Restivo, and Sergio Salemi.
\newblock On aperiodic trace languages.
\newblock In Choffrut C. et~al., editors, {\em Proceedings of the 8th Annual
  Symposium on Theoretical Aspects of Computer Science (STACS'91), Hamburg
  1991}, number 480 in Lecture Notes in Computer Science, pages 76--88,
  Berlin-Heidelberg-New York, 1991. Springer.

{\sl{}}

\bibitem[GRS92]{grs92}
Giovanna Guaiana, Antonio Restivo, and Sergio Salemi.
\newblock Star-free trace languages.
\newblock {\em Theoretical Computer Science}, 97:301--311, 1992.

{\sl{}}

\bibitem[GW91]{gw91}
P.~Godefroid and P.~Wolper.
\newblock A partial approach to model checking.
\newblock In {\em Proceedings of the 6th IEEE Symposium on Logic in Computer
  Science}, pages 406--415, 1991.

{\sl{}}

\bibitem[Hal50]{hal50}
M.~Hall.
\newblock A basis for free {L}ie rings and higher commutators in free groups.
\newblock {\em Proc. Amer. Math. Soc.}, 1:575--581, 1950.

{\sl{}}

\bibitem[Har78]{har78}
Michael~A. Harrison.
\newblock {\em Introduction to Formal Language Theory}.
\newblock Addison-Wesley publishing company, 1978.

{\sl{}}

\bibitem[Har79]{har79}
D.~Harel.
\newblock {\em First-order Dynamic Logic}.
\newblock Number~68 in Lecture Notes in Computer Science. Springer,
  Berlin-Heidelberg-New York, 1979.

{\sl{}}

\bibitem[Har85]{har85}
D.~Harel.
\newblock Recurring dominoes: Making the highly undecidable highly
  understandable.
\newblock {\em Annals of Discrete Mathematics}, 24:51--72, 1985.

{\sl{}}

\bibitem[Has79]{has79}
K.~Hashiguchi.
\newblock A decision procedure for the order of regular events.
\newblock {\em Theoretical Computer Science}, 8:69--72, 1979.


\bibitem[Has91]{has91}
K.~Hashiguchi.
\newblock Recognizable closures and submonoids of free partially commutative
  monoids.
\newblock {\em Theoretical Computer Science}, 86:233--241, 1991.


\bibitem[HK89]{hk89}
D.~V. Hung and E.~Knuth.
\newblock Semi-commutations and {P}etri-nets.
\newblock {\em Theoretical Computer Science}, 34:67--81, 1989.

{\sl{}}

\bibitem[HK91]{hk91}
T.~Harjiu and J.~Karhum{\"a}ki.
\newblock Decidability of the multeplicity equivalence of multitape finite
  automata.
\newblock {\em Theoretical Computer Science}, 78:347--355, 1991.

{\sl{}}

\bibitem[HKT92]{hkt92}
P.~W. Hoogers, H.~C.~M. Kleijn, and P.~S. Thiagarajan.
\newblock A trace semantics for petri nets.
\newblock In W.~Kuich, editor, {\em Proceedings of the 19th International
  Colloquium on Automata Languages and Programming (ICALP'92), Vienna (Austria)
  1992}, number 623 in Lecture Notes in Computer Science, pages 595--604,
  Berlin-Heidelberg-New York, 1992. Springer.

{\sl{}}

\bibitem[Hme76]{hme76}
J.I. Hmelevskii.
\newblock {\em Equations in Free Semigroups}.
\newblock Number 107. 1976.

{\sl{}}

\bibitem[Hoa85]{hoa85}
C.A.R. Hoare.
\newblock {\em Communicating Sequential Processes}.
\newblock Prentice-Hall International, London, 1985.

{\sl{}}

\bibitem[HR86]{hr86}
H.J. Hoogeboom and G.~Rozenberg.
\newblock Infinitary languages: {B}asic theory and applications to concurrent
  systems.
\newblock In J.W. Bakker et~al., editors, {\em Current Trends in Concurrency},
  number 242 in Lecture Notes in Computer Science, pages 266--342,
  Berlin-Heidelberg-New York, 1986. Springer.

{\sl{}}

\bibitem[HY93]{hy93}
Kosaburo Hashiguchi and Kazuya Yamada.
\newblock String matching problems over free partially commutative monoids.
\newblock {\em Information and Computation}, 101:131--149, 1993.

{\sl{}}

\bibitem[Iba78]{iba78}
O.H. Ibarra.
\newblock Reversal-bounded multicounter machines and their decision problems.
\newblock {\em Journal of the Association of Computing Machinery}, 25:116--133,
  1978.

{\sl{}}

\bibitem[JPS90]{jps90}
S.~Jesi, G.~Pighizzini, and N.~Sabadini.
\newblock Probabilistic asynchronous automata.
\newblock In V.~Diekert, editor, {\em {P}roceedings of a workshop of the
  {ESPRIT} {B}asic {R}esearch {A}ction {N}o 3166: {A}lgebraic and {S}yntactic
  {M}ethods in {C}omputer {S}cience {(ASMICS)}, {K}ochel am {S}ee, {B}avaria,
  {FRG} (1989)}, {R}eport {TUM-I9002}, {T}echnical {U}niversity of {M}unich,
  pages 99--114, 1990.

{\sl{}Probabilistic asynchronous automata are introduced, giving a non trivial
  generalization of Zielonka's theorem for acyclic dependence graph.}

\bibitem[JR81]{jr81}
D.~Janssens and G.~Rozenberg.
\newblock A characterization of context-free string languages by directed
  node-label controlled graph grammars.
\newblock {\em Acta Informatica}, 16:63--85, 1981.

{\sl{}}

\bibitem[Kar82]{kar82}
M.~Karonski.
\newblock A review of random graphs.
\newblock {\em Journal of Graph Theory}, 6:349--389, 1982.

{\sl{}}

\bibitem[Kel73]{kel73}
R.~Keller.
\newblock Parallel program schemata and maximal parallelism~{I}. {F}undamental
  results.
\newblock {\em Journal of the Association of Computing Machinery}, 20:514--537,
  1973.

{\sl{}}

\bibitem[KK]{kkb}
M.~Katsura and Y.~Kobayashi.
\newblock Lyndon traces and shuffle algebras.
\newblock Preprint.

\bibitem[KKar]{kka}
M.~Katsura and Y.~Kobayashi.
\newblock The shuffle algebra and its derivations.
\newblock {\em Theoretical Computer Science}, to appear.

{\sl{}Several properties and interesting formulas on the partially commutative
  shuffle product are given here.}

\bibitem[KL93]{kl93}
D.~Krob and P.~Lalonde.
\newblock Partially commutative {L}yndon words.
\newblock In P.~Enjalbert, A.~Finkel, and K.W. Wagner, editors, {\em
  Proceedings of STACS'93}, volume 665 of {\em Lecture Notes in Computer
  Science}, pages 237--246. Springer, 1993.

{\sl{}This paper connects Lalonde's Lyndon traces with Duchamp-Krob's ones.}

\bibitem[Kle56]{kle56}
S.C. Kleene.
\newblock Representation of events in nerve nets and finite automata.
\newblock In McCarthy Shannon, editor, {\em Automata Studies}, pages 3--40.
  1956.


\bibitem[KMLNR80]{kmn80}
K.H. Kim, L.~Makar-Limanov, J.~Neggers, and F.W. Roush.
\newblock Graph algebras.
\newblock {\em Journal of Algebra}, 64:46--51, 1980.

{\sl{}This paper proves that two free associative partially commutative
  algebras are isomorphic iff their dependance graphs are isomorphic.}

\bibitem[KMP77]{kmp77}
D.E. Knuth, J.~Morris, and V.~Pratt.
\newblock Fast pattern matching in strings.
\newblock {\em Siam J. on Computing}, 6:323--350, 1977.

{\sl{}}

\bibitem[Kob]{kob}
Y.~Kobayashi.
\newblock Partially commutative shuffling.
\newblock Preprint.

\bibitem[Kob90]{kob90}
Y.~Kobayashi.
\newblock Complete rewriting systems and homology of monoid algebras.
\newblock {\em J. Pure Appl. Algebra}, 65:263--275, 1990.

{\sl{}}

\bibitem[Kob92]{kob92}
Y.~Kobayashi.
\newblock Partial commutation, homology and the {M}{\"o}bius inversion formula.
\newblock In M.~Ito, editor, {\em {W}ords, {L}anguages and {C}ombinatorics
  (Kyoto, Japan 1990)}, pages 288--298. World Scientific, Singapore, 1992.

{\sl{}}

\bibitem[K{\"o}n91]{koe91}
R.~K{\"o}nig.
\newblock Graphs and free partially commutative monoids.
\newblock {\em Theoretical Computer Science}, 78:319--346, 1991.

{\sl{}}

\bibitem[KP90]{kp90}
S.~Katz and D.~Peled.
\newblock Defining conditional independence using collapses.
\newblock In M.Z. Kwiatkowska, M.W. Shields, and R.M. Thomas, editors, {\em
  Semantics for Concurrency}, Workshops in Computing, pages 262--280,
  Berlin-Heidelberg-New York, 1990. Springer.

{\sl{}}

\bibitem[KP91]{kp91}
S.~Katz and D.~Peled.
\newblock Interleaving set temporal logic.
\newblock {\em Theoretical Computer Science}, 75(3):21--43, 1991.


\bibitem[KP92]{kp92}
S.~Katz and D.~Peled.
\newblock Verification of distributed programs using representative
  interleaving sequences.
\newblock {\em Distributed Computing}, 6:107--120, 1992.

{\sl{}A logic, Interleaving Set Temporal Logic*, is introduced, enabling to
  quantify over runs as well as observations. A proof system is provided that
  is geared to properties that hold for every observation when proved for one
  convenient representative.}

\bibitem[KR80]{kr80}
K.H. Kim and F.W. Roush.
\newblock Homology of certain algebras defined by graphs.
\newblock {\em Journ. of Pure and Applied algebra}, 17:179--186, 1980.

{\sl{}}

\bibitem[KS86]{ks86}
W.~Kuich and A.~Salomaa.
\newblock {\em Semirings, Automata, Languages}.
\newblock Number~5 in EATCS Monographs on Theoretical Computer Science.
  Springer, Berlin-Heidelberg-New York, 1986.

{\sl{}}

\bibitem[KS92]{ks92}
M.~Kwiatkowska and M.~Stannett.
\newblock On transfinite traces.
\newblock In Volker Diekert and Werner Ebinger, editors, {\em {P}roceedings
  {ASMICS} {W}orkshop {I}nfinite {T}races, {T}{\"u}bingen}, Bericht 4/92, pages
  123--157. Universit{\"a}t Stuttgart, Fakult{\"a}t Informatik, 1992.

{\sl{}The main purpose of this paper is to defined transfinite traces. A
  generalization of the Foata normal form is given and used to define the
  equivalence on transfinite words which defines transfinite traces. In fact,
  it is much more easier to define transfinite traces using dependence graphs.}

\bibitem[Kur90]{kur90}
Walter Kurth.
\newblock {\em Termination und {K}onfluenz von {S}emi-{T}hue-{S}ystemen mit nur
  einer {R}egel}.
\newblock PhD thesis, Technische Universit{\"a}t {C}laustal-{Z}ellerfeld, 1990.

{\sl{}}

\bibitem[Kwi89a]{kwi89a}
M.~Kwiatkowska.
\newblock {\em Fairness for non-interleaving concurrency}.
\newblock {PhD} {T}hesis, University of Leicester (UK), 1989.

{\sl{}This thesis is devoted to the study of fairness properties. To this
  purpose, real traces are introduced and studied. The set of real traces
  ordered by the prefix relation is proved to be a Scott-domain.}

\bibitem[Kwi89b]{kwi89b}
M.~Kwiatkowska.
\newblock On infinitary trace languages.
\newblock Technical Report~31, University of Leicester (UK), 1989.

{\sl{}Real traces are defined as equivalence classes of words. The equivalence
  relation is defined by means of a trace preorder relation. The set of real
  traces ordered by the prefix relation is proved to be a Scott-domain. The
  relationship between real trace languages and Shield's asynchronous
  transition systems is investigated.}

\bibitem[Kwi90]{kwi90}
M.~Kwiatkowska.
\newblock A metric for traces.
\newblock {\em Information Processing Letters}, 35:129--135, 1990.

{\sl{}A metric on real traces which generalizes the natural metric on words is
  defined. The metric space of real traces is proved to be complete. It turns
  out that the topology induced by this metric is the Lawson topology on the
  Scott-domain of real traces. Therefore, it is also compact.}

\bibitem[Kwi91]{kwi91}
M.~Kwiatkowska.
\newblock On the domain of traces and sequential composition.
\newblock In S.~Abramsky and T.S.E.. Maibaum, editors, {\em Proceedings 16th
  Coll. on Trees in Algebra and Programming (CAAP'91), Brighton (UK)}, number
  493 in Lecture Notes in Computer Science, pages 42--56, Berlin-Heidelberg-New
  York, 1991. Springer.

{\sl{}The set of real traces is proved to be a Scott-domain and a complete
  metric space. The restriction of the concatenation to finite traces is not
  uniformly continuous, hence it does not extend canonically to real traces.
  Here a non associative concatenation is proposed.}

\bibitem[Lal]{lal}
P.~Lalonde.
\newblock Lyndon heaps : an analogue of {L}yndon words in partially commutative
  monoids.
\newblock preprint.

\bibitem[Lal79]{lal79}
G.~Lallement.
\newblock {\em Semigroups and Combinatorial Applications}.
\newblock John Wiley \& Sons, New York, 1979.

{\sl{}}

\bibitem[Lal90]{lal90}
P.~Lalonde.
\newblock {\em Contribution \`a la th\'eorie des empilements}, volume~4 of {\em
  Publications du LACIM}.
\newblock UQAM, 1990.

{\sl{}This PhD work contains the first construction of Lyndon traces using the
  terminology of Viennot's heaps of pieces. They are used to construct Lyndon
  bases of the free partially commutative Lie algebra.}

\bibitem[Lal91]{lal91}
P.~Lalonde.
\newblock Empilements de {L}yndon et bases d'alg\`ebres de {L}ie.
\newblock In M.~Delest, G.~Jacob, and P.~Leroux, editors, {\em Actes du
  colloque ``S\'eries formelles et combinatoire alg\'ebrique''}, pages
  275--286, 1991.

{\sl{}A survey of the main results of the PhD thesis of the author on Lyndon
  traces and Lyndon bases of the free partially commutative Lie algebra.}

\bibitem[Lat79]{lat79}
M.~Latteux.
\newblock C{\^o}nes rationnels commutatifs.
\newblock {\em Journal of Computer and System Sciences}, 18:307--333, 1979.

{\sl{}}

\bibitem[Lat92]{lat92}
M.~Latteux.
\newblock Some results on semi-commutations.
\newblock In M.~Ito, editor, {\em Proc.\ of the {I}nternational {C}olloquium on
  {W}ords, {L}anguages and {C}ombinatorics (Kyoto 1990)}. World Scientific,
  Singapore, 1992.
\newblock Appeared also as Technical Report {I}.{T} 201 Universit{\'e} de
  Lille.

{\sl{}}

\bibitem[Law88]{law88}
Jimmie~D. Lawson.
\newblock The versatile continuous order.
\newblock In M.~Main, A.~Melton, M.~Mislove, and D.~Schmidt, editors, {\em
  Proceedings of the Workshop on Mathematical Foundations of Programming
  Language Semantics}, number 298 in Lecture Notes in Computer Science, pages
  134--160, Berlin-Heidelberg-New York, 1988. Springer.

{\sl{}This paper is a survey of the basic properties of continuously ordered
  sets. In particular, order-theoretic aspects of continuously ordered sets and
  of domains, and Scott and Lawson topologies are presented.}

\bibitem[Laz54]{laz54}
M.~Lazard.
\newblock Sur les groupes nilpotents et les anneaux de {L}ie.
\newblock {\em Ann. Sci. ENS}, 3(71):101--190, 1954.

{\sl{}}

\bibitem[Laz60]{laz60}
M.~Lazard.
\newblock Groupes, anneaux de {L}ie et probl\`eme de {B}urnside.
\newblock Technical report, Inst. Mat. dell. Universita Roma, 1960.

{\sl{}A good presentation of Lazard's elimination theorems.}

\bibitem[Lev44]{lev44}
F.W. Levi.
\newblock On semigroups.
\newblock {\em Bull. Calcutta Math. Soc.}, 36:141--146, 1944.

{\sl{}}

\bibitem[Lot83]{lot83}
M.~Lothaire.
\newblock {\em Combinatorics on Words}.
\newblock Addison-Wesley, Reading, M.A., 1983.

{\sl{}}

\bibitem[LP85]{lp85}
O.~Lichtenstein and A.~Pnueli.
\newblock Checking that finite state concurrent programs satisfy their linear
  specification.
\newblock In {\em Proc. of the 12th ACM Symposium on Principles of Programming
  Languages}, pages 97--107, 1985.

{\sl{}}

\bibitem[LPRT94]{lprt92}
K.~Lodaya, R.~Parikh, R.~Ramanujam, and P.S. Thiagarajan.
\newblock A logical study of distributed transition systems.
\newblock {\em Information and Computation}, ??(??):??, 1994.
\newblock to appear.


\bibitem[LS67]{ls67}
A.~Lentin and M.-P. Sch{\"u}tzenberger.
\newblock Combinatorial problem in the theory of free monoids.
\newblock In Box and Bowling, editors, {\em Proceedings of the conference held
  at the University of North Carolina at Chapel Hill}, pages 128--144. North
  Carolina Press, 1967.

{\sl{}}

\bibitem[LS77]{ls77}
R.E. Lyndon and P.E. Schupp.
\newblock {\em Combinatorial group theory}.
\newblock Springer, Berlin-Heidelberg-New York, 1977.

{\sl{}}

\bibitem[LS81]{ls81}
A.~Lascoux and M.P. Sch{\"{u}}tzenberger.
\newblock Le mono{\"{\i}}de plaxique.
\newblock In {\em Qua\-der\-ni de ``La ricerca scientifica''}, volume 109,
  1981.

{\sl{}}

\bibitem[LV89]{lv89}
Ming Li and P.~Vitanyi.
\newblock How to share concurrent asynchronous wait-free variables.
\newblock In {\em Proceedings of the 16th International Colloquium on Automata,
  Languages and Programming (ICALP'89), Stresa (Italy) 1989}, number 372 in
  Lecture Notes in Computer Science, pages 488--505, Berlin-Heidelberg-New
  York, 1989. Springer.


\bibitem[LWZ90]{lwz90}
H.-N. Liu, C.~Wrathall, and K.~Zeger.
\newblock Efficient solution of some problems in free partially commutative
  monoids.
\newblock {\em Information and Computation}, 89:180--198, 1990.

{\sl{}}

\bibitem[Mac70]{macl70}
Saunders MacLane.
\newblock {\em Categories. For the Working Mathematician}.
\newblock Number~5 in Graduate Texts in Mathematics. Springer,
  Berlin-Heidelberg-New York, 1970.

{\sl{}}

\bibitem[Mag35]{mag35}
W.~Magnus.
\newblock Beziehungen zwischen {G}ruppen und {I}dealen in einen spe\-ziel\-len
  {R}ing.
\newblock {\em Math. Ann.}, CXI:259--280, 1935.

{\sl{}}

\bibitem[Mak83]{mak83}
G.S. Makanin.
\newblock The problem of solvability of equations in free semigroups.
\newblock {\em Math. USSR Izvestiya}, 21:483--546, 1983.

{\sl{}}

\bibitem[Maz77]{maz77}
A.~Mazurkiewicz.
\newblock Concurrent program schemes and their interpretations.
\newblock {DAIMI Rep. PB}~78, Aarhus University, Aarhus, 1977.

{\sl{}}

\bibitem[Maz84]{maz84}
A.~Mazurkiewicz.
\newblock Traces, histories, graphs: Instances of a process monoid.
\newblock In M.P. Chytil et~al., editors, {\em Proceeding of the 11th Symposium
  on Mathematical Foundations of Computer Science (MFCS'84), Praha (CSFR)
  1984}, number 176 in Lecture Notes in Computer Science, pages 115--133,
  Berlin-Heidelberg-New York, 1984. Springer.

{\sl{}}

\bibitem[Maz85]{maz85}
A.~Mazurkiewicz.
\newblock Semantics of concurrent systems: a modular fixed point approach.
\newblock In G.~Rozenberg, editor, {\em Advances in Petri nets}, number 188 in
  Lecture Notes in Computer Science, pages 353--375, Berlin-Heidelberg-New
  York, 1985. Springer.

{\sl{}}

\bibitem[Maz87]{maz87}
A.~Mazurkiewicz.
\newblock Trace theory.
\newblock In W.~Brauer et~al., editors, {\em Petri Nets, Applications and
  Relationship to other Models of Concurrency}, number 255 in Lecture Notes in
  Computer Science, pages 279--324, Berlin-Heidelberg-New York, 1987. Springer.

{\sl{}}

\bibitem[Maz88]{maz88}
A.~Mazurkiewicz.
\newblock Solvability of the asynchronous ranking problem.
\newblock {\em Information Processing Letters}, 28:221--224, 1988.


\bibitem[M{\'e}t86a]{met86icalp}
Y.~M{\'e}tivier.
\newblock On recognizable subsets of free partially commutative monoids.
\newblock In L.~Kott, editor, {\em Proceedings of the 13th International
  Colloquium on Automata Languages and Programming (ICALP'86), Rennes (France)
  1986}, number 226 in Lecture Notes in Computer Science, pages 254--264,
  Berlin-Heidelberg-New York, 1986. Springer.

{\sl{}}

\bibitem[M{\'e}t86b]{met86rairo}
Y.~M{\'e}tivier.
\newblock Une condition suffisante de reconnaissabilit{\'e} dans un
  mono{\"{\i}}de partiellement commutatif.
\newblock {\em R.A.I.R.O. --- Informatique {T}h{\'e}orique et Applications},
  20:121--127, 1986.

{\sl{}}

\bibitem[M{\'e}t87]{met87}
Y.~M{\'e}tivier.
\newblock An algorithm for computing asynchronous automata in the case of
  acyclic non-commutation graph.
\newblock In Th. Ottmann, editor, {\em Proceedings of the 14th International
  Colloquium on Automata, Languages and Programming (ICALP'87), {Karls\-ruhe}
  (FRG) 1987}, number 267 in Lecture Notes in Computer Science, pages 226--236,
  Berlin-Heidelberg-New York, 1987. Springer.

{\sl{}A simple construction of deterministic asynchronous automata is provided
  in the case when non-commutativity relation is acyclic.}

\bibitem[M{\'e}t88]{met88tcs}
Y.~M{\'e}tivier.
\newblock On recognizable subsets of free partially comutative monoids.
\newblock {\em Theoretical Computer Science}, 58:201--208, 1988.

{\sl{}It is proved that if $X$ is a recognizable set of words such that each
  iterative factor of $X$ yields a connected trace then the closure $[X]$ of
  $X$ under partial commutation remains recognizable.}

\bibitem[Mil80]{mil80}
R.~Milner.
\newblock {\em A Calculus of Communicating Systems}.
\newblock Number~92 in Lecture Notes in Computer Science. Springer,
  Berlin-Heidelberg-New York, 1980.

{\sl{}}

\bibitem[MK64]{mck64}
J.D. Mc~Knight.
\newblock Kleene quotient theorem.
\newblock {\em Pacific Journal of Mathematics}, pages 1343--1352, 1964.


\bibitem[MKS76]{mks76}
W.~Magnus, A.~Kharass, and D.~Solitar.
\newblock {\em Combinatorial group theory}.
\newblock Dover, 1976.

{\sl{}}

\bibitem[MM82]{mm82}
E.W. Mayr and A.R. Meyer.
\newblock The complexity of the word problems for commutative semigroups and
  polynomial ideals.
\newblock {\em Advances in Math.}, 46:305--329, 1982.

{\sl{}}

\bibitem[MO87]{mo87}
Y.~M{\'e}tivier and E.~Ochma\'nski.
\newblock On lexicographic semi-commutations.
\newblock {\em Information Processing Letters}, 26:55--59, 1987.

{\sl{}A characterization of semi-commutation systems for which the set of
  minimal words and the set of irreducible words are equal is given.}

\bibitem[MOP89]{mop89}
A.~Mazurkiewicz, E.~Ochma{\'n}ski, and W.~Penczek.
\newblock Concurrent systems and inevitability.
\newblock {\em Theoretical Computer Science}, 64:281--304, 1989.

{\sl{}}

\bibitem[MP91a]{mp91a}
Z.~Manna and A.~Pnueli.
\newblock Completing the temporal picture.
\newblock {\em Theoretical Computer Science}, 83(1):97--139, 1991.

{\sl{}}

\bibitem[MP91b]{mp91}
Z.~Manna and A.~Pnueli.
\newblock {\em The Temporal Logic of Reactive and Concurrent Systems,
  Specification}.
\newblock Springer, 1991.

{\sl{}}

\bibitem[MR91]{mr92}
Y.~M{\'e}tivier and B.~Rozoy.
\newblock On the star operation in free partially commutative monoids.
\newblock {\em International Journal of Foundations of Computer Science},
  2:257--265, 1991.

{\sl{}Let $X$ be a finite set of traces. A property of iterative factors of
  $X^*$ is presented that is subsequently used to provide a necessary condition
  for recognizability of $X^*$.}

\bibitem[MS89]{ms89}
P.~Massazza and N.~Sabadini.
\newblock Some applications and techniques for generating functions.
\newblock In J.~Diaz and F~Orejas, editors, {\em Proceedings Tapsoft 89 (CAAP
  89)}, number 351 in Lecture Notes in Computer Science, pages 321--336,
  Berlin-Heidelberg-New York, 1989. Springer.

{\sl{}}

\bibitem[NO88]{no88}
P.~Narendran and F.~Otto.
\newblock Preperfectness is undecidable for {T}hue systems containing only
  length-reducing rules and a single commutation rule.
\newblock {\em Information Processing Letters}, 29:125--130, 1988.

{\sl{}}

\bibitem[Och79]{och79}
E.~Ochma{\'n}ski.
\newblock Petri nets and concurrent grammars (in polish).
\newblock Technical Report 233/CYF/79, 1979.


\bibitem[Och81]{och81}
E.~Ochma{\'n}ski.
\newblock Automatic construction of concurrent programs (in polish).
\newblock Technical Report 130/CYF/81, 1981.


\bibitem[Och84]{och84}
E.~Ochma{\'n}ski.
\newblock {\em Regular trace languages (in Polish)}.
\newblock PhD thesis, Warszawa, 1984.


\bibitem[Och85]{och85}
E.~Ochma{\'n}ski.
\newblock Regular behaviour of concurrent systems.
\newblock {\em Bulletin of the European Association for Theoretical Computer
  Science (EATCS)}, 27:56--67, Oct 1985.

{\sl{}}

\bibitem[Och88a]{och88apn}
E.~Ochma{\'n}ski.
\newblock Occurrence traces -- processes of elementary net systems.
\newblock In {\em Advances in Petri Nets 88}, number 340 in Lecture Notes in
  Computer Science, pages 331--342, Berlin-Heidelberg-New York, 1988. Springer.


\bibitem[Och88b]{och88stacs}
E.~Ochma{\'n}ski.
\newblock On morphisms of trace monoids.
\newblock In {\em STACS'88 Proceedings}, number 294 in Lecture Notes in
  Computer Science, pages 346--355, Berlin-Heidelberg-New York, 1988. Springer.


\bibitem[Och89]{och89}
E.~Ochma{\'n}ski.
\newblock Semi-commutationes for {P}lace/{T}ransition {S}ystems.
\newblock {\em Bulletin of the European Association for Theoretical Computer
  Science (EATCS)}, 38:191--198, 1989.

{\sl{}}

\bibitem[Och90]{och90}
E.~Ochma{\'n}ski.
\newblock Semi-{C}ommutation and {P}etri {N}ets.
\newblock In V.~Diekert, editor, {\em Proceedings of the {ASMICS} workshop
  {F}ree {P}artially {C}ommutative {M}onoids, {K}ochel am {S}ee 1989}, {R}eport
  {TUM-I9002}, {T}echnical {U}niversity of {M}unich, pages 151--166, 1990.

{\sl{}}

\bibitem[Och92]{och92}
E.~Ochma{\'n}ski.
\newblock Modelling concurrency with semi-commutations.
\newblock In I.~M. Havel and V.~Koubek, editors, {\em Proceedings of the 17th
  Symposium on Mathematical Foundations of Computer Science (MFCS'92), Prague,
  (Czechoslovakia), 1992}, number 629 in Lecture Notes in Computer Science,
  pages 412--420, Berlin-Heidelberg-New York, 1992. Springer.

{\sl{}}

\bibitem[OW91]{ow91}
F.~Otto and C.~Wrathall.
\newblock Overlaps in free partially commutative monoids.
\newblock {\em Journal of Computer and System Sciences}, 42:186--198, 1991.

{\sl{}}

\bibitem[OW93]{ow93}
E.~Ochma{\'n}ski and P.A. Wacrenier.
\newblock On regular compatibility of semi-commutations.
\newblock To appear in ICALP'93 proceedings, 1993.

\bibitem[Par88]{par88}
R.~Parikh.
\newblock Decidability and undecidability in distributed transition systems.
\newblock {\em A perspective in Theoretical Computer Science}, 16, 1988.

{\sl{}}

\bibitem[P{\'e}c81]{pec81}
J.P. P{\'e}cuchet.
\newblock Sur la d\'etermination du rang d'une \'equation dans le mono{\^\i}de
  libre.
\newblock {\em Theoretical Computer Science}, 16:337--340, 1981.

{\sl{}}

\bibitem[Pel87]{pel87}
D.~Peled.
\newblock Interleaving set temporal logic.
\newblock Master thesis, Technion, Israel, 1987.

{\sl{}}

\bibitem[Pel93]{pel93}
D.~Peled.
\newblock All from one, one from all: on model checking using representatives.
\newblock In {\em Proc. of 5th International Conference on Computer Aided
  Verification, Grece}, number 697 in Lecture Notes in Computer Science, pages
  409--423, Berlin-Heidelberg-New York, 1993. Springer.


\bibitem[Pen90]{pen90}
W.~Penczek.
\newblock A concurrent branching time temporal logic.
\newblock In E.~B{\"o}rger, H.~Kleine~B{\"u}ning, and M.M. Richter, editors,
  {\em Proceedings of the 3rd Workshop on Computer Science Logic}, number 440
  in Lecture Notes in Computer Science, pages 337--354, Berlin-Heidelberg-New
  York, 1990. Springer.

{\sl{}}

\bibitem[Pen92a]{pen92asmics}
W.~Penczek.
\newblock On temporal logics for trace systems.
\newblock In Volker Diekert and Werner Ebinger, editors, {\em {P}roceedings
  {ASMICS} {W}orkshop {I}nfinite {T}races, {T}{\"u}bingen}, Bericht 4/92, pages
  158--204. Universit{\"a}t Stuttgart, Fakult{\"a}t Informatik, 1992.

{\sl{}}

\bibitem[Pen92b]{pen92ipl}
W.~Penczek.
\newblock On undecidability of temporal logics on trace systems.
\newblock {\em Information Processing Letters}, 43:147--153, 1992.

{\sl{}Several propositional temporal logics interpreted on trace systems are
  proved to be undecidable. In particular, these are logics using past or run
  operators and referring to the action names.}

\bibitem[Pen93a]{pen93stacs}
W.~Penczek.
\newblock Axiomatizations of temporal logics on trace systems.
\newblock In P.~Enjalbert, A.~Finkel, and K.~W. Wagner, editors, {\em
  Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer
  Science (STACS'93), W{\"u}rzburg 1993}, number 665 in Lecture Notes in
  Computer Science, pages 452--462, Berlin-Heidelberg-New York, 1993. Springer.

{\sl{}Complete proof systems with $\omega$-rules for several temporal logics
  interpreted on trace systems are given. The discussed temporal logics
  include: Partial Order Logic, Computation Tree Logic with past modalities,
  and an essential subset of Interleaving Set Temporal Logic.}

\bibitem[Pen93b]{pen93ijfcs}
W.~Penczek.
\newblock Temporal logics for trace systems: On automated verification.
\newblock {\em International Journal of Foundations of Computer Science},
  4:31--67, 1993.

{\sl{}An extension of Computation Tree Logic by past modalities interpreted
  over Mazurkiewicz's trace systems is defined. The logic is shown to be
  undecidable. The model checking problem is proved to be $NP$-hard and a one
  exponential time model checking algorithm for the logic is given. Examples of
  model checking serializability and inevitability are provided.}

\bibitem[Per84]{per84report}
D.~Perrin.
\newblock Words over a partially commutative alphabet.
\newblock Tech. {R}ep. {LITP} 84-59, {LITP}, Universit\'e Paris~7 (France),
  1984.
\newblock Also appeared in A. Apostolico, editor, {\em Combinatorial Algorithms
  on Words}, Springer NATO-ASI Series, Vol. F12, p.329-340, 1986.

{\sl{}}

\bibitem[Per89]{per89}
D.~Perrin.
\newblock Partial commutations.
\newblock In {\em Proceedings of the 16th International Colloquium on Automata,
  Languages and Programming (ICALP'89), Stresa (Italy) 1989}, number 372 in
  Lecture Notes in Computer Science, pages 637--651, Berlin-Heidelberg-New
  York, 1989. Springer.

{\sl{}}

\bibitem[Pig]{pi93b}
G.~Pighizzini.
\newblock Synthesis of nondeterministic asynchronous automata.
\newblock In M.~Droste and Y.~Gurevich, editors, {\em Semantics of programming
  languages and model theory}. Gordon and Breach.
\newblock to appear.

{\sl{}An algorithm for constructing nondeterministic asynchronous automata is
  presented.}

\bibitem[Pig89]{pig89}
G.~Pighizzini.
\newblock Asynchronous automata: analysis of a category that admits infinitely
  many minimal objects.
\newblock Technical Report 47/89, Dip. Scienze dell'Informazione,
  Universit{\`a} di Milano, 1989.

{\sl{}}

\bibitem[Pig90]{pig90}
G.~Pighizzini.
\newblock About asynchronous cellular automata.
\newblock Technical Report 76/90, Dip. Scienze dell'Informazione,
  Universit{\`a} di Milano, 1990.

{\sl{}}

\bibitem[Pig92]{pig92}
G.~Pighizzini.
\newblock Asynchronous automata versus asynchronous cellular automata.
\newblock Technical report, Dip. Scienze dell'Informazione, Universit{\`a} di
  Milano, 1992.
\newblock to appear in {\it Theoretical Computer Science}.

{\sl{}Asynchronous automata and asynchronous cellular automata are compared and
  transformations between these models are presented. The problem of the
  existence of the minimum automaton accepting a given trace language is
  studied for both models.}

\bibitem[Pig93a]{pi93a}
G.~Pighizzini.
\newblock {\em Recognizable trace languages and asynchronous automata}.
\newblock PhD thesis, Universit{\`a} di Milano, February 1993.


\bibitem[Pig93b]{pig93}
G.~Pighizzini.
\newblock Synthesis of nondeterministic asynchronous automata.
\newblock In M.~Droste and Y.~Gurevich, editors, {\em Semantics of programming
  languages and model theory}, number~5 in Algebra, Logic and Applications,
  pages 109--126. Gordon and Breach Science Publ., 1993.

{\sl{}A Kleene-like characterization of the class of recognizable trace
  languages is presented. It allows to define a modular algorithm for building
  the asynchronous automaton which recognizes a given trace language.}

\bibitem[PKP91]{pkp91}
D.~Peled, S.~Katz, and A.~Pnueli.
\newblock Specifying and proving serializability in temporal logic.
\newblock In {\em Proceedings of LICS}, page ???, 1991.

{\sl{}}

\bibitem[PP93a]{pp93}
D.~Peled and A.~Pnueli.
\newblock Proving partial order liveness properties.
\newblock {\em Theoretical Computer Science}, 1993.
\newblock A preliminary version appeared in the proceedings of the 17th
  International Colloquium on Automata, Languages and Programming, Warwick
  University, England, July 1990, Lecture Notes in Computer Science 443,
  Springer Verlag, 553-571.

{\sl{}A proof system is presented for Interleaving Set Temporal Logic* that
  enables to prove properties that exploit the full expressive power of the
  logic, i.e., properties that hold for some observations but not for all.}

\bibitem[PP93b]{pp93tr}
D.~Perrin and J.E. Pin.
\newblock Mots {I}nfinis.
\newblock Tech. {R}ep. {LITP} 93.40, Universit\'e Paris~7 (France), 1993.
\newblock Book to appear.

{\sl{}This report contains the first chapters of a book to appear. The first
  two chapters give most results on infinite words concerning automata
  recognizable and rational languages and semigroups. The third chapter is
  devoted to the study of the metric space of infinite words.}

\bibitem[Red63]{red63}
L.~Redei.
\newblock {\em Theorie der endlich erzeugbaren kommutativen Halbgruppen}.
\newblock Number~41 in Hamb. Math. Einzelschr. Physica-Verlag, 1963.

{\sl{}}

\bibitem[Ree58]{ree58}
R.~Ree.
\newblock Lie elements and an algebra associated with shuffles.
\newblock {\em Ann. of Maths.}, 68:210--220, 1958.

{\sl{}}

\bibitem[Rei85]{rei85}
W.~Reisig.
\newblock {\em Petri Nets (an Introduction)}.
\newblock Number~4 in EATCS Monographs on Theoretical Computer Science.
  Springer, Berlin-Heidelberg-New York, 1985.

{\sl{}}

\bibitem[Rei92]{rei92}
K.~Reinhardt.
\newblock \.
\newblock Personnal communication, 1992.

\bibitem[Reu89]{reu89}
C.~Reutenauer.
\newblock {\em Aspects math{\'e}matiques des r{\'e}seaux de {P}etri}.
\newblock Masson, Paris, 1989.

{\sl{}}

\bibitem[Ros82]{ros82}
Joseph~G. Rosenstein.
\newblock {\em Linear orderings}.
\newblock Academic Press, New York, 1982.

{\sl{}}

\bibitem[RS64]{rs59}
M.O. Rabin and D.~Scott.
\newblock Finite automata and their decision problems.
\newblock In E.F. Moore, editor, {\em Sequential Machines: Selected Papers}.
  Addison-Wesley, 1964.

{\sl{}}

\bibitem[RS70]{rs70}
H.~Rasiowa and R.~Sikorski.
\newblock {\em The Mathematics of Metamathematics}.
\newblock PWN, Warszawa, 1970.

{\sl{}}

\bibitem[RW91]{rw91}
Y.~Roos and P.A. Wacrenier.
\newblock Composition of two semi commutations.
\newblock In A.~Tarlecki, editor, {\em Proceedings of the 16th Symposium on
  Mathematical Foundations of Computer Science (MFCS'91), Kazimierz Dolny
  (Poland) 1991}, number 520 in Lecture Notes in Computer Science, pages
  406--414, Berlin-Heidelberg-New York, 1991. Springer.

{\sl{}}

\bibitem[Ryt84]{ryt84}
W.~Rytter.
\newblock Some properties of trace languages.
\newblock {\em Fundamenta Informaticae}, VII:117--127, 1984.

{\sl{}}

\bibitem[Sak87]{sak87}
J.~Sakarovitch.
\newblock On regular trace languages.
\newblock {\em Theoretical Computer Science}, 52:59--75, 1987.

{\sl{}}

\bibitem[Sak90]{sak90}
J.~Sakarovitch.
\newblock {T}he {``Last''} {D}ecision {P}roblem on {R}ational {T}race
  {L}anguages.
\newblock In V.~Diekert, editor, {\em {P}roceedings of a workshop of the
  {ESPRIT} {B}asic {R}esearch {A}ction {N}o 3166: {A}lgebraic and {S}yntactic
  {M}ethods in {C}omputer {S}cience {(ASMICS)}, {K}ochel am {S}ee, {B}avaria,
  {FRG} (1989)}, {R}eport {TUM-I9002}, {T}echnical {U}niversity of {M}unich,
  pages 168--171, 1990.

{\sl{}}

\bibitem[Sak92]{sak92}
J.~Sakarovitch.
\newblock The ''last'' decision problem for rational trace languages.
\newblock In {\em LATIN'92 proceedings}, number 583 in Lecture Notes in
  Computer Science, pages 460--473, 1992.


\bibitem[Sal73]{sal73}
A.~Salomaa.
\newblock {\em Formal Laguages}.
\newblock Academic Press, 1973.


\bibitem[SC82]{sc82}
A.P. Sistla and E.~Clarke.
\newblock The complexity of propositional temporal logic.
\newblock In {\em 14th ACM Symposium on Theory of Computing}, pages 159--167,
  1982.

{\sl{}}

\bibitem[Sch58]{sch58}
M.P. Sch{\"{u}}tzenberger.
\newblock Sur une propri\'et\'e combinatoire des alg\`ebres de {L}ie libres
  pouvant \^etre utilis\'ee dans un probl\`eme de math\'ematiques appliqu\'ees.
\newblock In {\em S\'eminaire Dubreuil-Pisot, Ann\'ee 1958-59}, 1958.

{\sl{}}

\bibitem[Sch65]{sch65}
M.P. Sch{\"{u}}tzenberger.
\newblock On a factorization of free monoids.
\newblock {\em Proc. A.M.S.}, 16:21--24, 1965.

{\sl{}}

\bibitem[Sch90]{sch90}
W.~Schmitt.
\newblock Hopf algebras and identities in free partially commutative monoids.
\newblock {\em Theoretical Computer Science}, 73:335--340, 1990.

{\sl{}The first definition of the shuffle product for traces.}

\bibitem[SDS89]{sds89}
H.~Servatius, C.~Droms, and B.~Servatius.
\newblock Surface subgroups of graph groups.
\newblock {\em Proc. of A.M.S.}, 106(3):573--578, 1989.

{\sl{}}

\bibitem[SDS90]{sds90}
H.~Servatius, C.~Droms, and B.~Servatius.
\newblock The finite basis extension property and graph groups.
\newblock In P.~Latiolais, editor, {\em Topology and combinatorial group
  theory}, volume 1440 of {\em Lecture Notes in Mathematics}. Springer, 1990.

{\sl{}}

\bibitem[Ser89]{ser89}
H.~Servatius.
\newblock Automorphisms of graph groups.
\newblock {\em Journal of Algebra}, 126(1):34--60, 1989.

{\sl{}}

\bibitem[Shi79]{shi79}
M.W. Shields.
\newblock {A}dequate path expressions.
\newblock In G.~Kahn, editor, {\em {P}roceedings {S}emantics of {C}oncurrent
  {C}omputation, Evian (France) 1979}, number~70 in Lecture Notes in Computer
  Science, pages 249--265, Berlin-Heidelberg-New York, 1979. Springer.

{\sl{}}

\bibitem[Sim78]{sim78}
I.~Simon.
\newblock Limited subsets of a free monoid.
\newblock In {\em 19th FOCS Proceedings}, pages 143--150, 1978.


\bibitem[SS78]{ss78}
A.~Salomaa and M.~Soittola.
\newblock {\em Automata theoretic aspects of formal power series}.
\newblock Springer, 1978.

{\sl{}}

\bibitem[Sta89]{sta89}
E.W. Stark.
\newblock Concurrent transition systems.
\newblock {\em Theoretical Computer Science}, 64:221--269, 1989.

{\sl{}}

\bibitem[Thi85]{thi85}
J.Y. Thibon.
\newblock Int\'egrit\'e des alg\`ebres de s\'eries formelles sur un alphabet
  partiellement commutatif libre.
\newblock {\em Theoretical Computer Science}, 41, 1985.

{\sl{}It is proved that the free associative partially commutative algebra on a
  domain is still a domain.}

\bibitem[Tho90a]{tho90handbook}
Wolfgang Thomas.
\newblock Automata on infinite objects.
\newblock In Jan~van Leeuwen, editor, {\em Handbook of Theoretical Computer
  Science}, chapter~4, pages 133--191. Elsevier Science Publishers B. V., 1990.

{\sl{}}

\bibitem[Tho90b]{tho90traces}
Wolfgang Thomas.
\newblock On logical definability of trace languages.
\newblock In V.~Diekert, editor, {\em {P}roceedings of a workshop of the
  {ESPRIT} {B}asic {R}esearch {A}ction {N}o 3166: {A}lgebraic and {S}yntactic
  {M}ethods in {C}omputer {S}cience {(ASMICS)}, {K}ochel am {S}ee, {B}avaria,
  {FRG} (1989)}, {R}eport {TUM-I9002}, {T}echnical {U}niversity of {M}unich,
  pages 172--182, 1990.

{\sl{}}

\bibitem[TZ90]{tz91}
Wolfgang Thomas and Wieslaw Zielonka.
\newblock Logical definability of trace languages.
\newblock unpublished manuscript, 1990.

\bibitem[Var92]{var92}
S.~Varricchio.
\newblock On the decidability of the equivalence problem for partially
  commutative rational power series.
\newblock {\em Theoretical Computer Science}, 99(2):291--299, 1992.

{\sl{}Extending a result due to Harju and Karhum{\"a}ki, it is proved the
  decidability of the equivalence problem for rational power series over free
  partially commutative monoids.}

\bibitem[Vie74]{vie74}
G.~Viennot.
\newblock {\em Alg\`ebres de {L}ie libres et mono{\"{\i}}des libres}.
\newblock Th\`ese d'etat, Universit\'e Paris 7, 1974.

{\sl{}}

\bibitem[Vie78]{vie78}
G.~Viennot.
\newblock {\em Alg\`ebres de {L}ie libres et mono{\"{\i}}des libres}, volume
  691 of {\em Lecture Notes in Mathematics}.
\newblock Springer, 1978.

{\sl{}This lecture note is one of the best references on bases of free Lie
  algebras.}

\bibitem[Vie86]{vie86}
X.G. Viennot.
\newblock Heaps of pieces {I}: Basic definitions and combinatorial lemmas.
\newblock In G.~Labelle et~al., editors, {\em Proceedings Combinatoire
  {\'e}numerative, Montreal, Quebec (Canada) 1985}, number 1234 in Lecture
  Notes in Mathematics, pages 321--350, Berlin-Heidelberg-New York, 1986.
  Springer.

{\sl{}The first presentation of the heap monoid which is a geometric way of
  working with traces.}

\bibitem[VW86]{vw86}
M.Y. Vardi and P.~Wolper.
\newblock An automata-theoretic approach to automatic program verification.
\newblock In {\em Proceedings of LICS}, pages 322--331, 1986.

{\sl{}}

\bibitem[Wac93]{wac93}
P.A. Wacrenier.
\newblock {\em Semi-commutations et reconnaissabilit{\'e}}.
\newblock Th{\`e}se, Universit{\'e} des Sciences et Technologies de Lille
  (France), 1993.

{\sl{}}

\bibitem[WDO92]{wdo92}
C.~Wrathall, V.~Diekert, and F.~Otto.
\newblock One-rule trace-rewriting systems and confluence.
\newblock In I.~M. Havel and V.~Koubek, editors, {\em Proceedings of the 17th
  Symposium on Mathematical Foundations of Computer Science (MFCS'92), Prague,
  (Czechoslovakia), 1992}, number 629 in Lecture Notes in Computer Science,
  pages 511--521, Berlin-Heidelberg-New York, 1992. Springer.
\newblock An extended version to appear in Information and Computation.

{\sl{}}

\bibitem[Wol89]{wol89}
P.~Wolper.
\newblock On the relation of programs and computations to models of temporal
  logic.
\newblock In {\em Proceedings of Temporal Logic in Specification Workshop,
  Altrincham, UK, 1987}, number 398 in Lecture Notes in Computer Science, pages
  75--123, Berlin-Heidelberg-New York, 1989. Springer.


\bibitem[Wra88]{wra88}
C.~Wrathall.
\newblock The word problem for free partially commutative groups.
\newblock {\em Journal Symbolic Computation}, 6:99--104, 1988.

{\sl{}}

\bibitem[Wra89]{wra89}
C.~Wrathall.
\newblock Free partially commutative groups.
\newblock In {\em Proceedings of ``Intern. Symposium on Combinatorial
  Optimization''}, pages 195--216, 1989.

{\sl{}}

\bibitem[Zie87]{zie87}
W.~Zielonka.
\newblock Notes on finite asynchronous automata.
\newblock {\em R.A.I.R.O. --- Informatique {T}h{\'e}orique et Applications},
  21:99--135, 1987.

{\sl{}Finite asynchronous automata are introduced (only automata having such
  that for each action the reading and writing domains are equal are
  considered). It is proved that such automata recognize deterministically
  exactly all recognizable subsets of free partially commutative monoids. A
  subclass of asynchronous automata --- loosly cooperating automata --- is also
  introduced and examined. A special representation of recognizable sets of
  traces is deduced.}

\bibitem[Zie89]{zie89}
W.~Zielonka.
\newblock Safe executions of recognizable trace languages by asynchronous
  automata.
\newblock In A.~R. Mayer et~al., editors, {\em Proceedings Symposium on Logical
  Foundations of Computer Science, Logic at Botik '89, Pereslavl-Zalessky
  (USSR) 1989}, number 363 in Lecture Notes in Computer Science, pages
  278--289, Berlin-Heidelberg-New York, 1989. Springer.

{\sl{}Finite cellular asynchronous automata are introduced. The following
  safety property is examined: an automaton is said to be safe if each
  computation starting at an initial state can be extended to an accepting
  computation. It is shown that while there exist recognizable trace languages
  that cannot be recognized by safe deterministic asynchronous cellular
  automata, all recognizable trace languages can be recognized by safe
  non-deterministic unambiguous automata.}

\end{thebibliography}
