"Jan\u010Dar, Petr" . . . . . "513-528" . "Computing and Informatics" . "5" . "513638" . . "1335-9150" . "RIV/61989100:27240/05:00012189!RIV06-GA0-27240___" . "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 (i.e., language inclusion) is PTIME-hard, even for finite acyclic labelled transition systems. This reproves and substantially extends the result of Balc\u00E1zar, Gabarr\u00F3 and S\u00E1ntha (1992) for bisimilarity."@cs . . . "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 (i.e., language inclusion) is PTIME-hard, even for finite acyclic labelled transition systems. This reproves and substantially extends the result of Balc\u00E1zar, Gabarr\u00F3 and S\u00E1ntha (1992) for bisimilarity." . . "[FC36788DADCC]" . . . "verification; finite transition systems; bisimulation equivalence; trace equivalence; computational complexity; PTIME-hardness"@en . "2"^^ . "Behavioural Equivalences on Finite-State Systems are PTIME-hard"@cs . "Behavioural Equivalences on Finite-State Systems are PTIME-hard" . "RIV/61989100:27240/05:00012189" . . "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 (i.e., language inclusion) is PTIME-hard, even for finite acyclic labelled transition systems. This reproves and substantially extends the result of Balc\u00E1zar, Gabarr\u00F3 and S\u00E1ntha (1992) for bisimilarity."@en . "24" . . . "2"^^ . . . . "Behavioural Equivalences on Finite-State Systems are PTIME-hard"@en . . . . "P(GA201/03/1161)" . "Sawa, Zden\u011Bk" . "Behavioural Equivalences on Finite-State Systems are PTIME-hard"@en . "Behavioural Equivalences on Finite-State Systems are PTIME-hard"@cs . "15"^^ . "Behavioural Equivalences on Finite-State Systems are PTIME-hard" . "SK - Slovensk\u00E1 republika" . "27240" .