Complexity of Proper Prefix-Convex Regular Languages

The final publication is available at Springer via http:/dx.doi.org/10.1007/978-3-319-60134-2_5A language L over an alphabet Σ is prefix-convex if, for any words x,y,z∈Σ∗, whenever x and xyz are in L, then so is xy. Prefix-convex languages include right-ideal, prefix-closed, and prefix-free languages, which were studied elsewhere. Here we concentrate on prefix-convex languages that do not belong to any one of these classes; we call such languages proper. We exhibit most complex proper prefix-convex languages, which meet the bounds for the size of the syntactic semigroup, reversal, complexity of atoms, star, product, and Boolean operations.Natural Sciences and Engineering Research Council of Canada [grant no. OGP0000871