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.