The Containment Problem for Unambiguous Register Automata

2018/09/24 by Antoine Mottet, Mottet, Antoine, Karin Quaas +1 · 1 citation
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Machine Learning and Algorithms #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1809.08985

openalex publication_date 2018/09/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We investigate the complexity of the containment problem "Does L(A)⊆ 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.

Cited by

• Graded Monads in the Semantics of Nominal Automata

Related

• On the Containment Problem for Unambiguous Single-Register Automata with Guessing
• New Techniques for Universality in Unambiguous Register Automata
• When is Containment Decidable for Probabilistic Automata?
• Techniques for Showing the Decidability of the Boundedness Problem of Language Acceptors
• Lower Bounds for Unambiguous Automata via Communication Complexity