Behavioural Equivalences on Finite-State Systems are PTIME-hard
Zdeněk Sawa ; Petr Jančar
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
Text on Computing and Informatics
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.
Publié le : 2012-01-26
Classification:  Verification; finite transition systems; bisimulation equivalence; trace equivalence; computational complexity; PTIME-hardness 
@article{cai397,
     author = {Zden\v ek Sawa and Petr Jan\v car},
     title = {Behavioural Equivalences on Finite-State Systems are PTIME-hard},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai397}
}

Zdeněk Sawa; Petr Jančar. Behavioural Equivalences on Finite-State Systems are PTIME-hard. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai397/