Behavioural Equivalences on Finite-State Systems are PTIME-hard

Zdeněk Sawa; Petr Jančar

Behavioural Equivalences on Finite-State Systems are PTIME-hard

Authors

Zdeněk Sawa
Petr Jančar

Keywords:

Verification, finite transition systems, bisimulation equivalence, trace equivalence, computational complexity, PTIME-hardness

Abstract

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 http://147.213.75.17/ojs/index.php/cai/article/view/397