A simple realization of a parallel device recognizing regular trace languages

ABSTRACT

This paper studies parallel devices recognizing trace languages. We introduce a concept of an asynchronous automaton with &egr;-moves and show that for a given regularly defined trace language there exists a simple version of an asynchronous automaton with &egr;-moves recognizing this language.

REFERENCES

• Cho86: C. Choffrut. Free partially eonunutative monoids. Universites Paris VI at VII 86.20. 1986.
• CF69: P. Cartier, D. Foata. Problemes combinatoires de commutation et rearrangements. Lect. Notes in Mathematics 85 (1969), Springer.
• CM87: R. Cori, Y. Metivier. Approximation d'une trace, automates asynchronous et ordre des evenements darts les systems repartis. Universite de Bordeaux I, No. 1-8708 (1987).
• Jan88: Ryszard Janicki, How to relieve a programmer from synchronization details, Proceedings of the 1988 ACM sixteenth annual conference on Computer science, p.438-446, February 1988, Atlanta, Georgia, United States [doi>10.1145/322609.322790]
• Jan85: R. Janieki. Transforming Sequential Systems into Concurrent Systems. Theoretical Computer Science 36 (1985),.
• Jan81: R. Janicki. On the Design of Concurrent Systems. Proc. 2nd. Conf, on Distributed Computing Systems. Paris, 1981. IEEE Press, New York, 1981, pp.455-466.
• JLKD85: R Janicki , P E Lauer , M Kounty , R Devillers, Concurrent and maximally concurrent evolution of nonsequential systems, Theoretical Computer Science, v.43 n.2-3, p.213-238, July 1986
• JL89: Ryszard Janicki , P. E. Lauer , W. Brauer , Grzegorz Rozenberg , Arto Salomaa, Specification and Analysis of Concurrent Systems: The COSY Approach, Springer-Verlag New York, Inc., Secaucus, NJ, 1992
• JM89a: Ryszard Janicki , Tomasz Müldner, Transformations of sequential specifications into concurrent specifications by synchronization guards, Conference proceedings on Algebraic methodology and software technology, p.97-129, May 1989, Iowa City, Iowa, United States
• JM89b: R. Janicki , T. Muldner, Complete sequential specification allows for concurrent execution, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.221-231, February 21-23, 1989, Louisville, Kentucky [doi>10.1145/75427.75455]
• Lal79: Gerard Lallement, Semigroups and Combinatorial Applications, John Wiley & Sons, Inc., New York, NY, 1979
• Maz77: A. Mazurkiewiez.. Concurrent Program Schema and Their Interpretations. Report Daimi.PB-78 Aarlaus University, 1977.
• Maz86: Antoni W. Mazurkiewicz, Trace Theory, Proceedings of an Advanced Course on Petri Nets: Central Models and Their Properties, Advances in Petri Nets 1986-Part II, p.279-324, September 08-19, 1986
• Met87: Y. Métivier, An algorithm for computing asynchronous automata in the case of acyclic non-commutation graphs, 14th International Colloquium on Automata, languages and programming, p.226-236, July 1987, Karlsruhe, Germany
• Rei85: W. Reisig, Petri Nets. Springer, 1985.
• Roz88: I. J. Aalbersberg, Theory of traces, Theoretical Computer Science, v.60 n.1, p.1-82, Sept., 1988 [doi>10.1016/0304-3975(88)90051-5]
• Shi79: M. W. Shields, Adequate Path Expressions, Proceedings of the International Sympoisum on Semantics of Concurrent Computation, p.249-265, July 02-04, 1979
• Zie89: Wieslaw Zielonka, Safe Executions of Recognizable Trace Languages by Asynchronous Automata, Proceedings of the Symposium on Logical Foundations of Computer Science: Logic at Botik '89, p.278-289, July 03-08, 1989
• Zie87: W. Zielonka. Notes on Finite Asynchronous Automata. In~or. Theor. etAppl. Vol. 21 N. 2.. pp. 99-135. (1987)
• Zie84: W. Zielonka. Mathematical Model of Co-operating Concurrent Processes. Ph.D. Thesis, Warsaw Technical University, Warsaw, Poland, 1984.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Languages, Theory