Notes on finite asynchronous automata. (English) Zbl 0623.68055

Zielonka, Wiesław

RAIRO, Inf. Théor. Appl. 21, 99-135 (1987).

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.

MSC:

68Q45	Formal languages and automata
20M35	Semigroups in automata theory, linguistics, etc.

Keywords:

regular language; free partially commutative monoid; traces; trace language; finite asynchronous automaton

References:

[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 · doi:10.1007/3-540-10856-4_86
[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 · doi:10.1007/BFb0079468
[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 · doi:10.1016/0304-3975(84)90053-7
[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 · doi:10.1016/0304-3975(85)90013-1
[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 · doi:10.1016/0304-3975(86)90094-0
[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.