💻 computer science

On Complexity Bounds and Confluence of Parallel Term Rewriting

This paper introduces automatic techniques for deriving upper and lower bounds on the parallel complexity of parallel-innermost term rewriting by leveraging sequential complexity methods and establishing sufficient criteria for confluence, a framework validated through the extension of the AProVE tool and extensive benchmark experiments.

Original authors: Thaïs Baudon, Carsten Fuhs, Laure Gonnord

Published 2026-04-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Thaïs Baudon, Carsten Fuhs, Laure Gonnord

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

Imagine you are the manager of a massive, chaotic kitchen. Your goal is to prepare a complex meal (a computation) using a specific recipe book (a Term Rewrite System). In the old days, you had a single chef who followed the recipe step-by-step, one instruction at a time. This is sequential computing.

But now, you have a kitchen with hundreds of chefs (parallel computing). The question is: How much faster can we cook if everyone works at the same time? And more importantly, how do we know if the meal will actually taste the same no matter which chef grabs which ingredient first?

This paper is a guidebook for answering those questions for a specific type of "recipe" used in computer science called Term Rewriting. Here is the breakdown of their findings using simple analogies.

1. The Problem: The "Single Chef" vs. The "Kitchen Brigade"

In traditional computer science, we are very good at predicting how long a single chef takes to cook a meal. We have tools that can look at a recipe and say, "This will take 10 minutes."

However, when you have a kitchen brigade where chefs work in parallel, the rules change.

The Trap: Sometimes, giving a task to 100 chefs doesn't make it 100 times faster. If the recipe says, "Wait for the sauce to boil before chopping the onions," the chopping chefs have to stand around doing nothing.
The Goal: The authors wanted to build a tool that can look at a recipe and tell you:
1. Upper Bound: "Even with infinite chefs, this will take at most X minutes." (The best-case speedup).
2. Lower Bound: "Even with infinite chefs, this will take at least Y minutes." (The bottleneck).

2. The Magic Trick: "Dependency Tuples" as a Map

To solve this, the authors used a clever trick called Parallel Dependency Tuples.

Imagine you are looking at a recipe for a cake.

Sequential View: You see a list: "Mix flour, then add eggs, then bake."
Parallel View: You see a map. "Mix flour and add eggs can happen at the same time, but baking must wait for both."

The authors created a new way to draw this map. Instead of just listing steps, they broke the recipe down into chains of dependencies.

If two tasks are independent (like chopping carrots and slicing onions), they can be done in parallel.
If one task depends on another (like baking depends on mixing), they must wait.

They realized that instead of inventing a whole new language to describe parallel cooking, they could translate the parallel recipe back into a format that their existing "single-chef" analysis tools already understood. They essentially said, "Hey, existing tools, just pretend these parallel chains are separate sequential tasks, and tell us the longest path."

3. The "Confluence" Check: Will the Cake Taste the Same?

This is the most critical part of the paper. In a parallel kitchen, chaos can happen.

Scenario: Chef A adds salt to the soup. Chef B adds pepper.
The Risk: What if Chef A and Chef B both try to grab the same spoon at the exact same time? Or what if the order in which they add ingredients changes the final taste?

In computer science, this is called Confluence. It asks: Does the order in which we perform parallel steps matter?

If Yes (Not Confluent): The computer might crash or give you a wrong answer depending on which chef moved first.
If No (Confluent): The result is deterministic. No matter who grabs what first, the final soup tastes exactly the same.

The authors realized that to accurately predict the speed of parallel cooking, you must know if the recipe is "safe" (confluent). If the recipe is chaotic, your speed predictions are useless because the result might be garbage.

They developed two new "Safety Checks" (Theorems) that act like a quality control inspector:

The "No Overlap" Check: If no two rules in the recipe ever try to use the same ingredient in a conflicting way, it's safe.
The "Trivial Overlap" Check: Even if rules overlap, if they result in the exact same outcome anyway, it's still safe.

These checks are fast and automatic. They tell the computer: "Okay, this recipe is safe to run in parallel. Now let's calculate the speed."

4. The Results: From Theory to Practice

The authors didn't just write theory; they built a tool called APROVE (a robot chef) and tested it on hundreds of standard recipes (benchmarks) from the computer science community.

The Surprise: They found that for many programs, the "parallel speedup" is massive. A task that takes $O(n^2)$ time (like sorting a huge list sequentially) might drop to $O(n)$ time (linear) when parallelized.
The Reality Check: They also found cases where parallelism doesn't help. If the recipe is a long chain of "wait for the previous step," adding more chefs doesn't speed it up. Their tool correctly identified these bottlenecks.

The Big Picture Analogy

Think of the paper as a Traffic Control System for a Super-Highway.

Sequential Analysis is like counting how long it takes one car to drive from A to B.
Parallel Analysis is asking: "If we have 1,000 lanes, how fast can 1,000 cars get there?"
The Authors' Contribution:
- They built a Map (Dependency Tuples) that shows which lanes merge and which are independent.
- They built a Safety Inspector (Confluence Criteria) to ensure that if two cars merge, they don't crash.
- They proved that you can use your old, trusted traffic laws (sequential tools) to predict the flow of this new, super-fast highway, provided you check the safety rules first.

In short: They gave us a way to automatically predict how much faster a computer program will run if we give it a super-computer with infinite cores, while guaranteeing that the answer won't change just because the cores ran in a different order.

1. Problem Statement

The paper addresses a significant gap in the literature regarding the automated analysis of parallel runtime complexity for Term Rewrite Systems (TRSs).

Context: While automated complexity analysis for sequential innermost rewriting (corresponding to call-by-value evaluation in languages like OCaml, Scala, and Rust) is mature, there are no established techniques for analyzing parallel-innermost rewriting.
The Gap: Parallel-innermost rewriting models execution on machines with unbounded parallelism where all innermost redexes (function calls on data) are reduced simultaneously. Existing tools cannot automatically determine if a program's complexity improves when parallelized (e.g., from $O(n^2)$ to $O(n)$ ) or if it remains unchanged due to structural dependencies.
Challenge: To derive lower bounds for parallel complexity, the rewrite relation must be confluent (deterministic). However, standard confluence criteria for sequential rewriting do not necessarily apply to parallel-innermost rewriting, and no automated tools existed to verify this property for the parallel strategy.

2. Methodology

The authors propose a transformational approach that leverages existing sequential complexity analysis tools to solve the parallel problem. The methodology consists of three main pillars:

A. Parallel Dependency Tuples (PDTs)

To analyze upper bounds, the authors extend the standard Dependency Tuples (DT) framework.

Concept: In sequential analysis, a rule $\ell \to r$ generates a single DT grouping all recursive calls. In parallel analysis, independent calls can be evaluated simultaneously.
Mechanism: The authors define Maximal Structural Dependency Chains (MSDC). If a rule's right-hand side contains function calls that are structurally dependent (one must wait for the other), they are grouped. If calls are independent, they are split into separate PDTs.
Result: Instead of one DT per rule, a rule generates a set of PDTs. Each PDT represents one possible "worst-case" execution path (the longest chain of dependencies). The complexity of the parallel system is bounded by the complexity of this set of PDTs using standard polynomial interpretations.

B. Transformation to Relative Rewriting

To utilize existing tools for lower bounds and to reuse sequential analysis machinery, the authors introduce a transformation from a PDT problem back to a standard TRS.

Mechanism: They transform the canonical parallel DT problem $\langle PDT(R), PDT(R), R \rangle$ into a Relative TRS $PDT(R) / R$.
Logic: In this relative system, rules from $PDT(R)$ (the parallel dependencies) count towards the complexity, while rules from $R$ (the original rewrite rules) are "free" (used only to evaluate arguments).
Benefit: This allows the use of state-of-the-art tools (like APROVE and TCT) that compute lower bounds for sequential innermost complexity to infer lower bounds for the parallel case.

C. Confluence Criteria for Parallel-Innermost Rewriting

Since the lower bound transformation requires the parallel-innermost relation ( $\xrightarrow{i}_{R}$ ) to be confluent, the authors provide two effective, syntactic sufficient criteria:

Non-overlapping Rules (Corollary 6.10): If a TRS has no critical pairs (non-overlapping), the parallel-innermost relation is deterministic and thus confluent.
Trivial Innermost Critical Overlays (Theorem 6.18): A stronger criterion stating that if all innermost critical overlays (overlaps that can actually occur in an innermost step) are trivial (i.e., result in the same term), then the parallel-innermost relation is confluent.

Significance: These criteria are purely syntactic and can be checked automatically without search problems.

3. Key Contributions

Formal Framework: Definition of Parallel Dependency Tuples (PDTs) and the Parallel-Innermost Runtime Complexity ( $pirc_R$ ).
Theoretical Proofs:
- Proof that the complexity of the canonical parallel DT problem bounds the derivation height of parallel-innermost rewriting (Theorem 4.9).
- Proof that the transformation to a relative TRS preserves both upper and lower complexity bounds (Theorems 5.6 and 5.8).
- Proof that non-overlapping TRSs and TRSs with trivial innermost critical overlays are confluent under parallel-innermost rewriting (Theorem 6.18).
Implementation: Integration of these techniques into the APROVE tool (approx. 730 lines of Java code added).
Benchmarks: Extensive experiments on 294 TRSs from the TPDB (Termination Problem Data Base) selected for their potential parallelism.

4. Experimental Results

The authors evaluated their implementation on the TPDB benchmark suite:

Upper Bounds: The new "Section 4" configuration (using PDTs) improved the inferred upper bounds for 70 TRSs (linear bounds) compared to the baseline sequential analysis (50 TRSs), a 40% improvement.
- Example: For a specific recursive TRS, the sequential bound was $O(n^{10})$ , while the parallel analysis correctly identified a tight bound of $O(n)$ .
Lower Bounds: Using the transformation to relative TRSs (Section 5), the tool successfully inferred non-trivial lower bounds for 140 out of 165 TRSs proven confluent via the weaker criterion, and 159 out of 190 using the stronger Theorem 6.18.
Confluence Analysis: The new Theorem 6.18 proved confluence for 64.6% of the benchmark set, significantly outperforming the non-overlapping criterion (56.1%). On the COPS confluence benchmark, it proved confluence for 47.5% of the systems, compared to 10.4% for the non-overlapping check.
Precision: For 49 TRSs, the tool successfully inferred tight bounds (matching upper and lower bounds, e.g., $\Theta(n)$ ).

5. Significance and Impact

Bridging the Gap: This is the first work to provide a fully automated method for inferring both upper and lower bounds for parallel term rewriting complexity.
Compiler Optimization: The results are directly applicable to parallelizing compilers. By determining if a function's complexity is asymptotically identical in sequential and parallel modes (e.g., $O(n^2)$ vs $O(n^2)$ ), compilers can avoid unnecessary parallelization overhead. Conversely, identifying cases where parallelism yields significant speedups (e.g., $O(n^2) \to O(n)$ ) guides where to apply parallel execution (e.g., on GPUs).
Tool Reuse: The methodology elegantly reuses the massive ecosystem of sequential complexity tools (APROVE, TCT) by transforming the parallel problem into a sequential one, avoiding the need to build entirely new analysis engines from scratch.
Confluence Theory: The paper resolves open conjectures regarding the relationship between sequential and parallel confluence, providing practical, checkable criteria for deterministic parallel programs.

In summary, the paper establishes a robust theoretical and practical foundation for static analysis of parallel term rewriting, enabling precise estimation of "parallelism potential" in functional programs modeled as TRSs.