| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 434420 | Theoretical Computer Science | 2013 | 7 Pages |
Abstract
We investigate the state complexity of combined operations for suffix-free regular languages. Suffix-free deterministic finite-state automata have a unique structural property that is crucial for obtaining the precise state complexity of basic operations. Based on the same property, we establish the state complexity of four combined operations: star-of-union, star-of-intersection, star-of-reversal and star-of-catenation. In the case of star-of-intersection, we only have an upper bound and the lower bound is open.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hae-Sung Eom, Yo-Sub Han,