An Algebraic Characterization of Prefix-Strict Languages

Let <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi mathvariant="sans-serif">Σ</mi><mo>+</mo></msup></semantics></math></inline-formula> be the set of all finite words over a finite alphabet <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="sans-serif">Σ</mi></semantics></math></inline-formula>. A word <i>u</i> is called a strict prefix of a word <i>v</i>, if <i>u</i> is a prefix of <i>v</i> and there is no other way to show that <i>u</i> is a subword of <i>v</i>. A language <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>L</mi><mo>⊆</mo><msup><mi mathvariant="sans-serif">Σ</mi><mo>+</mo></msup></mrow></semantics></math></inline-formula> is said to be prefix-strict, if for any <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>∈</mo><mi>L</mi></mrow></semantics></math></inline-formula>, <i>u</i> is a subword of <i>v</i> always implies that <i>u</i> is a strict prefix of <i>v</i>. Denote the class of all prefix-strict languages in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi mathvariant="sans-serif">Σ</mi><mo>+</mo></msup></semantics></math></inline-formula> by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">P</mi><mo>(</mo><msup><mi mathvariant="sans-serif">Σ</mi><mo>+</mo></msup><mo>)</mo></mrow></semantics></math></inline-formula>. This paper characterizes <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">P</mi><mo>(</mo><msup><mi mathvariant="sans-serif">Σ</mi><mo>+</mo></msup><mo>)</mo></mrow></semantics></math></inline-formula> as a universe of a model of the free object for the ai-semiring variety satisfying the additional identities <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>x</mi><mo>+</mo><mi>y</mi><mi>x</mi><mo>≈</mo><mi>x</mi></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>x</mi><mo>+</mo><mi>y</mi><mi>x</mi><mi>z</mi><mo>≈</mo><mi>x</mi></mrow></semantics></math></inline-formula>. Furthermore, the analogous results for so-called suffix-strict languages and infix-strict languages are introduced.