Structural properties of NFAs and growth rates of nondeterminism measures

DOI10.1016/J.IC.2021.104690OpenAlexW3120287019MaRDI QIDQ2113384FDOQ2113384

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)

Cites Work

• Introduction to algorithms.
• Depth-First Search and Linear Graph Algorithms
• Title not available (Why is that?)
• Faster algorithms for the shortest path problem
• Finding the growth rate of a regular or context-free language in polynomial time
• Descriptional and computational complexity of finite automata -- a survey
• Descriptional complexity of machines with limited resources
• 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
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• On the degree of ambiguity of finite automata
• From finite automata to regular expressions and back -- a summary on descriptional complexity
• On measuring nondeterminism in regular languages
• Characterizing regular languages with polynomial densities
• Title not available (Why is that?)
• Cycle height of finite automata
• Comparisons between Measures of Nondeterminism on Finite Automata
• Title not available (Why is that?)
• Ambiguity, Nondeterminism and State Complexity of Finite Automata
• Nondeterminism growth and state complexity
• State Complexity of Finite Tree Width NFAs
• Branching measures and nearly acyclic NFAs
• Parameterized Prefix Distance between Regular Languages

Cited In (4)

• Deciding path size of nondeterministic (and input-driven) pushdown automata
• Composite and non-monotonic growth functions of Mealy automata.
• Existential and universal width of alternating finite automata
• Converting finite width AFAs to nondeterministic and universal 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)