An Algebraic Characterization of Prefix-Strict Languages

Abstract

Let Σ+ be the set of all finite words over a finite alphabet Σ. A word u is called a strict prefix of a word v, if u is a prefix of v and there is no other way to show that u is a subword of v. A language L⊆Σ+ is said to be prefix-strict, if for any u,v∈L, u is a subword of v always implies that u is a strict prefix of v. Denote the class of all prefix-strict languages in Σ+ by P(Σ+). This paper characterizes P(Σ+) as a universe of a model of the free object for the ai-semiring variety satisfying the additional identities x+yx≈x and x+yxz≈x. Furthermore, the analogous results for so-called suffix-strict languages and infix-strict languages are introduced.

Keywords

• free algebra
• formal languages
• embedding order
• ai-semirings variety