Branching measures and nearly acyclic NFAs

DOI10.1142/S012905411940032XzbMATH Open1427.68148OpenAlexW4234130960MaRDI QIDQ5205046FDOQ5205046

Authors: Chris Keeler, Kai Salomaa 

Publication date: 10 December 2019

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s012905411940032x

Recommendations

• Branching measures and nearly acyclic NFAs
• Nondeterminism growth and state complexity
• Worst Case Branching and Other Measures of Nondeterminism
• Nondeterministic tree width of regular languages
• Unary NFAs with limited nondeterminism

zbMATH Keywords

finite automatanondeterminismdegree of ambiguity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Introduction to algorithms.
• Depth-First Search and Linear Graph Algorithms
• Amounts of nondeterminism in finite automata
• Title not available (Why is that?)
• The tractability frontier for NFA minimization
• A Second Course in Formal Languages and Automata Theory
• Descriptional and computational complexity of finite automata -- a survey
• Finite automata and unary languages
• Descriptional complexity of machines with limited resources
• Numeration systems, linear recurrences, and regular sets
• Communication complexity method for measuring nondeterminism in finite automata
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
• On the relation between ambiguity and nondeterminism in finite automata
• Cycle-aware minimization of acyclic deterministic finite-state automata
• On the degree of ambiguity of finite automata
• Ambiguity and communication
• On measuring nondeterminism in regular languages
• Thin and slender languages
• Title not available (Why is that?)
• Recent trends in descriptional complexity of formal languages
• On the finite-valuedness problem for sequential machines
• Concise representations of regular languages by degree and probabilistic finite automata
• Ambiguity, nondeterminism and state complexity of finite automata
• State complexity of finite tree width NFAs

Cited In (4)

• Branching measures and nearly acyclic NFAs
• Worst Case Branching and Other Measures of Nondeterminism
• Cycle height of finite automata
• Computation width and deviation number

Uses Software

• OEIS

This page was built for publication: Branching measures and nearly acyclic NFAs

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