Notes on finite asynchronous automata. (English) Zbl 0623.68055

Let \(\Sigma\) be a finite alphabet and \(I\subset \Sigma \times \Sigma\) an irreflexive relation. Intuitively (a,b)\(\in I\) denotes that the actions a, b can be executed simultaneously. Let \(\sim\) be the minimal congruence relation over \(\Sigma^*\) created by \(\{\) ab\(\equiv ba|\) (a,b)\(\in I\}\). The free partially commutative monoid E(\(\Sigma\),I) is a quotient of \(\Sigma^*\) by \(\sim\). As it was shown by A. Mazurkiewicz [Concurrent program schemes and their interpretations, DAIMI-PB-78, Aarhus University (1977)] elements of E(\(\Sigma\),I), called traces, model in a natural way executions in concurrent systems. The trace language \(T\subset E(\Sigma,I)\) is called regular if the language UT is regular. In the paper the notion of a finite asynchronous automaton is introduced. Such an automaton is a tuple \({\mathbb{A}}=({\mathbb{P}}_ 1,...,{\mathbb{P}}_ u,\Delta,{\mathbb{F}})\), where \({\mathbb{P}}_ i=(\Sigma_ i,S_ i,s^ 0_ i)\) is an ith process, \(\Sigma_ i\) is an alphabet of \({\mathbb{P}}_ i\), \(S_ i\) is a finite and nonempty set of states of \({\mathbb{P}}_ i\), \(s^ 0_ i\in S_ i\) is an initial state. \({\mathbb{F}}\subset S=\times^{n}_{i=1}S_ i\) the family of final states.
Let \(Dom(a)=\{i\in \Pr oc:\) \(a\in \Sigma_ i\}\) for \(a\in \Sigma =\cup^{n}_{i=1}\Sigma_ i\). Then, \(\Delta =\{\delta_ a:\) \(a\in \Sigma \}\) is the family of the next-state functions \[ \forall a\in \Sigma,\quad \delta_ a:\times_{i\in Dom(a)}S_ i\quad \to \quad {\mathcal P}(\times_{i\in Dom(a)}S_ i). \] Let \((s_ 1',...,s_ n')\), \((s_ 1'',...,s_ n'')\in \times^{n}_{i=1}S_ i\), \(a\in \Sigma\). Then \((s_ 1',...,s_ n')\Rightarrow^{a}(s_ 1'',...,s_ n'')\) iff \((s_ i''=s_ i')\) for \(i\not\in Dom(a)\) and \((s''_{i_ 1},...,s''_{i_ k})\in \delta_ a(s'_{i_ 1},...,s'_{i_ k})\), where \(Dom(a)=\{i_ 1,...,i_ k\}.\)
This relation is extended in a natural way to traces from \(E(\Sigma,I_{{\mathbb{A}}})\), where \(I_{{\mathbb{A}}}=\{(a,b)\in \Sigma^ 2:\) \(Dom(a)\cap Dom(b)=\emptyset \}\). The main theorem of the paper is as follows: \(T\subset E(\Sigma,I)\) is regular iff there exists a finite asynchronous automaton \({\mathbb{A}}\) such that \(I=I_{{\mathbb{A}}}\), and \(T=T({\mathbb{A}})=\{t\in E(\Sigma,I):\exists s\in {\mathbb{F}}(s^ 0_ 1,...,s^ 0_ n)\Rightarrow^{t}S\}\). As a corollary a new characterization of regular subsets of f.p.c. monoids is given.


68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
Full Text: DOI EuDML


[1] 1. A. BERTONI, M. BRAMBILLA, G. MAURI and N. SABADINI, An Application of the Theory of Tree Partially Commutative Monoids: Asymptotic Densities of Trace Languages, Lecture Notes in Comp. Sci., Vol. 117, 1981, Springer-Verlag, pp. 205-215. Zbl0468.68081 · Zbl 0468.68081
[2] 2. A. BERTONI, G. MAURI and N. SABADINI, A Hierarchy of Regular Trace Languages and Some Combinatorial Applications, 2nd World Conf. on Mathematics at the Service of Men, Las Palmas, 1982. Zbl0512.68056 · Zbl 0512.68056
[3] 3. P. CARTIER and D. FOATA, Problèmes combinatoires de commutation et réarrangements, Lecture Notes in Math., Vol 85, 1969, Springer-Verlag. Zbl0186.30101 MR239978 · Zbl 0186.30101
[4] 4. M. CLERBOUT and M. LATTEUX, Partial Commutations and Faithful Rational Transductions, Theoretical Comp. Science, Vol. 34, 1984, pp. 241-254. Zbl0548.68073 MR773455 · Zbl 0548.68073
[5] 5. R. CORI and Y. METIVIER, Recognizable Subsets of Partially Abelian Monoids, Theoretical Comp. Science, Vol. 35, 1985, pp. 179-189. Zbl0559.20040 MR785150 · Zbl 0559.20040
[6] 6. R. CORI and D. PERRIN, Sur la reconnaissabilité dans les monoïdes partiellement commutatifs libres, R.A.I.R.O. Inform. Théor., Vol. 19, 1985, pp. 21-32. MR795769
[7] 7. C. DUBOC, Commutations dans les monoïdes libres : un cadre théoretique pour l’étude du parallélisme, Thèse de 3e cycle, also Technical Report 86-25, Laboratoire Informatique Théoretique et Programmation, 1986.
[8] 8. C. DUBOC, Mixed Product and Asynchronous Automata (submitted for publication). Zbl0638.68095 · Zbl 0638.68095
[9] 9. S. EILENBERG, Automata, Languages and Machines, Vol. A, 1974, Academic Press. Zbl0317.94045 MR530382 · Zbl 0317.94045
[10] 10. R. JANICKI, Synthesis of Concurrent Schemes, Lecture Notes in Comp. Sc., Vol. 64, 1978, Springer Verlag, pp. 298-307. Zbl0382.68023 MR519848 · Zbl 0382.68023
[11] 11. G. LALLEMENT, Semigroups and Combinatorial Applications, 1979, J. Wiley and Sons, New York. Zbl0421.20025 MR530552 · Zbl 0421.20025
[12] 12. A. MAZURKIEWICZ, Concurrent Program Schemes and Their Interpretations, DAIMI-PB-78, Aarhus University, 1977.
[13] 13. E. OCHMAŃSKI, Regular Behaviour of Concurrent Schemes, E.A.T.C.S. Bulletin, No. 27, October 1985, pp. 56-67.
[14] 14. W. REISIG, Petrinetze. Eine Einführung, 1982, Springer Verlag. Zbl0482.68054 MR694697 · Zbl 0482.68054
[15] 15. M. W. SHIELDS, Non-Sequential Behaviour : 1, Report CSR-120-82, Department of Comp. Science, University of Edinburgh, 1982.
[16] 16. P. H. STARKE, Free Petri Net Languages, Lecture Notes in Comp. Sc., Vol. 64, Springer Verlag, pp. 506-515. Zbl0391.68038 MR519867 · Zbl 0391.68038
[17] 17. A. TARLECKI, Notes on the Implementability of Formal Languages by Concurrent Systems, Institute of Computer Science of Polish Academy of Sciences, Report 481, Warsaw, 1982.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.