Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
435480 | Theoretical Computer Science | 2016 | 13 Pages |
Abstract
We study the state complexity of language operations for unary NFAs with limited nondeterminism. We consider the Boolean operations, concatenation, and Kleene star. We give upper bounds for the state complexity of these language operations and lower bounds that are fairly close to the upper bounds. Our constructions rely on the fact that minimal unary NFAs with limited nondeterminism can be found in Chrobak normal form for most measures of nondeterminism. The measures of nondeterminism which are considered here with the above property are tree width, advice, and trace.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Alexandros Palioudakis, Kai Salomaa, Selim G. Akl,