💻 computer science

Simple grammar bisimilarity, with an application to session type equivalence

This paper presents a single-exponential time algorithm for deciding simple grammar bisimilarity based on grammar valuation and applies it to achieve the first polynomial-time decision procedure for context-free session type equivalence.

Original authors: Diogo Poças, Gil Silva, Vasco T. Vasconcelos

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Diogo Poças, Gil Silva, Vasco T. Vasconcelos

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Checking if Two Machines are "Twins"

Imagine you have two complex machines (like robots or computer programs). You want to know if they are equivalent. Do they behave exactly the same way? If you press a button on Machine A, does Machine B do the exact same thing? If Machine A gets stuck, does Machine B get stuck too?

In computer science, this is called the Bisimilarity problem. It's like checking if two actors are perfect twins: they must react to every possible input in the exact same way, step-by-step.

This paper focuses on a specific type of machine called a Simple Grammar. Think of these as machines that follow a strict set of rules to generate sentences or perform actions. The authors created a new, much faster way to check if two of these machines are twins.

The Problem: The Old Way Was Too Slow

Before this paper, if you wanted to check if two complex machines were twins, the computer had to try a massive number of possibilities.

The Old Method: Imagine trying to find a specific grain of sand on every beach on Earth, one by one. It was so slow that for large machines, the computer would run out of time before finding the answer. The old method was "double-exponential," meaning the time it took grew so fast it was practically impossible for big problems.
The New Method: The authors found a shortcut. Their new algorithm is "single-exponential." It's still fast enough to be tricky for huge machines, but it's a massive improvement—like switching from searching every beach on Earth to just searching the local park.

The Secret Weapon: The "Basis-Updating" Algorithm

How did they make it faster? They invented a method they call the Basis-Updating Algorithm.

Imagine you are trying to prove two people are twins. You start with a small list of things you know for sure (e.g., "They both have blue eyes"). This is your Basis.

The Guess: You look at the two machines. You guess, "Maybe they are the same." You add this guess to your list.
The Test: You press a button on both.
- If they do the same thing, you check what happens next. You add that new state to your list.
- If they do different things, you know immediately: They are not twins. You stop and say "NO."
The Update: If you find a mismatch later in the process, you don't give up entirely. You go back to your list, erase the wrong guess, and try a different one. Maybe they aren't identical twins, but maybe they are cousins who behave similarly in specific ways? You update your list (the "Basis") to reflect this new understanding.

The magic of their algorithm is that it is very smart about when to stop guessing and how to update the list. It avoids getting stuck in loops and ensures it doesn't waste time checking things it already knows are wrong.

The Real-World Application: Session Types

Why does this matter? The paper connects this math problem to Session Types.

What is a Session Type?
Think of a Session Type as a script for a conversation.

Client: "I want to buy a coffee."
Server: "Okay, do you want milk or sugar?"
Client: "Sugar."
Server: "Here is your coffee."

In computer programming, these scripts ensure that two programs talking to each other don't get confused (e.g., the server doesn't try to send a coffee before the client asks for it).

The Problem:
Sometimes, programmers write these scripts in a very complex, recursive way (like a story that tells itself over and over). Checking if two different scripts do the exact same thing is hard.

The Solution:
The authors showed that these complex conversation scripts can be turned into the "Simple Grammar" machines mentioned earlier. Because they built a fast algorithm to check if those machines are twins, they now have the first fast way to check if two complex conversation scripts are equivalent.

Before: Checking if two complex scripts were the same might take a computer days or years.
Now: It takes seconds or minutes.

The Results: A Speed Test

The authors didn't just write the math; they built a computer program to test it.

They compared their new method against the old, slow method.
The Result: Their new method was significantly faster. In many cases, the old method gave up (timed out) after 30 seconds, while the new method solved the problem instantly.
The Data: They tested 1,000 pairs of conversation scripts. The new method solved all of them. The old method failed on 18% of them.

Summary

The Goal: Check if two complex, rule-based systems behave exactly the same.
The Breakthrough: A new "Basis-Updating" algorithm that is much faster than previous methods (single-exponential vs. double-exponential).
The Application: It allows computers to quickly verify that complex communication protocols (Session Types) are equivalent, which is crucial for building reliable software.
The Future: While this is a huge improvement, the authors admit they haven't found a "polynomial" (super-fast) solution yet. The problem is still hard, but they made it much more manageable.

In short: They found a smarter way to check if two complex robots are twins, which helps programmers ensure their software conversations never go wrong.

Technical Summary: Simple Grammar Bisimilarity and Session Type Equivalence

Problem Statement

The paper addresses the simple grammar bisimilarity problem: given a simple grammar (a deterministic context-free grammar in Greibach normal form) and two words of nonterminals, determine if they are bisimilar. Bisimilarity is a fine-grained equivalence notion based on behavior, distinct from language equivalence (which is undecidable for context-free grammars).

While bisimilarity for general context-free grammars (BPA processes) is known to be decidable, the exact complexity remains open, lying between EXPTIME and 2-EXPTIME. The best-known algorithm for general context-free grammars runs in double-exponential time ( $2^{2^{O(n)}}$ ). Since simple grammars are a deterministic subset, the authors investigate whether a more efficient algorithm exists for this specific class.

A primary motivation for this work is the equivalence problem for context-free session types. Session types describe structured communication protocols. While regular session types suffice for many applications, extensions allowing context-free recursion (beyond tail recursion) are necessary for complex protocols. Determining the equivalence of two context-free session types is a critical subroutine in compiler design for languages like FreeST. This problem directly translates to the simple grammar bisimilarity problem.

Methodology

The authors propose a novel algorithm called the basis-updating algorithm. The methodology relies on several key theoretical constructs:

Norms and Valuation:
- Norm ( $\|\gamma\|$ ): The length of the shortest sequence of transitions leading to the empty word.
- Seminorm ( $s(\gamma)$ ): The norm of the maximal normed prefix of $\gamma$ .
- Valuation ( $v$ ): The maximum seminorm among all right-hand sides of production rules in the grammar. The paper notes that valuation is at most exponential in the size of the grammar.
Characterization of Solutions:
The algorithm relies on characterizing solutions to equations of the form $X\alpha \sim Y\beta$ . The authors establish that for simple grammars, solutions are unique up to bisimilarity in specific cases (e.g., when $X$ and $Y$ are normed). This uniqueness is a critical departure from general context-free grammars, where multiple non-bisimilar solutions may exist.
Coinductive Congruence:
Instead of using the "least congruence" (which is only semi-decidable), the authors define coinductive congruence ( $\equiv^c_B$ ) relative to a finite basis $B$ . A basis is a finite set of pairs of nonterminals (or words) that serves as a hypothesis for the bisimulation relation.
- A basis is self-bisimulation if it satisfies specific transition-matching conditions.
- Theorem 4.6 proves that for every simple grammar, there exists a basis $B$ such that coinductive congruence coincides with bisimilarity.
The Basis-Updating Algorithm:
The algorithm constructs a derivation tree to check if two input words are bisimilar. It maintains a basis $B$ and a set $S$ of "irreducible" pairs.
- Initialization: $B$ starts with reflexive pairs $(X, X)$ .
- Expansion: The algorithm explores the derivation tree. When it encounters a pair $(X\alpha, Y\beta)$ $(X α, Y β)$ not covered by $B$ $B$ , it attempts to "guess" a rule:
  - BPA1 Guess: Assumes $X \sim Y\beta$ (reducible).
  - BPA2 Guess: Assumes $X\alpha \sim Y\beta$ (irreducible but comparable).
- Updating: If a guess fails (e.g., transitions do not match or a partial failure occurs), the algorithm backtracks. It removes the failed guess from $B$ , adds the pair to the irreducible set $S$ , and updates $B$ with a new pair (often switching from a BPA1 guess to a BPA2 guess).
- Termination: The process continues until all leaves are finished (returning 'YES') or a total failure is detected (returning 'NO').

Key Contributions

Polynomial-Time Algorithm for Session Types: The paper presents the first polynomial-time algorithm for deciding the equivalence of context-free session types. This is achieved by converting session types to simple grammars with a valuation linear in the size of the type, and then applying the basis-updating algorithm.
Single-Exponential Complexity for Simple Grammars: The basis-updating algorithm decides simple grammar bisimilarity in time polynomial in the grammar size, the valuation, and the seminorms of the input words. Since the valuation is at most exponential in the grammar size, the overall complexity is single-exponential ( $2^{O(n)}$ ). This improves upon the previous double-exponential bound known for general context-free grammars.
Theoretical Characterization: The authors provide a rigorous characterization of solutions to bisimilarity equations for simple grammars (Lemmas 3.3–3.5), proving the uniqueness of solutions in specific cases, which is essential for the algorithm's correctness and efficiency.
Coinductive Congruence Framework: The paper introduces and formalizes the notion of coinductive congruence as a decidable relation under mild assumptions, offering a new tool for analyzing infinite-state systems.

Results

Theoretical Bounds: The time complexity of the basis-updating algorithm is $O(n^{12} d^2 v^2)$ , where $n$ is the number of nonterminals, $d$ is the maximum degree (transitions per nonterminal), and $v$ is the valuation.
Experimental Validation: The authors implemented the algorithm in Haskell and compared it against the existing 2-EXPTIME implementation used in the FreeST programming language (based on Almeida et al. [AMV20]).
- Timeouts: On a sample of 1,000 type pairs, the previous algorithm timed out on 181 cases (18% of the sample), whereas the new algorithm timed out on zero cases.
- Performance: The new algorithm outperformed the previous one in 64% of cases, with significant speedups. The empirical average-case complexity was found to be roughly $O(x^{1.53})$ (where $x$ is input size), significantly lower than the theoretical worst-case bound, suggesting the worst-case inputs are rare.
- Scalability: The new algorithm demonstrated polynomial growth in runtime relative to input size, while the previous algorithm showed signs of super-polynomial (exponential) growth.

Significance and Claims

The paper claims to provide a practical and theoretically superior solution to the context-free session type equivalence problem. By reducing the complexity from double-exponential to single-exponential (and empirically polynomial), the work enables more efficient type checking in compilers for languages supporting context-free session types.

The authors are modest regarding the theoretical limits:

They acknowledge that the exact complexity of simple grammar bisimilarity remains open; it is not yet proven to be in P (polynomial time).
The exponential factor in their complexity analysis arises from the valuation of the grammar and the number of nodes generated during the coinductive congruence check.
They explicitly state that extending these techniques to general context-free grammars (non-deterministic) is non-trivial because the uniqueness results for solutions do not hold in the general case, potentially leading to exponentially many non-bisimilar solutions.

In conclusion, the paper establishes a new state-of-the-art for simple grammar bisimilarity and context-free session type equivalence, offering a concrete algorithm that is both theoretically sound and empirically efficient, while leaving the question of a fully polynomial-time solution for the general case as an open research direction.