Structural properties of NFAs and growth rates of nondeterminism measures

DOI10.1016/J.IC.2021.104690MaRDI QIDQ2113384zbMATH OpenOpenAlexFDO

Authors Chris Keeler, Kai Salomaa

Publication date 14 March 2022

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2021.104690

zbMATH Keywords

growth ratefinite automatanondeterminismstate complexitytree widthstring path width

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Nondeterminism growth and state complexity
• Branching measures and nearly acyclic NFAs
• Nondeterministic tree width of regular languages
• Comparisons between measures of nondeterminism on finite automata
• Branching measures and nearly acyclic NFAs

Cites work

• scientific article; zbMATH DE number 2181949 (Why is no real title available?)
• Ambiguity, nondeterminism and state complexity of finite automata
• Branching measures and nearly acyclic NFAs
• Characterizing regular languages with polynomial densities
• Communication complexity method for measuring nondeterminism in finite automata
• Comparisons between measures of nondeterminism on finite automata
• Cycle height of finite automata
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• Depth-First Search and Linear Graph Algorithms
• Descriptional and computational complexity of finite automata -- a survey
• Descriptional complexity of machines with limited resources
• Digraph complexity measures and applications in formal language theory
• Faster algorithms for the shortest path problem
• Finding the growth rate of a regular or context-free language in polynomial time
• From finite automata to regular expressions and back -- a summary on descriptional complexity
• Introduction to algorithms.
• Nondeterminism growth and state complexity
• On measuring nondeterminism in regular languages
• On the degree of ambiguity of finite automata
• Parameterized Prefix Distance between Regular Languages
• 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

Cited in

(5)

• Converting finite width AFAs to nondeterministic and universal finite automata
• Deciding path size of nondeterministic (and input-driven) pushdown automata
• Maximal existential and universal width
• Composite and non-monotonic growth functions of Mealy automata.
• Existential and universal width of alternating finite automata

This page was built for publication: Structural properties of NFAs and growth rates of nondeterminism measures

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