State complexity of combined operations

被引：56
作者：
Salomaa, Arto
Salomaa, Kai
Yu, Sheng
机构：
[1] Turku Ctr Comp Sci, FIN-20520 Turku, Finland
[2] Queens Univ, Sch Comp, Kingston, ON K7L 3N6, Canada
[3] Univ Western Ontario, Dept Comp Sci, London, ON N6A 5B7, Canada
来源：
THEORETICAL COMPUTER SCIENCE | 2007年 / 383卷 / 2-3期
关键词：
state complexity; combined operations; regular languages;
D O I：
10.1016/j.tcs.2007.04.015
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We study the state complexity of combined operations. Two particular combined operations are studied: star of union and star of intersection. It is shown that the state complexity of a combined operation is not necessarily similar to the combination of the individual state complexities of the participating operations. (c) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码：140 / 152
页数：13
相关论文
共 22 条
[1]  
[Anonymous], LECT NOTES COMPUTER
[2]  
[Anonymous], THEORY AUTOMATA
[3]   PARTIAL ORDERS ON WORDS, MINIMAL ELEMENTS OF REGULAR LANGUAGES, AND STATE COMPLEXITY [J].
BIRGET, JC .
THEORETICAL COMPUTER SCIENCE, 1993, 119 (02) :267-291
[4]  
Campeanu C., 2002, Journal of Automata, Languages and Combinatorics, V7, P303
[5]  
Campeanu C., 2001, Proc. of Workshop on Implementing Automata 1999, V2214, P60, DOI DOI 10.1007/3-540-45526-46
[6]  
Campeanu C., 2000, DISCRETE MATH & THEO, P53
[7]  
Domaratzki M., 2002, Journal of Automata, Languages and Combinatorics, V7, P455
[8]  
Holzer M., 2001, Journal of Automata, Languages and Combinatorics, V6, P453
[9]  
Holzer M, 2003, LECT NOTES COMPUT SC, V2608, P148
[10]  
HOLZER M, 2002, LECT NOTES COMPUTER, V2450, P162
123