Partial characterization of synchronization languages | SpringerLink
Skip to main content
Springer Nature Link
Log in

Partial characterization of synchronization languages

  • Contributed Papers
  • Conference paper
  • First Online:
Mathematical Foundations of Computer Science 1997 (MFCS 1997)

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

Abstract

Synchronization languages are associated with synchronization expressions, a high-level construct which allows a programmer to express synchronization constraints in a distributed context. We give a negative answer to a conjecture enunciated by L. Guo, K. Salomaa and S. Yu which aims at characterizing synchronization languages in terms of regular languages closed under a rewriting system. Then we propose an extension of the system which gives a positive answer for a class of regular languages.

This work is partially supported by the group MOSYDIS of the PRC-GDR AMI

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. M. Clerbout, M. Latteux, and Y. Roos. Semi-commutations. In V. Diekert and G. Rozenberg, editors, The Book of Traces, chapter 12, pages 487–551. World Scientific, 1995.

    Google Scholar 

  2. R. Cori and D. Perrin. Automates et commutations partielles. R. A.I.R.0. — Theoretical Informatics and Applications, 19:21–32, 1985.

    Google Scholar 

  3. M. Clerbout, Y. Roos, and I. Ryl. Synchronization languages. Theoretical Computer Science. to appear.

    Google Scholar 

  4. R. Govindarajan, L. Guo, S. Yu, and P. Wang. ParC project: Practical constructs for parallel programming languages. In Proc. IEEE of the 15th Annual Internationnal Computer Software & Applications Conference, pages 183–189, 1991.

    Google Scholar 

  5. L. Guo, K. Salomaa, and S. Yu. Synchronization expressions and languages. In Proc. of the 6th Symposium on Parallel and Distributed Processing, pages 257–264, 1994.

    Google Scholar 

  6. L. Guo, K. Salomaa, and S. Yu. On synchronization languages. Fundamenta Informaticae, 25:423–436, 1996.

    Google Scholar 

  7. Y. Métivier. Contribution `a l'étude des monoïdes de commutations. PhD thesis, Université de Bordeaux I, 1988.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. C.N.R.S. U.A. 369, L.I.F.L. Université de Lille I Bât. M3, Cité Scientifique, 59655, Villeneuve d'Ascq Cedex, France

    Isabelle Ryl, Yves Roos & Mireille Clerbout

Authors
  1. Isabelle Ryl
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yves Roos
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mireille Clerbout
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Igor Prívara Peter Ružička

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ryl, I., Roos, Y., Clerbout, M. (1997). Partial characterization of synchronization languages. In: Prívara, I., Ružička, P. (eds) Mathematical Foundations of Computer Science 1997. MFCS 1997. Lecture Notes in Computer Science, vol 1295. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0029964

Download citation

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

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-63437-9

  • Online ISBN: 978-3-540-69547-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation