Probabilistic asynchronous automata

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