# Is there a name for the class of operations containing prefix, suffix, etc?

I'm currently doing some research on operations on languages, specifically prefix, suffix, infix and outfix.

For example, for a language $L$, the prefix set of $L$ is:

$pref(L) = \{x \mid xy \in L, y \in \Sigma^* \}$

Infix is

$inf(L) = \{w \mid xwy \in L, x,y \in \Sigma^* \}$

and outfix is:

$outf(L) = \{xy \mid xwy \in L, w \in \Sigma^* \}$

I'm wondering, is there a name for the "class" of operations which contains all of these? I think I might have seen "bitfix" used in a paper somewhere, but it seems to mean something different.

-
A bifix code is both a prefix code and a suffix code, but that is not related to taking subwords of a language. – Hendrik Jan Jun 26 '13 at 23:29
I thought it meant something different. Good to know! – jmite Jun 27 '13 at 0:32
The paper State Complexity of Prefix, Suffix, Bifix and Infix Operators on Regular Languages (doi) does indeed define operations on languages with these names. To complicate matters, they use non-standard notions. As you did, one usually interprets prefix $pref(L)$ as $\{x\mid xy\in L\}$ whereas that paper uses $L^p=L \backslash L\Sigma^+$, which removes strings with a proper $L$ prefix. The motivation is the theory of codes, see my other remark, but its naming is extremely confusing. – Hendrik Jan Jun 27 '13 at 13:38
Isn't $pref(L) \subseteq inf(L)$? So that one disappears. And $inf(L)$ is just $L$ closed under taking substrings? – Pål GD Jul 30 '13 at 22:21
What do you mean it "disappears"? Indeed, prefix is a subset of infix, and infix is closed under substrings, and outfix is closed under removing substrings. I'm asking about the terminology: I want to know a name for the class of operations. – jmite Jul 30 '13 at 22:37

In natural languages, at least, the term is affix.

-

The closure of those operations (in fact, just the closure of "outfix") gives you arbitrary subsequences.

-

The prefix and suffix operations can be expressed in terms of right- resp. left-quotients:

$\qquad \operatorname{pref(L)} = L / \Sigma^*$ and

$\qquad \operatorname{suff(L)} = L \backslash \Sigma^*$.

Similarly, one could define "inner" and "outer" quotients like this:

$\qquad L_1 \mathbin{\bot} L_2 = \{ w \mid xwy \in L_1, xy \in L_2 \}$ and

$\qquad L_1 \mathbin{\top} L_2 = \{ xy \mid xwy \in L_1, w \in L_2 \}$.

Your infix and outfix reduce to these notions by taking $L_2 = \Sigma^*$.

I did make these up right now, but I think calling this class of operations quotients would be resonable and consistent with generalisations of prefix and suffix.

-

Sorry, do not recall a name for this common concept.

But we can come up with ideas nevertheless. I would call the notion "regular selections". Prefix selects letters from a string according to $1^*0^*$, infix according to $0^*1^*0^*$. If you like that, then your research should also include the selection of even positions $(01)^* + (01)^*0$.

-