On the State Complexity of Scattered Substrings and Superstrings

被引：13
作者：
Okhotin, Alexander [1 ,2 ]
机构：
[1] Univ Turku, Dept Math, FIN-20014 Turku, Finland
[2] Acad Finland, Helsinki, Finland
来源：
FUNDAMENTA INFORMATICAE | 2010年 / 99卷 / 03期
基金：
芬兰科学院;
关键词：
descriptional complexity; finite automata; state complexity; substring; subword; subsequence; Higman-Haines sets; HIGMAN-HAINES SETS; REGULAR LANGUAGES; EFFECTIVE CONSTRUCTIONS; OPERATIONS; SIZE;
D O I：
10.3233/FI-2010-252
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
It is proved that the set of scattered substrings of a language recognized by an n-state DFA requires a DFA with at least 2(n/2-2) states (the known upper bound is 2(n)), with witness languages given over an exponentially growing alphabet. For a 3-letter alphabet, scattered substrings are shown to require at least 2(root 2n+30-6) states. A similar state complexity function for scattered superstrings is determined to be exactly 2(n-2) + 1 for an alphabet of at least n-2 letters, and strictly less for any smaller alphabet. For a 3-letter alphabet, the state complexity of scattered superstrings is at least 1/54(root n/2)n(-3/4).
引用
收藏
页码：325 / 338
页数：14
相关论文
共 16 条
[1]   State complexity of cyclic shift [J].
不详 .
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2008, 42 (02) :335-360
[2]  
[Anonymous], 1970, Soviet Mathematics Doklady
[3]   INTERSECTION AND UNION OF REGULAR LANGUAGES AND STATE COMPLEXITY [J].
BIRGET, JC .
INFORMATION PROCESSING LETTERS, 1992, 43 (04) :185-190
[4]  
Campeanu C., 2002, Journal of Automata, Languages and Combinatorics, V7, P303
[5]   The size of Higman-Haines sets [J].
Gruber, Hermann ;
Holzer, Markus ;
Kutrib, Martin .
THEORETICAL COMPUTER SCIENCE, 2007, 387 (02) :167-176
[6]   More on the Size of Higman-Haines Sets: Effective Constructions [J].
Gruber, Hermann ;
Holzer, Markus ;
Kutrib, Martin .
FUNDAMENTA INFORMATICAE, 2009, 91 (01) :105-121
[7]  
Haines L. H., 1969, J. Comb. Theory, V6, P94, DOI [DOI 10.1016/S0021-9800(69)80111-0, 10.1016/S0021-9800(69)80111-0, 10.1016/s0021-9800(69) 80111-0]
[8]  
Higman G., 1952, Proc. London Math. Soc., V2, P326
[9]   State complexity of some operations on binary regular languages [J].
Jirásková, G .
THEORETICAL COMPUTER SCIENCE, 2005, 330 (02) :287-298
[10]   The state complexity of L2 and Lk [J].
Rampersad, Narad .
INFORMATION PROCESSING LETTERS, 2006, 98 (06) :231-234
12