| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 434799 | Theoretical Computer Science | 2012 | 13 Pages |
Abstract
We investigate the nondeterministic state complexity of several operations on finite automata accepting star-free and unary star-free languages. It turns out that in most cases exactly the same tight bounds as for general regular languages are reached. This nicely complements the results recently obtained by Brzozowski and Liu (2011) [8] for the operation problem of star-free and unary star-free languages accepted by deterministic finite automata.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
