Structural properties of NFAs and growth rates of nondeterminism measures
type: Item
instance of: scholarly article
title: Structural properties of NFAs and growth rates of nondeterminism measures
author: Chris Keeler
author: Kai Salomaa
published in: Information and Computation
publication date: 2022-03-14T00:00:00Z
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7488456
zbMATH Keywords: finite automata
zbMATH Keywords: nondeterminism
zbMATH Keywords: tree width
zbMATH Keywords: string path width
zbMATH Keywords: growth rate
zbMATH Keywords: state complexity
MaRDI profile type: Publication
full work available at URL: j.ic.2021.104690
OpenAlex ID: W3120287019
cites work: Faster algorithms for the shortest path problem
cites work: Q3651735
cites work: FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME
cites work: Q5422234
cites work: On measuring nondeterminism in regular languages
cites work: Q5403035
cites work: From finite automata to regular expressions and back -- a summary on descriptional complexity
cites work: Ambiguity, Nondeterminism and State Complexity of Finite Automata
cites work: Descriptional and computational complexity of finite automata -- a survey
cites work: Communication complexity method for measuring nondeterminism in finite automata
cites work: Branching measures and nearly acyclic NFAs
cites work: Cycle height of finite automata
cites work: Nondeterminism growth and state complexity
cites work: Parameterized Prefix Distance between Regular Languages
cites work: Q4967154
cites work: Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
cites work: DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
cites work: State Complexity of Finite Tree Width NFAs
cites work: Comparisons between Measures of Nondeterminism on Finite Automata
cites work: Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
cites work: Characterizing regular languages with polynomial densities
cites work: Depth-First Search and Linear Graph Algorithms
cites work: Q3022156
cites work: On the degree of ambiguity of finite automata
DOI: 10.1016/J.IC.2021.104690
description: scientific article; zbMATH DE number 7488456