Complexity of Prefix-Convex Regular Languages

Janusz Brzozowski, Corwin Sinnamon

A language $L$ over an alphabet $\Sigma$ is prefix-convex if, for any words $x,y,z\in {\Sigma }^{\ast }$, whenever $x$ and $xyz$ are in $L$, then so is $xy$. Prefix-convex languages include right-idea…