The containment problem for unambiguous register automata

DOI10.4230/LIPICS.STACS.2019.53MaRDI QIDQ5090504zbMATH OpenOpenAlexFDO

Authors Antoine Mottet, Karin Quaas

Publication date 18 July 2022

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

zbMATH Keywords

containment problemdata wordslanguage inclusion problemregister automataunambiguous automata

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• The containment problem for unambiguous register automata and unambiguous timed automata
• When is containment decidable for probabilistic automata?
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• Unambiguous constrained automata
• Unambiguous constrained automata

Cites work

• A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton
• Alternating register automata on finite words and trees
• Automata and Logics for Words and Trees over an Infinite Alphabet
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• Finite state machines for strings over infinite alphabets
• Finite-memory automata
• Finite-memory automata with non-deterministic reassignment
• Forms of determinism for automata
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• Intractability of decision problems for finite-memory automata
• LTL with the freeze quantifier and register automata
• Probabilistic automata of bounded ambiguity
• Relating timed and register automata
• Unambiguity in automata theory
• Unambiguous languages exhaust the index hierarchy
• When is containment decidable for probabilistic automata?

Cited in

(10)

• The containment problem for unambiguous register automata and unambiguous timed automata
• A special case of a unary regular language containment
• When are emptiness and containment decidable for probabilistic automata?
• On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
• Universality Problem for Unambiguous VASS
• scientific article; zbMATH DE number 7559500 (Why is no real title available?)
• Nominal tree automata with name allocation
• Language inclusion for boundedly-ambiguous vector addition systems is decidable
• New techniques for universality in unambiguous register automata
• Languages of boundedly-ambiguous vector addition systems with states

This page was built for publication: The containment problem for unambiguous register automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090504)