Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10330789 | Information and Computation | 2011 | 10 Pages |
Abstract
Finite automata operating on nested words were introduced by Alur and Madhusudan in 2006. While nested word automata retain many of the desirable properties of ordinary finite automata, there is no known efficient minimization algorithm for deterministic nested word automata and, interestingly, state complexity bounds for nested word automata turn out to differ significantly from the corresponding bounds for ordinary finite automata. Consequently lower bounds for the state complexity of nested word languages need to rely on fooling set type techniques. We discuss limitations of the techniques and show that, even in the deterministic case, the bounds given by the lower bound methods may be arbitrarily far away from the actual state complexity of the nested word language.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Kai Salomaa,