Growth Rate of Minimum Branching
Loading...
Authors
Palioudakis, Alexandros
Han, Yo-Sub
Salomaa, Kai
Date
2018-03-14
Type
journal article
Language
en
Keyword
Finite Automata , Limited Nondeterminism , Branching Measure
Alternative Title
Abstract
There are different ways of quantifying
the nondeterminism used by a nondeterministic
finite automaton (NFA).
The amount of nondeterminism is measured as
a function of the input length.
For most nondeterminism measures the possible
growth rates of the measure have
been characterized, but this question remains
open for the branching of an NFA.
Here, we consider a close variant of the
branching measure which we call the
minimum branching.
We show that
the minimum branching of an NFA is always either
bounded or grows exponentially.
Description
Citation
Alexandros Palioudakis, Yo-Sub Han, Kai Salomaa: Growth Rate of Minimum Branching. Journal of Automata, Languages and Combinatorics 23(1-3): 281-292 (2018)
Publisher
Institut fur Informatik, Justus-Liebig Universitat Giessen