Computing the width of non-deterministic automata

zbMATH Open1440.68157arXiv1811.00483MaRDI QIDQ5207047FDOQ5207047

Authors: Denis Kuperberg, Anirban Majumdar 

Publication date: 3 January 2020

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

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

zbMATH Keywords

finite automatondeterminisationautomaton widthgood-for-games automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

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

Cited In (7)

• 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
• Nondeterminism in the presence of a diverse or unknown future

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)