Branching measures and nearly acyclic NFAs

DOI10.1142/S012905411940032XMaRDI QIDQ5205046zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

finite automatanondeterminismdegree of ambiguity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

Cites work

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

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

Describes a project that uses

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)