Behavioural Equivalences on Finite-State Systems are PTIME-hard
Keywords:
Verification, finite transition systems, bisimulation equivalence, trace equivalence, computational complexity, PTIME-hardnessAbstract
The paper shows a LOGSPACE-reduction from the Boolean circuit value problem which demonstrates that any relation subsuming bisimilarity and being subsumed by trace preorder (ie, language inclusion) is PTIME-hard, even for finite acyclic labelled transition systems. This reproves and substantially extends the result of Balcazar, Gabarro and Santha (1992) for bisimilarity.Downloads
Download data is not yet available.
Downloads
Published
2012-02-06
How to Cite
Sawa, Z., & Jančar, P. (2012). Behavioural Equivalences on Finite-State Systems are PTIME-hard. Computing and Informatics, 24(5), 513–528. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/397
Issue
Section
Articles