Visibly Recursive Automata
This work addresses formal language theory problems for automata models, offering incremental improvements in expressiveness and algorithms.
The authors introduced visibly recursive automata (VRAs) as an extension of visibly pushdown automata, showing that deterministic VRAs are less expressive but proposing codeterminism to preserve expressiveness with better algorithmic properties, such as enabling complementation.
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.