Visibly Recursive Automata
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915999666667520 |
|---|---|
| author | Dubrulle, Kévin Bruyère, Véronique Pérez, Guillermo A. Staquet, Gaëtan |
| author_facet | Dubrulle, Kévin Bruyère, Véronique Pérez, Guillermo A. Staquet, Gaëtan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_11648 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Visibly Recursive Automata Dubrulle, Kévin Bruyère, Véronique Pérez, Guillermo A. Staquet, Gaëtan Formal Languages and Automata Theory Computational Complexity 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. |
| title | Visibly Recursive Automata |
| topic | Formal Languages and Automata Theory Computational Complexity |
| url | https://arxiv.org/abs/2603.11648 |