E-convex infix codes (Q1820251): Difference between revisions

Let X be an alphabet. For \(v,w\in X^*\) define \(v\leq_ iw\Leftrightarrow w\in X^*vX^*\) and \(v\leq_ ew\Leftrightarrow w\in X^*v_ 1X^*...X^*v_ nX^*\), where \(v=v_ 1...v_ n\), \(v_ i\in X\). These two relations are partial orders, the infix order and the embedding order, respectively. The languages \(L\subseteq X^*\) consisting of incomparable words only are known to be codes, infix codes and hypercodes, respectively. In this paper the class of infix codes is considered which are e-convex, that is, convex with respect to \(\leq_ e\). The class of hypercodes is a proper subclass of the class of e-convex infix codes; the language \(\{ba^ nb|\) \(n\geq 0\}\) is an example of an e-convex infix code which is infinite, hence not a hypercode. Two characterization results are obtained: An e-convex code is an infix code if and only if it is a bifix code. A non-empty language is an e-convex infix code if and only if \(a^{-1}L\) and \(La^{-1}\) are e-convex for any \(a\in X\) and both \(\{X^{-1}y,x\}\), \(\{yX^{-1},x\}\) are hypercodes for any x,y\(\in L\) with \(| x| <| y|\). Finally, it is shown that the set of e-convex infix codes over X forms a hereditary free submonoid of the free monoid of bifix codes over X.