2026-07-23T13:35:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10292 2024-03-06T10:45:44Z ddc:004 open_access

The Containment Problem for Unambiguous Register Automata Mottet, Antoine Quaas, Karin Data words Register automata Unambiguous Automata Containment Problem Language Inclusion Problem We investigate the complexity of the containment problem "Does L(A)subseteq L(B) hold?", where B is an unambiguous register automaton and A is an arbitrary register automaton. We prove that the problem is decidable and give upper bounds on the computational complexity in the general case, and when B is restricted to have a fixed number of registers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antoine Mottet and Karin Quaas 2019 Is Part Of LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2019.53 urn:nbn:de:0030-drops-102926 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.53 eng https://creativecommons.org/licenses/by/3.0/legalcode