Deciding bisimulation and trace equivalences for systems with many identical processes | Zendy

HsuChun Yen | Zendy; Shi-Tsuen Jian | Zendy; Ta-Pang Lao | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Deciding bisimulation and trace equivalences for systems with many identical processes

Author(s) -

HsuChun Yen,

Shi-Tsuen Jian,

Ta-Pang Lao

Publication year - 1995

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

DOI - 10.1007/bfb0015435

Subject(s) - bisimulation , decidability , undecidable problem , trace (psycholinguistics) , computer science , process calculus , concurrency , p , pspace , model checking , theoretical computer science , inter process communication , pi calculus , equivalence (formal languages) , distributed computing , programming language , time complexity , discrete mathematics , algorithm , computational complexity theory , mathematics , linguistics , philosophy

In this paper, we study the complexity and decidability issues of checking trace and bisimulation equivalences for the model of systems with many identical processes with respect to various interprocess communication structures. In our model, each system consists of an arbitrary number of identical finite state processes using Milner's Calculus of Communicating Systems (CCS) as the style of interprocess communication. As it turns out, checking trace and bisimulation equivalences are undecidable for star-like and linear systems, whereas the two problems are complete for PSPACE and PTIME, respectively, for fully connected systems.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research