Name
Abstract | ||
|---|---|---|
We investigate the descriptional complexity of operations on finite and infinite regular languages over unary and arbitrary alphabets. The languages are represented by nondeterministic finite automata (NFA). In particular, we consider Boolean operations, catenation operations -- concatenation, iteration, -free iteration -- and the reversal. Most of the shown bounds are tight in the exact number of states, i.e. the number is sucient and necessary in the worst case. Otherwise tight bounds in the... |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1142/S0129054103002199 | Int. J. Found. Comput. Sci. |
Keywords | Field | DocType |
nondeterministic finite automata,regular language | Discrete mathematics,Generalized nondeterministic finite automaton,Combinatorics,Nondeterministic finite automaton,Nondeterministic algorithm,Unary operation,Deterministic finite automaton,Concatenation,Regular language,Catenation,Mathematics | Journal |
Volume | Issue | Citations |
14 | 6 | 79 |
PageRank | References | Authors |
2.91 | 9 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Markus Holzer | 1 | 138 | 12.30 |
| Martin Kutrib | 2 | 778 | 89.77 |