State complexity of unique rational operations

被引：3
作者：
Rampersad, Narad [1 ]
Santean, Nicolae [1 ]
Shallit, Jeffrey [1 ]
Ravikumar, Bala [2 ]
机构：
[1] Univ Waterloo, Sch Comp Sci, Waterloo, ON N2L 3G1, Canada
[2] Sonoma State Univ, Dept Comp Sci, Rohnert Pk, CA 94928 USA
来源：
THEORETICAL COMPUTER SCIENCE | 2009年 / 410卷 / 24-25期
关键词：
Unique union; Unique concatenation; Unique star; State complexity; AMBIGUITY; AUTOMATA;
D O I：
10.1016/j.tcs.2009.02.035
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
For each basic language operation we define its "unique" counterpart as being the operation that results in a language whose words can be obtained uniquely through the given operation. These Unique operations can arguably be viewed as combined basic operations, placing this work in the popular area of state complexity of combined operations on regular languages. We study the state complexity of unique rational operations and we provide upper bounds and empirical results meant to cast light into this matter. Equally important, we hope to have provided a generic methodology for estimating their state complexity. (C) 2009 Elsevier B.V. All rights reserved.
引用
收藏
页码：2431 / 2441
页数：11
相关论文
共 28 条
[1]  
[Anonymous], 1997, HDB FORMAL LANGUAGES, DOI DOI 10.1007/978-3-662-07675-0
[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]  
Blum M., 1967, 8 ANN S SWITCH AUT T, P155
[5]  
BOCHMANN GV, 2001, LNCS, V2494
[6]   AMBIGUITY IN GRAPHS AND EXPRESSIONS [J].
BOOK, R ;
EVEN, S ;
GREIBACH, S ;
OTT, G .
IEEE TRANSACTIONS ON COMPUTERS, 1971, C 20 (02) :149-+
[7]  
Campeanu C., 2002, Journal of Automata, Languages and Combinatorics, V7, P303
[8]  
CAMPEANU C, 1999, LNCS, V2214
[9]  
DALEY M, 2007, P TALE 2007, V44
[10]  
Ellul K., 2005, J. Autom. Lang. Comb., V10, P407, DOI [DOI 10.25596/JALC-2005-407, 10.25596/jalc-2005-407]
123