Syntactic Complexity of Regular Ideals

被引：0
作者：
Janusz A. Brzozowski
Marek Szykuła
Yuli Ye
机构：
[1] University of Waterloo,David R. Cheriton School of Computer Science
[2] University of Wrocław,Institute of Computer Science
[3] University of Toronto,Department of Computer Science
[4] Wish.com,undefined
来源：
Theory of Computing Systems | 2018年 / 62卷
关键词：
Factor-closed; Left ideal; Prefix-closed; Regular language; Right ideal; Suffix-closed; Syntactic complexity; Transition semigroup; Two-sided ideal; Upper bound;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The state complexity of a regular language is the number of states in a minimal deterministic finite automaton accepting the language. The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of regular languages is the worst-case syntactic complexity taken as a function of the state complexity n of languages in that class. We prove that nn−1, nn−1 + n − 1, and nn−2 + (n − 2)2n−2 + 1 are tight upper bounds on the syntactic complexities of right ideals and prefix-closed languages, left ideals and suffix-closed languages, and two-sided ideals and factor-closed languages, respectively. Moreover, we show that the transition semigroups meeting the upper bounds for all three types of ideals are unique, and the numbers of generators (4, 5, and 6, respectively) cannot be reduced.
引用
收藏
页码：1175 / 1202
页数：27
相关论文
共 37 条
[1]  
Ang T(2009)Languages convex with respect to binary relations, and their closure properties Acta Cybernet. 19 445-464
[2]  
Brzozowski JA(2010)Quotient complexity of regular languages J. Autom. Lang. Comb. 15 71-89
[3]  
Brzozowski JA(2013)In search of the most complex regular languages Int. J. Found. Comput. Sc. 24 691-708
[4]  
Brzozowski JA(2013)Quotient complexity of ideal languages Theoret. Comput. Sci. 470 36-52
[5]  
Brzozowski JA(2014)Quotient complexity of closed languages Theory Comput. Syst. 54 277-292
[6]  
Jirásková G(2005)Syntactic complexity of Internat. J. Found. Comput. Sci. 16 547-563
[7]  
Li B(2012)- and J. Autom. Lang. Comb. 17 83-105
[8]  
Brzozowski JA(2012)-trivial languages Theoret. Comput. Sci. 449 37-53
[9]  
Jirásková G(2011)Syntactic complexities of six classes of star-free languages Inf. Comput. 209 353-367
[10]  
Zou C(2014)Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages Theoret. Comput. Sci. 539 13-27
1234