On the existence of the minimum asynchronous automaton and on decision problems for unambiguous regular trace languages | SpringerLink
Skip to main content
Springer Nature Link
Log in

On the existence of the minimum asynchronous automaton and on decision problems for unambiguous regular trace languages

  • Contributed Papers
  • Conference paper
  • First Online:
STACS 88 (STACS 1988)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 294))

Included in the following conference series:

Abstract

In this paper we characterize concurrent alphabets for which every recognizable trace language admits a minimum finite state asynchronous automaton. Furthermore, we consider the equivalence problem for unambiguous regular trace languages, and prove that in some cases it is decidable even if the concurrency relation is not transitive.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. A.Arnold, Le théorème de Zielonka, manuscript, 1986

    Google Scholar 

  2. IJ.J.Aalbersberg, H.J.Hogeboom, Decision problems for regular trace languages, Proc. 14th ICALP, Lect. Not. Comp. Sci.267, pp.251–259, Springer, 1987

    Google Scholar 

  3. IJ.J. Aalbersberg, E. Welzel, Trace languages defined by regular string languages, RAIRO Int. Théor. et Apl., 20, pp.103–119, 1986

    Google Scholar 

  4. IJ.J. Aalbersberg, G. Rozenberg, Theory of traces, Institute of Applied Mathematics and Computer Science, Univerisity of Leiden, Tec.Rep no 86-16, 1986

    Google Scholar 

  5. J. Berstel, J. Sakarovitch, Recent results in the theory of rational sets, Proc.MFCS 86, Lect. Not.Comp.Sci. 233, pp.15–28, 1986

    Google Scholar 

  6. A. Bertoni, M. Brambilla, G. Mauri, N. Sabadini, An application of the theory of free partially commutative monoids: asymptotic densities of trace languages, Proc. 10th Symp. MFCS, Lect. Not. Comp. Sci. 118, pp. 205–215, Springer, 1981

    Google Scholar 

  7. A.Bertoni, G.Mauri, N.Sabadini, A hierarchy of regular trace languages and some combinatorial applications, Proc. II World Conf. on Math. at the Service of Men, Las Palmas, pp. 146–153, 1982

    Google Scholar 

  8. A. Bertoni, G. Mauri, N. Sabadini, Equivalence and membership problems for regular trace languages, Lect. Not. Comp. Sci. 140, pp. 61–71, 1982

    Google Scholar 

  9. A. Bertoni, G. Mauri, N. Sabadini, Unambiguous regular trace languages “Algebra, Comb. and Logic in Computer Science”, Colloquia Math. Soc.J.Bolyai, vbol.42,pp.113–123, North Holland, Amsterdam, 1985

    Google Scholar 

  10. A. Bertoni, G. Mauri, N. Sabadini, Concurrency and commutativity, Workshop on Petri Nets, Varenna, 1982

    Google Scholar 

  11. A. Bertoni, N. Sabadini, Generating functions of trace languages, Int.Rep. Dip. Comp. Sci., Milano, 1986

    Google Scholar 

  12. R. Cori, Y. Métivier, Approximation d'une trace, automates asynchrones et ordre des evenements dans les systems repartis, Université de Bordeaux I, no 1-8708, 1987

    Google Scholar 

  13. R. Cori, D. Perrin, Automates et commutations partielles, RAIRO Inf.Théor. 19, pp.21–32, 1985

    Google Scholar 

  14. C. Duboc, Commutations dans les monoídes libres: une cadre theorique pour l'étude du parallélisme; These du Doctorat, Université of Rouen, 1986

    Google Scholar 

  15. J.A. Goguen, J.W. Thatcher, F.C. Wagner, An initial algebra approach to the specification, correctness and implementation of abstract data types, IBM Res. Rep RC6487, Yorktown Heights, 1976.

    Google Scholar 

  16. E.V. Krishnamurthy, Error-free polynomial matrix computations, Springer-Verlag New York, Berlin, Heidelberg, Tokio, 1985.

    Google Scholar 

  17. G. Lallement, Semigroups and combinatorial applications, Wiley and Sons Ed., New York, 1979

    Google Scholar 

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

    Google Scholar 

  19. A. Mazurkiewicz, Semantics of concurrent systems: a modular fixed point trace approach, Lect. Not. Comp. Sci. 118, pp.353–375, 1985

    Google Scholar 

  20. Y. Métivier, An Algorithm for Computing Asynchronous Automata in the Case of Acyclic Non-Commutation Graphs, Lect. Not. Comp. Sci. 267, pp.226–236, Springer, 1987

    Google Scholar 

  21. J. Sakarovitch, On regular trace languages, to appear in RAIRO Inf. Théor. et Appl.

    Google Scholar 

  22. M. Szijarto, A classification and closure properties of languages for descibing concurrent systems behaviours, Fundamenta Informaticae 4, pp.531–549, 1981

    Google Scholar 

  23. M. Wand, Final algebra semantics and data type extensions, Indiana University Tec. Rep. n' 65, 1979

    Google Scholar 

  24. W. Zielonka, Notes on asynchronous automata, Tec. Rep. Inst.of Math., Warsaw Tec. Univ., Poland, 1984 (to be pubbl. on RAIRO Inf. Theor.)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento Scienze dell'Informazione, via Moretto da Brescia 9, 20133, Milano

    D. Bruschi, G. Pighizzini & N. Sabadini

Authors
  1. D. Bruschi
    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

Editor information

Robert Cori Martin Wirsing

Rights and permissions

Reprints and permissions

Copyright information

© 1988 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bruschi, D., Pighizzini, G., Sabadini, N. (1988). On the existence of the minimum asynchronous automaton and on decision problems for unambiguous regular trace languages. In: Cori, R., Wirsing, M. (eds) STACS 88. STACS 1988. Lecture Notes in Computer Science, vol 294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0035857

Download citation

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

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-18834-6

  • Online ISBN: 978-3-540-48190-4

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation