The state complexity of language operations on XNFA-succinct unary regular languages

被引：0
作者：
Marais, Laurette [1 ,2 ]
van Zijl, Lynette [2 ]
机构：
[1] Meraka Inst, Pretoria, South Africa
[2] Stellenbosch Univ, Stellenbosch, South Africa
来源：
PROCEEDINGS OF THE ANNUAL CONFERENCE OF THE SOUTH AFRICAN INSTITUTE OF COMPUTER SCIENTISTS AND INFORMATION TECHNOLOGISTS (SAICSIT 2018) | 2018年
基金：
新加坡国家研究基金会;
关键词：
Descriptional complexity; nondeterminism; language operations;
D O I：
10.1145/3278681.3278684
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Given two unary languages accepted by symmetric difference non-deterministic finite automata, we establish bounds on the state complexity of their union, intersection, relative complement and symmetric difference. For languages L-1 and L-2 accepted by minimal symmetric difference nondeterministic finite automata of size m and n respectively, we show that the state complexity of their union, intersection and relative complement has an upper bound of (2(m) - 1)(2(n) - 1).
引用
收藏
页码：20 / 28
页数：9
相关论文
共 15 条
[1]   PARTIAL ORDERS ON WORDS, MINIMAL ELEMENTS OF REGULAR LANGUAGES, AND STATE COMPLEXITY [J].
BIRGET, JC .
THEORETICAL COMPUTER SCIENCE, 1993, 119 (02) :267-291
[2]   FINITE AUTOMATA AND UNARY LANGUAGES [J].
CHROBAK, M .
THEORETICAL COMPUTER SCIENCE, 1986, 47 (02) :149-158
[3]  
Dornhoff L., 1978, APPL MODERN ALGEBRA
[4]  
Golomb S. W., 1981, Shift Register Sequences
[5]  
Holzer M., 2003, International Journal of Foundations of Computer Science, V14, P1087, DOI 10.1142/S0129054103002199
[6]  
Hopcroft John, 1990, Introduction To Automata Theory, Languages, And Computation
[7]   Tables of maximally equidistributed combined LFSR generators [J].
L'ecuyer, P .
MATHEMATICS OF COMPUTATION, 1999, 68 (225) :261-269
[8]  
Lothaire M., 2002, Encyclopedia of Mathematics and its Applications, V90
[9]  
Marais Laurette, 2016, LECT NOTES COMPUTER, V9777, P180, DOI [10.1007/978-3-319-41114-9_14, DOI 10.1007/978-3-319-41114-9_14]
[10]  
Stone HS., 1973, DISCRETE MATH STRUCT
12