Regularity for a large class of context-free processes is decidable | SpringerLink
Skip to main content
Springer Nature Link
Log in

Regularity for a large class of context-free processes is decidable

  • Session 4: Languages and Processes
  • Conference paper
  • First Online:
Automata, Languages and Programming (ICALP 1996)

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

Included in the following conference series:

  • 137 Accesses

Abstract

Regularity of context-free processes has been proved to be decidable for BPA systems by [MM94] and normed context-free processes by [Kru95], In this paper the decidable class of regular context-free processes is enlarged to that of context-free processes over so-called NRD specifications (definition in the paper). Furthermore an upper bound is given for the number of states modulo bisimulation.

Research supported by Esprit BRA 7166 CONCUR 2.

Research supported by the Netherlands Organization for Scientific Research (NWO) under contract SION 612-316-125.

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.

Similar content being viewed by others

References

  1. J. C. M. Baeten, J. A. Bergstra, and J. W. Klop. On the consistency of Koomen's fair abstraction rule. Theoretical Computer Science, 51(1/2):129–176, 1987.

    Article  Google Scholar 

  2. J. C. M. Baeten, J. A. Bergstra, and J. W. Klop. Decidability of Bisimulation Equivalence for Processes generating Context-free Languages. Journal of the ACM, 40(3):653–682, 1993.

    Article  Google Scholar 

  3. O. Burkart, D. Caucal, and B. Steffen. An Elementary Bisimulation Decision Procedure for Arbitrary Context-Free Processes. In MFCS '95, volume 969 of Lecture Notes in Computer Science, pages 423–433. Springer-Verlag, 1995.

    Google Scholar 

  4. Y. Bar-Hillel. Language and Information. Series in Logic. Addison-Wesley, 1964.

    Google Scholar 

  5. D.J.B. Bosscher and A. Ponse. Translating a Process Algebra with Symbolic Data Values to Linear Format. In Uffe H. Engberg, Kim G. Larsen, and Arne Skou, editors, Proceedings of the Workshop on Tools and Algorithms for the Construction and the Analysis of Systems, volume NS-95-2 of BRICS Notes Series, pages 119–130, 1995.

    Google Scholar 

  6. J.C.M. Baeten and W.P. Weijland. Process Algebra. Cambridge Tracts in Theoretical Computer Science 18. Cambridge University Press, 1990.

    Google Scholar 

  7. S. Christensen, H. Hüttel, and C. Stirling. Bisimulation is Decidable for all Context-free Processes. In W.R. Cleaveland, editor, Proceedings of CONCUR 92, volume 630 of Lecture Notes in Computer Science, pages 138–147. Springer-Verlag, 1992.

    Google Scholar 

  8. Y. Hirshfeld and F. Moller. Deciding Equivalences in Simple Process Algebras. In A. Ponse, M. de Rijke, and Y. Venema, editors, Modal Logic and Process Algebra, volume 53 of CSLI Lecture Notes, pages 151–169. CSLI Publications, Stanford, 1995.

    Google Scholar 

  9. Y. Hirshfeld and F. Moller. Decidability Results in Automata and Process Theory. In Logics for Concurrency: Automata vs Structure, Springer Lecture Notes in Computer Science, 1996. To appear. Previously presented as lecture notes at the VIII-th Banff Higher Order Workshop “Theories of Concurrency: Structure vs Automata ” in 1994.

    Google Scholar 

  10. Uno Holmer. Translating Static CCS Agents into Regular Form. PMG report 51, Department of Computer Science, Chalmers University of Technology and the University of Göteborg, 1989.

    Google Scholar 

  11. J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.

    Google Scholar 

  12. A. Kručera. Deciding Regularity in Process Algebras. Technical Report RS-95-52, BRICS (Basic Research in Computer Science, Centre of the Danish National Research Foundation), 1995.

    Google Scholar 

  13. S. Mauw and H. Mulder. Regularity of BPA-Systems is Decidable. In Bengt Jonsson and Joachim Parrow, editors, CONCUR'94: Concurrency Theory, volume 836 of Lecture Notes in Computer Science, pages 34–47. Springer-Verlag, 1994.

    Google Scholar 

  14. E. L. Post. A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society, 52:264–268, 1946.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CWI, P.O. Box 94079, 1090, GB Amsterdam, The Netherlands

    D. J. B. Bosscher & W. O. D. Griffioen

  2. Computing Science Institute, University of Nijmegen, P.O. Box 9010, 6500, GL Nijmegen, The Netherlands

    W. O. D. Griffioen

Authors
  1. D. J. B. Bosscher
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. W. O. D. Griffioen
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Friedhelm Meyer Burkhard Monien

Rights and permissions

Reprints and permissions

Copyright information

© 1996 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bosscher, D.J.B., Griffioen, W.O.D. (1996). Regularity for a large class of context-free processes is decidable. In: Meyer, F., Monien, B. (eds) Automata, Languages and Programming. ICALP 1996. Lecture Notes in Computer Science, vol 1099. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61440-0_127

Download citation

  • DOI: https://doi.org/10.1007/3-540-61440-0_127

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-61440-1

  • Online ISBN: 978-3-540-68580-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation