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.
| Original language | English |
|---|---|
| Pages (from-to) | 281-292 |
| Number of pages | 12 |
| Journal | Journal of Automata, Languages and Combinatorics |
| Volume | 23 |
| Issue number | 1-3 |
| Publication status | Published - 2018 |
Bibliographical note
Funding Information:(C) Supported by the Basic Science Research Program through NRF funded by MEST (2015R1D1A1A01060097) and the Yonsei University Future-leading Research Initiative of 2016.(D)Supported by the Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.We thank the anonymous referees for a careful reading of the paper and useful suggestions.
Funding Information:
(C)Supported by the Basic Science Research Program through NRF funded by MEST (2015R1D1A1A01060097) and the Yonsei University Future-leading Research Initiative of 2016. (D)Supported by the Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.
Publisher Copyright:
© Institut für Informatik · Justus-Liebig-Universität Giessen.
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics