3
$\begingroup$

Do algorithms exist to find all the patterns in a word?

I would like to count all the 3-step increasing sequences (123 i.e. 123, 234 & 345) in some word in the alphabet {1,2,3,4,5} such as "51234321343221343234". I don't care about spacing, so the subword 234 is good, but 23****4 is also good.

What if I ask these subwords be disjoint? I would expect a Robinson-Schensted-like algorithm except the increasing subsequences are of a fixed length.

Do asymptotics exist in either case?


How about patterns which are not necessarily increasing like 121 (i.e. 121,232,343,454,3**4*3, etc.)?

e.g. 51234321343221343234 has 343,121, 232,343,343 with 52124 left over.


$x = (x_1,x_2,\dots,x_3)$ and $y = (y_1,y_2,\dots,y_3)$ are "equivalent up to translation" if there is a single $k$ with $y_i = x_i + k$. A "pattern" an equivalence class of words equivalent up to translation. An "occurrence" of a pattern is an ordered subset of letters in a word equivalent to the given patterns. The bold numbers in 512 3 43213 4 32213432 3 4 are an occurrence the pattern 121.

$\endgroup$
4
  • $\begingroup$ If you're removing hits after finding them (as is implied by your words "left over"), then I think the number of hits is not well defined. For example, in the word 121121, if I first remove the first 1, first 2, and last 1, I am left with 211 -- no remaining hits; however, I can pick my first hit differently so as to end up with two total hits. If you're asking about the total number of (possibly overlapping) hits, then this is well defined, but what do you mean by "left over"? $\endgroup$ Feb 3, 2012 at 0:43
  • $\begingroup$ there will probably never be an algorithm that finds ALL the patterns in a word, it's too general. of course you can code a program to find a lot of specific patterns, like increasing sequences, but first of all, you should define what you call "pattern": is "246" a pattern? "963"? $\endgroup$ Feb 3, 2012 at 0:46
  • $\begingroup$ I think "pattern" means subword order isomorphic to a given one... so "246" and "135" are in the same pattern. Well... "123" is order-isomorphic to "246". How can I be more specific? $x = (x_1,x_2,\dots,x_3)$ and $y = (y_1,y_2,\dots,y_3)$ are equivalent up to translation so $y_i = x_i + k$ for all i. I think that's closer to what I mean. $\endgroup$ Feb 3, 2012 at 0:58
  • $\begingroup$ @Yoav. You are correct. Maybe we should ask for the maximum number of occurrences of a pattern in a given word. Or we could try to maximize the number letters left over :-) $\endgroup$ Feb 3, 2012 at 1:07

1 Answer 1

2
$\begingroup$

If you were asking for 3-step increasing sequences in permutations - and not words - then you are actually talking about so-called bivincular patterns. These were introduced in 2008 by Bousquet-Melou et al (http://arxiv.org/abs/0806.0666). Since you are only requiring that your sequences be consecutive in values - and don't place any restrictions on locations - then you could apply the inverse map (in terms of the permutation matrix it's reflection in a diagonal) to both the pattern and the permutation and you would turn your value-restrictions into location-restrictions. This would mean your patterns now become so-called vincular patterns. These were introduced in 2000 by Babson & Steingrimsson (http://combinatorics.cis.strath.ac.uk/download/BaSt00__Generalized_Permutation.pdf) under the name 'dashed patterns'.

There have been some algorithms written to count the number of permutations avoiding both types of patterns. See for example Nakamura (http://arxiv.org/abs/1102.2480).

Now, your question was about words, and not about permutations. I have not done any work in that area but there was a book that came out recently about patterns in words and permutations, see Sergey (http://www.springer.com/computer/theoretical+computer+science/book/978-3-642-17332-5)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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