Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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.

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.