|
28th Annual Conference on Current
Trends in
Theory and Practice of Informatics
|
|
November 24 - December 1, 2001
|
|
P-hardness of Equivalence Testing on Finite-State Processes
by Zdenek Sawa and Petr Jancar
Abstract:
The paper shows a simple LOGSPACE reduction from the boolean circuit
value problem which demonstrates that, on finite labelled transition
systems, deciding an arbitrary relation which subsumes bisimulation
equivalence and is subsumed by trace preorder is a polynomial-time-hard
problem (and thus can not be expected to be efficiently parallelizable).
By this, the result of Balcazar, Gabarro and Santha (1992) for
bisimilarity is substantially extended.