An Elementary Bisimulation Decision Procedure for Arbitrary Context-Free
Processes
O. Burkart, D. Caucal, B. Steffen
We present an elementary algorithm for deciding bisimulation
equivalence between arbitrary context-free processes. This
improves on the state of the art algorithm of Christensen,
H\"uttel and Stirling consisting of two semi-decision
procedures running in parallel, which prohibits any
complexity estimation. The point of our algorithm is the
effective construction of a finite relation characterizing
all bisimulation equivalence classes, whose mere existence
was exploited for the above mentioned decidability result.