Simple grammar bisimilarity, with an application to session type equivalence

Diogo Poças, Gil Silva, Vasco T. Vasconcelos

We provide an algorithm for deciding simple grammar bisimilarity whose complexity is polynomial in the valuation of the grammar (maximum seminorm among production rules). Since the…