. "Equivalence Checking of Non-flat Systems Is EXPTIME-hard" . "14"^^ . . "RIV/61989100:27240/03:00008382!RIV/2004/GA0/272404/N" . . "27240" . . "Equivalence Checking of Non-flat Systems Is EXPTIME-hard"@en . . . . "Equivalence Checking of Non-flat Systems Is EXPTIME-hard" . . "[84C9630B4BE7]" . "RIV/61989100:27240/03:00008382" . . "0"^^ . . "1"^^ . "0"^^ . "3-540-40753-7" . . "606130" . . . "equivalence checking, finite-state systems, complexity finite-state systems, complexity"@en . "Proceedings of CONCUR 2003 - Concurrency Theory" . "P(GA201/03/1161), Z(MSM 272400013)" . "Sawa, Zden\u011Bk" . . . . "1"^^ . "2003-01-01+01:00"^^ . "Berlin Heidelberg" . "237-250" . "Springer-Verlag. (Berlin; Heidelberg)" . "The equivalence checking of systems that are given as a composition of interacting finite-state systems is considered. It is shown that the problem is EXPTIME-hard for any notion of equivalence that lies between bisimulation equivalence and trace equivalence, as conjectured by Rabinovich (1997). The result is proved for parallel composition of finite-state systems where hiding of actions is allowed, and for 1-safe Petri nets. The technique of the proof allows to extend this result easily to other types of `non-flat' systems."@en . "Equivalence Checking of Non-flat Systems Is EXPTIME-hard"@en . . . "The equivalence checking of systems that are given as a composition of interacting finite-state systems is considered. It is shown that the problem is EXPTIME-hard for any notion of equivalence that lies between bisimulation equivalence and trace equivalence, as conjectured by Rabinovich (1997). The result is proved for parallel composition of finite-state systems where hiding of actions is allowed, and for 1-safe Petri nets. The technique of the proof allows to extend this result easily to other types of `non-flat' systems." . "Universite de Provence and Laboratoire d'Informa" . .