**SECOND EDIT**: This question is now essentially answered. See [this blog entry](http://wp.me/p1mOPD-7y) for details. Thanks to everyone who commented and answered here.




---


**EDITED TO ADD**: I asked a (hopefully more pointed and understandable) [version of this question](https://cstheory.stackexchange.com/q/7865/30) on CSTheory, and got some interesting partial answers, including a connection between this discrete combinatorial problem and the Chebyshev polynomials of the second kind. Thanks to everyone here for your help.


**ORIGINAL QUESTION**:


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.



Is there an official name for this prohibited word pattern?
I found a solution in the literature ([Latin Squares which Contain no Repeated Digrams](http://www.jstor.org/stable/2027267) by E.N. Gilbert, 1965), obtained by producing a special kind of Latin square (an *addition square*) using two permutations that are [Costas arrays](http://en.wikipedia.org/wiki/Costas_array). Please see a [blog entry](http://nanoexplanations.wordpress.com/2011/10/09/an-independent-discovery-of-costas-arrays/) I wrote for more details.


