Return to Question

SECOND EDIT: This question is now essentially answered. See this blog entry 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 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.

SECOND EDIT: This question is now essentially answered. See this blog entry 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 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.

EDITED TO ADD: I asked a (hopefully more pointed and understandable) version of this question 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.

SECOND EDIT: This question is now essentially answered. See this blog entry 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 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.

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.

EDITED TO ADD: I asked a (hopefully more pointed and understandable) version of this question 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.