[seqfan] Re: A108122 investigated using finite state tool

[Andrew Weimholt]

This follows from the definition of a108122

The elements of the array grow as follows:

1 --> 2
2 --> 3
3 --> 1,2,2,3

If we let "1" in the array correspond to {0,10,11,12} strings ending in 11
and let "2" in the array correspond to strings ending in "10" or "12"
and let "3" in the array correspond to strings ending in "0", but not "10"

then the array growth corresponds to the ways to grow the strings...

array :: string

1 --> 2  ::  "...11" --> "...110"  (append 0)

2 --> 3  ::  "...10" --> "...100"  (append 0) -OR-
2 --> 3  ::  "...12" --> "...120"  (append 0)

3 --> 1,2,2,3 ::  "...00" --> {"...000", "...010", "...012", "...011"}
 (replace 0 w/ 00,10,12, or 11)  -OR-
3 --> 1,2,2,3 ::  "...20" --> {"...200", "...210", "...212", "...211"}
 (replace 0 w/ 00,10,12, or 11)

Andrew






On Fri, Jun 13, 2014 at 4:46 AM, Dale Gerdemann <dale.gerdemann at gmail.com>
wrote:

> Hello Seqfans,
>
> A108122 appears to count strings of digit blocks in {0,10,11,12} where the
> block 111 is forbidden. I checked this for strings up to length 25.
>
> I discovered this by experimentation with the finite state toolkit "Foma",
> which is a program that I think people ought to know about. For this test,
> I used the extended regular expression:
>
> [x|1 x|1 1|1 2]*  & ~ $[1 1 1];
>
> I used 'x' instead of '0' because, rather unfortunately, '0' is reserved
> for another purpose in Foma. The operators here are
>
> [...]     grouping
> |         union
> *        Kleene star
> &       intersection
> ~       complement
> $       containment
> There are Unicode alternatives to these, which look quite a bit nicer.
>
> Complement and containment presuppose an alphabet, which Foma defines as
> the set of occurring symbols in the extended regular expression. So here
> Sigma = {x,1,2}. The Ascii character for Sigma is '?' To count strings of
> length 5, for example, the following code can be used:
>
> define myRegex [x|1 x|1 1|1 2]*  & ~ $[1 1 1];
> regex myRegex & [? ? ? ? ?];
>
> Foma will compile this into an automaton and count the paths in this
> automaton. Even for counting strings of length 25, the result is
> instantaneous.
>
> Foma was developed by Mans Hulden for use in Computational Linguistics. But
> there's no reason why its use should be limited to CL. The program is free
> and is available on GoogleCode.
>
> Dale Gerdemann
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>