Nominal Tree Automata with Name Allocation

Prucker S, Schröder L (2024)

Publication Type: Conference contribution

Publication year: 2024

Journal

LIPIcs : Leibniz International Proceedings in Informatics Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik

Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Book Volume: 311

Conference Proceedings Title: Leibniz International Proceedings in Informatics, LIPIcs

Event location: Calgary, AB CA

ISBN: 9783959773393

DOI: 10.4230/LIPIcs.CONCUR.2024.35

Abstract

Data trees serve as an abstraction of structured data, such as XML documents. A number of specification formalisms for languages of data trees have been developed, many of them adhering to the paradigm of register automata, which is based on storing data values encountered on the tree in registers for subsequent comparison with further data values. Already on word languages, the expressiveness of such automata models typically increases with the power of control (e.g. deterministic, non-deterministic, alternating). Language inclusion is typically undecidable for nondeterministic or alternating models unless the number of registers is radically restricted, and even then often remains non-elementary. We present an automaton model for data trees that retains a reasonable level of expressiveness, in particular allows non-determinism and any number of registers, while admitting language inclusion checking in elementary complexity, in fact in parametrized exponential time. We phrase the description of our automaton model in the language of nominal sets, building on the recently introduced paradigm of explicit name allocation in nominal automata.

Authors with CRIS profile

Simon Prucker Lehrstuhl für Informatik 8 (Theoretische Informatik) Lutz Schröder Lehrstuhl für Informatik 8 (Theoretische Informatik)

How to cite

APA:

Prucker, S., & Schröder, L. (2024). Nominal Tree Automata with Name Allocation. In Rupak Majumdar, Alexandra Silva (Eds.), Leibniz International Proceedings in Informatics, LIPIcs. Calgary, AB, CA: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.

MLA:

Prucker, Simon, and Lutz Schröder. "Nominal Tree Automata with Name Allocation." Proceedings of the 35th International Conference on Concurrency Theory, CONCUR 2024, Calgary, AB Ed. Rupak Majumdar, Alexandra Silva, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2024.

BibTeX: Download