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.
| Original language | English |
|---|---|
| Pages (from-to) | 87-93 |
| Number of pages | 7 |
| Journal | Theoretical Computer Science |
| Volume | 510 |
| DOIs | |
| Publication status | Published - 2013 Oct 28 |
Bibliographical note
Funding Information:This research was supported by the Basic Science Research Program through NRF funded by MEST ( 2010-0009168 , 2012R1A1A2044562 ).
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)