Behavioural Equivalences on Finite-State Systems are PTIME-hard

Zdeněk Sawa; Petr Jančar

Abstract

The paper shows a ŁOGSPACE-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.

Keywords

Cite this article

@article{cai-1208,
  author  = {Zdeněk Sawa and Petr Jančar},
  title   = {Behavioural Equivalences on Finite-State Systems are PTIME-hard},
  journal = {Computing and Informatics},
  volume  = {24},
  number  = {5},
  pages   = {513--528},
  year    = {2005},
  issn    = {1335-9150},
  url     = {https://cai.type.sk/content/2005/5/behavioural-equivalences-on-finite-state-systems-are-ptime-hard/}
}

Download .bib

TY  - JOUR
AU  - Zdeněk Sawa
AU  - Petr Jančar
TI  - Behavioural Equivalences on Finite-State Systems are PTIME-hard
JO  - Computing and Informatics
VL  - 24
IS  - 5
SP  - 513
EP  - 528
PY  - 2005
SN  - 1335-9150
UR  - https://cai.type.sk/content/2005/5/behavioural-equivalences-on-finite-state-systems-are-ptime-hard/
KW  - Verification
KW  - finite transition systems
KW  - bisimulation equivalence
KW  - trace equivalence
KW  - computational complexity
KW  - PTIME-hardness
ER  -

Download .ris

Sawa, Z., & Jančar, P. (2005). Behavioural Equivalences on Finite-State Systems are PTIME-hard. Computing and Informatics, 24(5), 513–528. https://cai.type.sk/content/2005/5/behavioural-equivalences-on-finite-state-systems-are-ptime-hard/

Download .txt