The bisimulation problem for equational graphs of finite out-degree
The bisimulation problem for equational graphs of finite out-degree is shown to be decidable. We reduce this problem to the eta-bisimulation problem for deterministic rational (vectors of) boolean series on the alphabet of a deterministic pushdown automaton M. We then exhibit a complete formal system for deducing equivalent pairs of such vectors.
bisimulation equational graphs complete formal systems deterministic pushdown automata rational languages finite dimensional vector spaces matrix semigroups