[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Probabilistic asynchronous automata

  • Published:
Mathematical systems theory Aims and scope Submit manuscript

Abstract

Asynchronous automata were introduced by W. Zielonka as an algebraic model of distributed systems, showing that the class of trace languages recognizable by automata over free partially commutative monoids coincides with the class of trace languages recognizable by deterministic asynchronous automata. In this paper we extend the notion of asynchronous automata to the probabilistic case. Our main result is a nontrivial generalization to Zielonka's theorem: we prove that the sets of behaviors of probabilistic automata and of probabilistic asynchronous automata coincide in the case of concurrent alphabets with acyclic dependency graphs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A. Arnold. An extension of the notions of traces and of asynchronous automata.RAIRO Inform. Théor., 25:355–393, 1991.

    MATH  Google Scholar 

  2. M. Anselmo and A. Bertoni. Two-way probabilistic automata and rational power series.Theoretical Computer Science-Proceedings of the Fourth Italian Conference, pp. 9–23. World Scientific, Singapore, 1992.

    Google Scholar 

  3. IJ. J. Aalbersberg and G. Rozenberg. Theory of traces.Theoret. Comput. Sci., 60:1–82, 1988.

    Article  MATH  MathSciNet  Google Scholar 

  4. A. Bertoni, G. Mauri, and N. Sabadini. Concurrency and commutativity. Technical Report, University of Milan, 1982. Presented at the 3rd European Workshop on Applications and Theory of Petri Nets, Varenna, 1982.

  5. A. Bertoni, G. Mauri, and N. Sabadini. Membership problem for regular and context-free trace languages.Inform. and Comput., 82:135–150, 1989.

    Article  MATH  MathSciNet  Google Scholar 

  6. D. Bruschi, G. Pighizzini, and N. Sabadini. On the existence of minimum asynchronous automata and on the equivalence problem for unambiguous regular trace languages.Inform. and Comput., 108:262–285, 1994.

    Article  MATH  MathSciNet  Google Scholar 

  7. P. Cartier and M. Foata.Problèmes combinatorics de commutation et rearrangements. Lecture Notes in Mathematics, Vol. 85. Springer-Verlag, Berlin, 1969.

    Google Scholar 

  8. R. Cori and Y. Mètivier. Approximation of a trace, asynchronous automata, and the ordering of events in a distributed system.Proc. 15th ICALP, pp. 147–161. Lecture Notes in Computer Science, Vol. 317. Springer-Verlag, Berlin, 1988.

    Google Scholar 

  9. V. Diekert.Combinatorics on Traces. Lecture Notes in Computer Science, Vol. 454. Springer-Verlag, Berlin, 1990.

    Google Scholar 

  10. V. Diekert and A. Muscholl. Deterministic asynchronous automata for infinite traces.Proc. 10th STACS, pp. 617–628. Lecture Notes in Computer Science, Vol. 665. Springer-Verlag, Berlin, 1993.

    Google Scholar 

  11. P. Gastin and A. Petit. Asynchronous automata for infinite traces.Proc. 19th ICALP, pp. 583–594. Lecture Notes in Computer Science, Vol. 623. Springer-Verlag, Berlin, 1992.

    Google Scholar 

  12. J. Kaneps and R. Freivalds. Running time to recognize nonregular languages by two-way probabilistic automata.Proc. ICALP 91, pp. 174–185. Lecture Notes in Computer Science, Vol. 510. Springer-Verlag, Berlin, 1991.

    Google Scholar 

  13. A. Mazurkiewicz. Concurrent program schemes and their interpretations. Technical Report DAIMI Rep. PB-78, Aarhus University, 1977.

  14. A. Mazurkiewicz. Trace theory. InAdvances in Petri Nets 1986 (W. Brauer, W. Reisig, and G. Rosenberg, eds.), pp. 279–324. Lecture Notes in Computer Science, Vol. 255. Springer-Verlag, Berlin, 1986.

    Google Scholar 

  15. Y. Mètivier. An algorithm for computing asynchronous automata in the case of acyclic noncommutation graphs.Proc. 14th ICALP, pp. 226–236. Lecture Notes in Computer Science, Vol. 267. Springer-Verlag, Berlin, 1987.

    Google Scholar 

  16. A. Paz.Introduction to Probabilistic Automata. Academic Press, New York, 1971.

    MATH  Google Scholar 

  17. D. Perrin. Partial commutations.Proc. 16th ICALP, pp. 637–651. Lecture Notes in Computer Science, Vol. 372. Springer-Verlag, Berlin, 1989.

    Google Scholar 

  18. M. O. Rabin. Probabilistic automata.Inform. and Control, 6:230–245, 1963. Also in E. F. Moore.Sequential Machines. Addison-Wesley, Reading, MA, 1964.

    Article  Google Scholar 

  19. A. Salomaa. Onm-adic probabilistic automata.Inform. and Control, 10:215–219, 1967.

    Article  MATH  MathSciNet  Google Scholar 

  20. W. Zielonka. Notes on finite asynchronous automata.RAIRO Inform. Theor., 21:99–135, 1987.

    MathSciNet  Google Scholar 

  21. W. Zielonka. Asynchronous automata.Proceedings of the Workshop: Free Partially Commutative Monoids, pp. 183–197. Institut für Informatic, Technische Universität, München, TUM-I9002, 1990.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano, Via Comelico 39, 2Q135, Milano, Italy

    S. Jesi, G. Pighizzini & N. Sabadini

Authors
  1. S. Jesi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. G. Pighizzini
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. N. Sabadini
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This research has been supported by European Projects EBRA Nos. 3148 (DEMON), 3166 (ASMICS), and 6317 (ASMICS2), by MURST 40%, and by the CNR Project “Modelli di Computazione Parallela.”

Rights and permissions

Reprints and permissions

About this article

Cite this article

Jesi, S., Pighizzini, G. & Sabadini, N. Probabilistic asynchronous automata. Math. Systems Theory 29, 5–31 (1996). https://doi.org/10.1007/BF01201811

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01201811

Keywords

Search

Navigation