Complexity of Left-Ideal, Suffix-Closed and Suffix-Free Regular Languages

Abstract

A language $L$ over an alphabet $\Sigma$ is suffix-convex if, for any words $x,y,z\in {\Sigma }^{\ast }$, 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.

20 pages, 11 figures, 1 table. arXiv admin note: text overlap with arXiv:1605.06697

References in corpus (3)

• Unrestricted State Complexity of Binary Operations on Regular Languages
• Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals
• Unrestricted State Complexity of Binary Operations on Regular and Ideal Languages