Skip to main content
2 of 5
added 466 characters in body

Is there an official name for this prohibited word pattern?

In trying to design an error-correction mechanism for self-assembling systems, I have "invented" a combinatorial object that seems natural enough that it must have appeared in the literature somewhere before. However, I don't know the keywords to search on to find it. So I'm hoping someone here can point me in the right direction.

Basic idea: a subword is prohibited from appearing in a future word if it is of form a---b, where a and b appeared earlier, with the same number of letters between them.

An example on a five-letter alphabet is this:

abcd (e)
aceb (d)
beca (d)
... etc...

The set of four-letter words, where each of the four letters is chosen from the five-letter alphabet. The words are ordered as the first one, the second one, etc. For letters $a,b$ in the alphabet, once the substring $a -^i b$ appears, it can never appear again, where $-$ is a wildcard for any letter(s), and $i \geq 0$ (so $-^0$ is the empty string).

So if axyb appears anywhere on one line, where x and y are any two letters (maybe x=y, maybe not) then for all x,y axyb is prohibited to appear on any future line.

A single line like "aaaa" would be ok in some scenarios and not in others.

I'm interested if we allow letters to appear multiple times in a word, if we require each letter appear at most once, and both in results that are existential, and also algorithmic (finding lists of such words), and other properties.

What is the name of this and/or related objects? What is a standard and/or state-of-the-art reference?

Thanks very much.