Faculty of Informatics logo (Un)decidable Problems in Process Algebras
- - - - -
Funding: Grant Agency of Czech Republic, Project No. 201/98/P046
Starting Date: January 1, 1998
Duration: 3 years
Project Leader: A. Kucera (FI)
- - - - -
Description The aim of the project is to examine decidability issues for various classes of infinite-state processes (Petri nets, process algebras like BPA, BPP, and PA, etc.). The main research priorities can be summarised as follows:
  • the exact comparison of the expressive power of various models, characterization of the `semantical intersection'
  • decidability of behavioural equivalences and preorders for infinite-state systems
  • regularity of processes (in a broader sense), effective constructibility of finite representation and characterisation of infinite-state behaviours
  • effective parallezation of certain classes of (normed) processes
This project is a continuation and extension of the project 201/97/0456.
- - - - -
Contact A. Kucera
- - - - -
Publications

Journals

  • Kucera A.: Effective Decomposability of Sequential Behaviours. Theoretical Computer Science, 242(1-2):71-89. Elsevier Science, 2000.
  • Kucera A.: Regularity of Normed PA Processes. Information Processing Letters, 72(1-2):9-17. Elsevier Science, 1999.
  • Kucera A.: On Finite Representations of Infinite-State Behaviours. Information Processing Letters, 70(1):23-30. Elsevier, 1999.
  • Cerna I., Kretinsky M. and Kucera A.: Comparing Expressibility of Normed BPA and Normed BPP Processes. Acta Informatica, 36(3):233-256. Springer, 1999.
  • Jancar P., Kucera A.: Bisimilarity of Processes with Finite-State Systems. Electronic Notes of Theoretical Computer Science, Vol.9. Elsevier, 1997.

Conference proceedings

  • Kucera A.: Efficient Verification Algorithms for One-Counter Processes. In Proc. of ICALP 2000, Geneva, Switzerland, pages 317-328, volume 1853 of LNCS, Springer, July 2000.
  • Jancar P., Kucera A. and Moller F.: Simulation and Bisimulation over One-Counter Processes. In Proc. of STACS 2000, Lille, France, pages 334-345, volume 1770 of LNCS, Springer, February 2000.
  • Kucera A. and Mayr R.: Weak Bisimilarity with Infinite-State Systems can be Decided in Polynomial Time. In Proc. of CONCUR'99, Eindhoven, The Netherlands, pages 368-382, volume 1664 of LNCS, Springer, August 1999 (also available as a technical report TUM-I9830, Technische Universitat Munchen, 1998).
  • Kucera A. and Mayr R.: Deciding Simulation Preorder on Simple Process Algebras. In Proc. of ICALP'99, Prague, Czech Republic, pages 503-512, volume 1644 of LNCS, Springer, July 1998 (also available as a technical report TUM-I9902, Technische Universitat Munchen, 1999).
  • Jancar P., Kucera A. and Mayr R.: Deciding Bisimulation-Like Equivalences with Finite-State Processes. In Proc. of ICALP'98, Aalborg, Danemark, pages 200-211, volume 1443 of LNCS, Springer, July 1998 (also available as a technical report TUM-I9805, Technische Universitat Munchen, 1998).
  • Kucera A.: On finite representations of infinite-state behaviours; in Proc. SOFSEM'97, Milovy, Czech Rep., November 1997, Lecture Notes in Computer Science, Vol. 1338, Springer 1997, pp. 481--488.
  • Kucera A.: How to parallelize sequential processes; in Proc. CONCUR'97, Warsaw, Poland, July 1997, Lecture Notes in Computer Science, Vol. 1243, Springer 1997, pp. 302--316.

Accepted for publication

  • Jancar P., Kucera A. and Mayr R.: Deciding Bisimulation-Like Equivalences with Finite-State Processes; to appear in Theoretical Computer Science, Elsevier Science.
- - - - -
- - - - -
webmaster@informatics.muni.cz