Visibly Recursive Automata

Kévin Dubrulle, Véronique Bruyère, Guillermo A. Pérez, Gaëtan Staquet

TL;DR

This paper introduces Visibly Recursive Automata (VRAs), a new modular framework for modeling systems with nested or recursive structures (like JSON, XML, or function calls). VRAs are as expressive as the industry-standard Visibly Pushdown Automata (VPAs) but offer a more intuitive, "procedural" design and significantly better algorithmic complexity for key verification tasks.

What Problem Does This Paper Address?

In formal verification and software modeling, we often need to represent recursive behaviors—situations where a program calls a function, jumps to new code, and eventually returns to where it left off. While Pushdown Automata (PDAs) can model this, most interesting questions about them (like "are these two programs equivalent?") are undecidable.

Visibly Pushdown Automata (VPAs) solved this by restricting how the stack is used, making these problems decidable. However, VPAs are "monolithic": they represent the entire system as one giant state machine, which makes them difficult for humans to design, understand, or for algorithms to "learn" from data. Existing modular alternatives, like Systems of Procedural Automata (SPAs), are easier to handle but aren't powerful enough to represent everything a VPA can.

The authors bridge this gap by creating a model that is both modular and fully expressive.

Methods

The authors define the Visibly Recursive Automaton (VRA). Instead of one large machine, a VRA is a collection of small, classical Finite Automata (FAs).

  • Procedural Calls: One FA can "call" another when it encounters a specific symbol.
  • Modular Design: Each FA serves a specific purpose, mirroring how modern software is engineered into separate functions.
  • Codeterminism: A key theoretical hurdle is that deterministic VRAs are less powerful than non-deterministic ones. To fix this, the authors introduce codeterminism—a property where different procedures triggered by the same call symbol must accept disjoint sets of words. This provides the algorithmic efficiency of determinism without sacrificing any expressive power.

The paper provides formal proofs for the equivalence between VRAs and VPAs and derives direct algorithms for standard operations (union, intersection, etc.) specifically tailored for the VRA structure.

Datasets

Not discussed in the paper. As a theoretical computer science paper, the focus is on formal definitions, proofs of expressiveness, and computational complexity analysis rather than empirical testing on specific datasets.

Key Insights and Ideas

  • The Power of Modularization: By breaking a complex system into smaller FAs, the authors show that you can achieve better computational upper bounds. For example, checking if a VRA is "empty" (accepts no words) takes $O(|A|^2)$ time, whereas the same check for a VPA takes $O(|A|^3)$.
  • Determinism vs. Expressiveness: In most automata theory, determinization is a standard "power-up." Here, the authors highlight a trap: forcing a VRA to be deterministic actually makes it weaker. Their "codeterminism" concept is a clever workaround that keeps the model powerful while keeping it computationally manageable.
  • Polynomial Translations: The paper proves that you can convert any VPA to a VRA (and vice versa) with only a polynomial increase in size, ensuring that VRAs are a practical alternative for any task currently using VPAs.

Key Results

The paper's main contribution is a complexity "scorecard" comparing VRAs to VPAs (summarized in the paper's Table 1):

Problem / Operation VRA Complexity VPA Complexity
Emptiness $O(|A|^2)$ $O(|A|^3)$
Complementation $2^{O(|A|)}$ $2^{O(|A|^2)}$
Inclusion $O(|A|^2) \cdot 2^{O(|A|)}$ $O(|A|^3) \cdot 2^{O(|A|^2)}$
Universality $2^{O(|A|)}$ $2^{O(|A|^2)}$

In almost every category, VRAs provide a lower complexity bound, particularly for complementation and universality, where the VRA approach avoids the quadratic exponent found in VPA algorithms.

Limitations and Future Work

  • Theoretical Focus: The paper is purely mathematical. While the complexity results are promising, the authors have not yet implemented these algorithms in a high-performance production tool.
  • Active Learning: The authors' long-term goal is to create an algorithm that can "learn" a VRA from examples (Angluin-style learning). This requires finding a "canonical" version of a VRA, which is still an open research question.
  • Determinization: While they solved complementation via codeterminism, the general problem of "determinizing" a VRA (when possible) remains a topic for future study.

Summary updated

Abstract

As an alternative to visibly pushdown automata, we introduce visibly recursive automata (VRAs), composed of a set of classical automata that can call each other. VRAs are a strict extension of so-called systems of procedural automata, a model proposed by Frohme and Steffen. We study the complexity of standard language-theoretic operations and classical decision problems for VRAs. Since the class of deterministic VRAs forms a strict subclass in terms of expressiveness, we propose a (weaker) notion that does not restrict expressive power and which we call codeterminism. Codeterminism comes with many desirable algorithmic properties that we demonstrate by using it, e.g., as a stepping stone towards implementing complementation of VRAs.
BibTeX
@inproceedings{dubrulle2026visibly,
  author = {Kévin Dubrulle and Véronique Bruyère and Guillermo A. Pérez and Gaëtan Staquet},
  title = {{Visibly Recursive Automata}},
  booktitle = {DLT},
  year = {2026},
  doi = {10.1007/978-3-032-28404-4\_15},
}
Figure