Computing the width of non-deterministic automata

MaRDI QIDQ5207047zbMATH OpenFDO

Authors Denis Kuperberg, Anirban Majumdar

Publication date 3 January 2020

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

zbMATH Keywords

finite automatondeterminisationautomaton widthgood-for-games automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Width of non-deterministic automata
• Nondeterminism growth and state complexity
• Nondeterministic tree width of regular languages
• On Determinisation of Good-for-Games Automata
• Worst Case Branching and Other Measures of Nondeterminism

Cites work

• scientific article; zbMATH DE number 3492660 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1927559 (Why is no real title available?)
• scientific article; zbMATH DE number 5585443 (Why is no real title available?)
• Alternating finite automata on -words
• Are good-for-games automata good for probabilistic model checking?
• Büchi Good-for-Games Automata Are Efficiently Recognizable
• Checking NFA equivalence with bisimulations up to congruence
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• Decidability results on the existence of lookahead delegators for NFA
• Deciding parity games in quasipolynomial time
• Eventually safe languages
• Finite-state automata on infinite inputs
• Forms of determinism for automata
• Minimizing GFG Transition-Based Automata
• Nondeterminism in the presence of a diverse or unknown future
• On Determinisation of Good-for-Games Automata
• Provably Difficult Combinatorial Games
• Reasoning about online algorithms with weighted automata
• Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
• Solving Games Without Determinization
• Structurally Unambiguous Finite Automata
• The Complexity of Tree Automata and Logics of Programs
• The Theory of Stabilisation Monoids and Regular Cost Functions
• The quest for a tight translation of Büchi to co-Büchi automata
• Universal graphs and good for games automata: new tools for infinite duration games
• Width of non-deterministic automata

Cited in

(7)

• Nondeterminism in the presence of a diverse or unknown future
• Computer Aided Verification
• THE LENGTH OF SUBSET REACHABILITY IN NONDETERMINISTIC AUTOMATA
• Testing Computability by Width Two OBDDs
• Width of non-deterministic automata
• Computation width and deviation number
• VC-dimensions of nondeterministic finite automata for words of equal length

This page was built for publication: Computing the width of non-deterministic automata

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