Visibly Recursive Automata

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

Read Visibly Recursive Automata by Kévin Dubrulle, Véronique Bruyère, Guillermo A. Pérez, and Gaëtan Staquet (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-11648.txt.

Introduction

Dubrulle and co-authors introduce visibly recursive automata that can call each other. The model gives an alternative to visibly pushdown automata for nested structure. The team studies the cost of standard operations and decision problems for these machines. Pure deterministic versions prove strictly weaker. The authors therefore define codeterminism, a weaker notion that keeps full power. Codeterminism then serves as a stepping stone toward their complementation.

Catalog record

CREATORKévin Dubrulle, Véronique Bruyère, Guillermo A. Pérez, and Gaëtan Staquet
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE140747
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.11648

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Visibly Recursive Automata Thanks: K. Dubrulle is a FRIA grantee of the Belgian Fonds de la Recherche Scientifique –FNRS; G. A. Pérez is supported by the FWO “SynthEx” project (G0AH524N). Kévin Dubrulle, Véronique Bruyère, Guillermo A. Pérez, and Gaëtan Staquet 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. 1 Introduction Almost all computer systems are programmed by defining multiple functions that call each other, sometimes recursively. When modeling such systems — for verification and model checking purposes, for instance — it is thus important to take into account the calls to functions (i.e., jump into a different part of the code) and their returns (i.e., jump back to the position immediately following that before the corresponding call). These behaviors can be represented by context-free grammars or, equivalently, pushdown automata (PDAs) [ 20 ] . While context-free languages (CFLs), i.e., the family of languages accepted by PDAs, enjoy model checking tools [ 1 , 8 , 27 , 30 ] , many properties of interest for CFLs are undecidable. For example, checking the equivalence of two PDAs, universality of a PDA, or checking whether a PDA satisfies a context-free property, are all undecidable problems. Thus, along the years, some restrictions have been considered to obtain positive decidability results, such as in [ 10 , 11 , 12 , 15 ] . Among these restrictions, here, we focus on visibly pushdown languages (VPLs), recognized by visibly pushdown automata (VPAs) [ 3 ] and nested word automata [ 5 , 4 ] . We consider only VPAs, as they are more commonly used in the literature. VPAs split the alphabet into three disjoint subsets: one set of symbols is only used for calls whose reading triggers a push on the stack, a second set only for returns whose reading pops the top of the stack, and the last set contains the internal symbols with no influence on the stack of calls. In other words, it is the type of symbol that dictates the operation to be applied on the stack. Thanks to this restriction, VPLs enjoy closure under several operations and some problems that are undecidable for CFLs become decidable for VPLs. For example, VPLs are closed under union, intersection, and complementation [ 3 ] . Moreover, emptiness, universality, and language equality and inclusion are all decidable for VPAs. VPAs have been used in practice to verify XML and JSON documents against their schemas in a streaming context [ 9 , 23 , 25 ] . In particular, in [ 9 ] , we learned (in the Angluin’s active learning setup [ 6 , 21 ] ) a VPA modeling a given JSON schema from a sample of good and bad documents. We implemented our algorithm in a prototype tool, showing that an automaton-based approach is feasible, despite the size of the learned VPA. However, VPAs suffer from a significant drawback: they tend to be large and, thus, complex to construct and learn. While a variation of VPA specialized for JSON schemas is studied in [ 25 ] , we conjecture that it would be more efficient to build an automaton defined as a collection of smaller automata , rather than a single large automaton. In [ 14 ] , we studied the validation of JSON documents using such a model (introduced in the sequel); an early implementation [ 13 ] showed promising results. Whilst other work treat models that strictly include VPAs [ 18 , 31 ] , we here focus on “modularizing” VPAs. Previous work considered two ways for modularization: k -module single-entry automata ( k -SEVPAs) [ 2 ] and systems of procedural automata (SPAs) [ 17 ] . The set of call symbols of a k -SEVPA is partitioned into k classes, the automaton has a main module and k distinct interconnected submodules, one for each class. The transitions labeled by call and return symbols manage these interconnections, by hard-coding the stack manipulations. While VPAs and k -SEVPAs are equivalent (for any value of k ) and there exists a unique minimal k -SEVPA for a given language, this minimal automaton may have exponentially more states than a VPA accepting the same language. Nonetheless, this family enjoys some active learning algorithms [ 21 , 22 ] . Our VPA-based approach from [ 9 ] actually relies on 1 -SEVPAs. Due to their sizes, our algorithm for JSON documents is slower than state-of-the-art JSON validators, as highlighted in [ 25 ] . The submodules of an SPA are classical finite automata (FAs) that are not interconnected, and the transitions do not manipulate the stack directly. Instead, each call symbol is associated with a specific automaton. Whenever the symbol corresponding to the FA \mathcal{A} is read, a call to this automaton is performed, with a jump to its initial state. Later on, when a sub-word is accepted by \mathcal{A} and followed by a return symbol, we go back to the state from which we read the call symbol. While a stack is maintained to remember the calls, it is handled purely by the semantics of SPAs, i.e., none of the transitions explicitly push or pop. In [ 17 ] , an active learning algorithm for SPAs is also presented. Interestingly, SPAs are strictly less expressive than VPAs. Contributions. In this paper, we introduce a new kind of modular automata we call visibly recursive automata (VRAs). Similarly to SPAs [ 17 ] , a VRA is composed of multiple FAs. However, in contrast to that work, we lift the restriction that each call symbol corresponds to a unique automaton. Instead, we allow multiple FAs to share a common call symbol. We argue that VRAs form a strict superset of SPAs, and we show that they are equivalent to VPAs with polynomial size translations (see Theorem 2.1 ). We claim that, like for [ 17 ] , since we construct smaller FAs, each serving a specific purpose, VRAs are easier to construct and understand: one can focus on each part of the system individually. This is much closer to how programs are engineered and implemented: each function serves a specific role and can call other functions to achieve its goal. It also mirrors the way in which JSON schemas are structured, 1 1 1 See https://json-schema.org/understanding-json-schema/structuring . i.e., in a modular way. Furthermore, we conjecture that this decomposition will allow for more efficient learning than what is possible for VPAs (each part is an FA that can be learned more easily than VPAs [ 6 , 21 , 22 ] ) and enable a modular and compositional learning algorithm more

Read the complete text