Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes

摘要

The fastest known algorithm for checking bisimulation equivalence of normed context-free processes worked in O(n~(13)) time. We give an alternative algorithm working in O(n~8 polylog n) time, As a side effect we improve the best known upper bound for testing equivalence of simple context-free grammars from O(n~7polylog n) to O(n~6polylog n).