State complexity of combined operations

被引：54
作者：
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
    BIRGET, JC
    [J]. 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