The Containment Problem for Unambiguous Register Automata

DOI10.4230/LIPIcs.STACS.2019.53OpenAlexW2889973542MaRDI QIDQ5090504

Antoine Mottet, Karin Quaas

Publication date: 18 July 2022

Full work available at URL: https://arxiv.org/abs/1809.08985

zbMATH Keywords

data wordscontainment problemunambiguous automataregister automatalanguage inclusion problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (5)

When are emptiness and containment decidable for probabilistic automata? ⋮ Unnamed Item ⋮ The containment problem for unambiguous register automata and unambiguous timed automata ⋮ Universality Problem for Unambiguous VASS ⋮ On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite-memory automata
• Intractability of decision problems for finite-memory automata
• Alternating register automata on finite words and trees
• Forms of Determinism for Automata (Invited Talk)
• LTL with the freeze quantifier and register automata
• FINITE-MEMORY AUTOMATA WITH NON-DETERMINISTIC REASSIGNMENT
• Automata and Logics for Words and Trees over an Infinite Alphabet
• A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton
• Probabilistic Automata of Bounded Ambiguity
• Finite state machines for strings over infinite alphabets
• Unambiguity in Automata Theory
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY

This page was built for publication: The Containment Problem for Unambiguous Register Automata