Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10334320 | Theoretical Computer Science | 2005 | 12 Pages |
Abstract
We investigate the state complexity of some operations on binary regular languages. In particular, we consider the concatenation of languages represented by deterministic finite automata, and the reversal and complementation of languages represented by nondeterministic finite automata. We prove that the upper bounds on the state complexity of these operations, which were known to be tight for larger alphabets, are tight also for binary alphabets.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Galina Jirásková,