Behavioural Equivalences on Finite-State Systems are PTIME-hard

In: Computing and Informatics, vol. 24, no. 5

Z. Sawa - P. Jančar

Details:

Year, pages: 2005, 513 - 528

Keywords:

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

About article:

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.

How to cite:

ISO 690:

Sawa, Z., Jančar, P. 2005. Behavioural Equivalences on Finite-State Systems are PTIME-hard. In Computing and Informatics, vol. 24, no.5, pp. 513-528. 1335-9150.

APA:

Sawa, Z., Jančar, P. (2005). Behavioural Equivalences on Finite-State Systems are PTIME-hard. Computing and Informatics, 24(5), 513-528. 1335-9150.