State Complexity of Combined Operations for Prefix-Free Regular Languages

Title
State Complexity of Combined Operations for Prefix-Free Regular Languages
Authors
한요섭Kai SalomaaSheng Yu
Issue Date
2009-03
Publisher
Lecture notes in computer science
Citation
VOL 5457, 398-409
Abstract
We investigate the state complexity of combined operations for prefix-free regular languages. Prefix-free minimal deterministic finitestate automata have a unique structural property that plays an important role to obtain the precise state complexity of basic operations. Based on the same property, we establish the precise state complexity of four combined operations: star-of-union, star-of-intersection, star-of-reversal and star-of-catenation.
URI
http://pubs.kist.re.kr/handle/201004/37014
ISSN
0302-9743
Appears in Collections:
KIST Publication > Article
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE