Complexity of Left-Ideal, Suffix-Closed and Suffix-Free Regular Languages
详细信息 查看全文
- 关键词：Different alphabets ; Left ideal ; Most complex ; Quotient/state complexity ; Regular language ; Suffix ; closed ; Suffix ; convex ; Suffix ; free ; Syntactic semigroup ; Transition semigroup ; Unrestricted complexity
- 刊名：Lecture Notes in Computer Science
- 出版年：2017
- 出版时间：2017
- 年：2017
- 卷：10168
- 期：1
- 页码：171-182
- 丛书名：Language and Automata Theory and Applications
- ISBN：978-3-319-53733-7
- 卷排序：10168
文摘
A language L over an alphabet \(\varSigma \) is suffix-convex if, for any words \(x,y,z\in \varSigma ^*\), whenever z and xyz are in L, then so is yz. Suffix-convex languages include three special cases: left-ideal, suffix-closed, and suffix-free languages. We examine complexity properties of these three special classes of suffix-convex regular languages. In particular, we study the quotient/state complexity of boolean operations, product (concatenation), star, and reversal on these languages, as well as the size of their syntactic semigroups, and the quotient complexity of their atoms.