3
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ You seem to be missing the example of the five-letter alphabet, but presumably $\{a,b,c,d,e\}$ will do? $\endgroup$
    – j.c.
    Commented Aug 12, 2011 at 15:59
  • 1
    $\begingroup$ Your example is not clear. However, my interpretation implies that any ordered pair of two consecutive letters appears at most once in a word, which implies that any such word must have at most $n^2+1$ letters in it from an $n$ letter alphabet. While rewriting your example, using specific words that are allowed and disallowed, you might look up Debruijn sequences, which have some of the flavor of what you suggest. Gerhard "Ask Me About System Design" Paseman, 2011.08.12 $\endgroup$
    – Gerhard Paseman
    Commented Aug 12, 2011 at 18:23
  • 1
    $\begingroup$ If we take the word "official" literally, then there's no such thing as official names for concepts in mathematics. There are conventional or standard names. I think in some fields (astronomy? chemistry?) there is such a thing as official nomenclature, but not in mathematics. $\endgroup$
    – Michael Hardy
    Commented Aug 12, 2011 at 21:49
  • 1
    $\begingroup$ @Aaron, could you provide explicit examples? For example, in the example you gave, for the alphabet $\{a,b,c,d,e\}$, I take it that the word $abab$ is not part of the set. Do the letters $a$ and $b$ in your description have to be distinct? For example, is the first four-letter word in the set you describe $aaaa$? $\endgroup$
    – JRN
    Commented Aug 13, 2011 at 1:22
  • 1
    $\begingroup$ Thank you for the link to your writeup, as well as the MathOverflow acknowledgment. As part of the cleanup, I request you post an answer including the link and the phrase "Costas arrays", and then accept that answer. I don't think anyone cares about the reputation you get that way, but if you do, you can make the answer community wiki before accepting it to decline the reputation points. Gerhard "Ask Me About System Design" Paseman, 2011.10.10 $\endgroup$
    – Gerhard Paseman
    Commented Oct 10, 2011 at 15:17

4 Answers 4

Reset to default
2
$\begingroup$

I recommend looking at Balanced Incomplete Block Designs. They have some features which resemble (my interpretation of) your scenario.

Each block maps to a word (usually a block is a set, so order of elements does not matter; in the case of duplicated letters, color each a with a different color for now, and consider washing off the paint at the very end).

Pairs of elements are supposed to occur lambda many times among all blocks (usually 2 or more is considered, but you could have lambda 1 or have ab as part of one block and ba as part of another.)

It is rare, and sometimes prohibited, to have the same triplet abc appear in more than one block.

It would be nice to know more of the application. Without it, I make the following rash (and perhaps wrong) suggestion: maybe your words are not supposed to be words. Maybe they are blocks or multisets which are part of a BIBD or some generalized combinatorial design. Dinitz and Colbourn edited a handbook which you might find, well, handy, for researching your situation. Handbook of Combinatorial Designs is the title, if I recall correctly.

Gerhard "Ask Me About Block Designs" Paseman, 2011.08.13

Improve this answer
$\endgroup$
1
  • $\begingroup$ I should retract the word "rare"; Hadamard matrices correspond to BIBDs in which many triplets occur in more than one block. Even so, my rash suggestion may still be useful. Gerhard "Ask Me About System Design" Paseman, 2011.08.13 $\endgroup$
    – Gerhard Paseman
    Commented Aug 13, 2011 at 18:48
2
$\begingroup$

I found a solution in the literature (Latin Squares which Contain no Repeated Digrams by E.N. Gilbert, 1965), obtained by producing a special kind of Latin square (an addition square) using two permutations that are Costas arrays. Please see a blog entry I wrote for more details.

Improve this answer
$\endgroup$
1
$\begingroup$

This doesn't answer your specific question but might be of interest to people as background

Here's a not very specific search phrase:

permutations OR words "forbidden subsequences" OR "restricted subsequences" OR "avoidable patterns" OR "avoiding patterns" OR "pattern avoidance" OR "restricted permutations" OR "restricted words"

Some wikilinks:

http://en.wikipedia.org/wiki/Permutation_pattern

http://en.wikipedia.org/wiki/Enumerations_of_specific_permutation_classes

http://en.wikipedia.org/wiki/Combinatorics_on_words

and a forthcoming book:

Patterns in Permutations and Words:

http://www.springer.com/computer/theoretical+computer+science/book/978-3-642-17332-5

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks very much for these. A couple I already looked at, both the others no. $\endgroup$
    – Aaron Sterling
    Commented Aug 13, 2011 at 14:30
  • $\begingroup$ I just had a helpful email correspondence with Sergey Kitaev, author of the book you linked. So thanks for pointing me in that direction. $\endgroup$
    – Aaron Sterling
    Commented Aug 17, 2011 at 14:34
0
$\begingroup$

Even though this is an indirect approach to answering your question, it might reveal something useful.

For a word of length k on n letters, there are k choose 2 pairs of letters, not necessarily distinct, that appear in that word; one would thus expect a collision (a repeated substring of the form $a-^jb$, for example) in most lists of n^2/(k choose 2) words. The list might be shorter because this assumes collisions occuring at the same offset, whereas your condition does not require the repeat to occur in the two words at the same position inside each word. If you can, try to compute the length of longest possible word list meeting your constraints for some small n and k, and use the Online Encyclopedia of Integer Sequences to help.

This suggests to me a picture of certain kinds of designs: a sort of projective geometry where each point may be replaced by a multiset, as well as orthogonal array designs. If you temporarily consider the condition that collisions may occur at the same offset, I think you will have something resembling an orthogonal design, and (if I am right; check with an expert on orthogonal designs because I am NOT one) your list will be a very special kind of orthogonal design.

Gerhard "Ask Me About System Design" Paseman, 2011.08.30

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .