imported>Gfis: ref. OESI wiki

2021-11-03T21:24:30Z

ref. OESI wiki

← Older revision		Revision as of 21:24, 3 November 2021
Line 37:		Line 37:

	We begin with 2 columns, and we denote the states by pairs of substates ''s</sub>i</sub>t<sub>j</sub>''.		We begin with 2 columns, and we denote the states by pairs of substates ''s</sub>i</sub>t<sub>j</sub>''.
	\| 0 0 0 1 1 0 1 1		\| 0 0 0 1 1 0 1 1 # valid inputs
	-----+-------------------------		-----+-------------------------
	s1t1\| s1t1 s1t2 s2t1 s2t2		1 s1t1\| s1t1 s1t2 s2t1 s2t2 4
	s1t2\| s1t3 s1t2 s2t3 s2t2		2 s1t2\| s1t3 s1t2 s2t3 s2t2 4
	s1t3\| s1t3 s1x0 s2t3 s2x0		3 s1t3\| s1t3 s1x0 s2t3 s2x0 2
	s2t1\| s3t1 s3t2 s2t1 s2t2		4 s2t1\| s3t1 s3t2 s2t1 s2t2 4
	s2t2\| s3t3 s3t2 s2t3 s2t2		5 s2t2\| s3t3 s3t2 s2t3 s2t2 4
	s2t3\| s3t3 s3x0 s2t3 s2x0		6 s2t3\| s3t3 s3x0 s2t3 s2x0 2
	s3t1\| s3t1 ~~s3x0~~ ~~x0t3~~ x0t2		7 s3t1\| s3t1 s3t2 x0t1 x0t2 2
	s3t2\| s3t3 ~~s3x0~~ x0t3 x0t2		8 s3t2\| s3t3 s3t2 x0t3 x0t2 2
	s3t3\| s3t3 s3x0 x0t3 x0x0		9 s3t3\| s3t3 s3x0 x0t3 x0x0 1
			When the states are numbered 1, 2, 3, ..., the table reduces to:
			\| 00 01 10 11 #vi
			-----+-------------------------
			1\| 1 2 4 5 4
			2\| 3 2 6 5 4
			3\| 3 0 6 0 2
			4\| 7 8 4 5 4
			5\| 9 8 6 5 4
			6\| 9 0 6 0 2
			7\| 7 8 0 0 2
			8\| 9 8 0 0 2
			9\| 9 0 0 0 1
			There is a [https://github.com/gfis/OEIS-mat/blob/master/contrib/rh/dfsa.pl Perl program] that evaluates such DFSAs:
			perl dfsa.pl -d 1 4 "1,2,4,5,3,2,6,5,3,0,6,0,7,8,4,5,9,8,6,5,9,0,6,0,7,8,0,0,9,8,0,0,9,0,0,0"
			===Other regular languages===
			'''[https://oeis.org/A124696 A124696]''' is another example of a finite state machine, as explained in the [https://oeis.org/wiki/Number_of_base_k_circular_n-digit_numbers_with_adjacent_digits_differing_by_d_or_less OEIS wiki article].

imported>Gfis: First version

2021-11-03T19:56:00Z

First version

New page

== Counts of arrays ==
More than 20000 sequences in the [https://oeis.org OEIS] enumerate arrays with special properties. The sequences were defined by Ron Hardin, often with conjectured ordinary (rational) generating functions. Such o.g.f.s and/or linear recurrences with constant coefficients were also contributed by Colin Barker. We want to derive such g.f.s. systematically. As a first example, we take:
'''[https://oeis.org/ A223615]''' Number of n X 3 0..1 arrays with rows and columns unimodal.
Column 3 of A223620
G.f.: x*(7 + 44*x^2 - 20*x^3 + 20*x^4 - 6*x^5 + x^6) / (1 - x)^7.
a(n) = 7*a(n-1) - 21*a(n-2) + 35*a(n-3) - 35*a(n-4) + 21*a(n-5) - 7*a(n-6) + a(n-7) for n > 7.
=== Unimodal words ===
A unimodal word ''wi'' has one "plateau" - first the symbols are increasing (''wi <= wi+1''), then they are decreasing (''wi >= wi+1'').

For the alphabet {''0'', ''1''} the unimodal words of length ''n'' are:
n=1 2 3 4
0 00 000 0000
1 01 001 0001
10 010 0010
11 011 0011
100 0100
110 0110
111 0111
1000
1100
1110
1111
------------------
# 2 4 7 11 -> [https://oeis.org/A000124 (central polygonal numbers)]
A word is unimodal iff it does not match the regular expression pattern ''100*1''. Words of length 1 or 2 are always unimodal.
===Deterministic Finite State Automaton (DFSA)===
The DFSA for unimodal words over the alphabet {''0'', ''1''} has a simple transition table with 3 states:
symbol
state| 0 1
-----+---------
s1| s1 s2
s2| s3 s2
s3| s3 x0
We always use a start state of ''1''. Successor state ''0'' is "forbidden", since it would lead to a non-unimodal word.
===Matrices of words===
Now we arrange the words in columns of an ''n X k'' matrix, with a specified number ''k'' of parallel columns of length ''n'', and we ask for the number of such arrangeents depending on ''n''. In addition, we require that the rows in the matrix also have the unimodal property. Then we get the following DFSA table for ''k=2'' :

We begin with 2 columns, and we denote the states by pairs of substates ''sitj''.
| 0 0 0 1 1 0 1 1
-----+-------------------------
s1t1| s1t1 s1t2 s2t1 s2t2
s1t2| s1t3 s1t2 s2t3 s2t2
s1t3| s1t3 s1x0 s2t3 s2x0
s2t1| s3t1 s3t2 s2t1 s2t2
s2t2| s3t3 s3t2 s2t3 s2t2
s2t3| s3t3 s3x0 s2t3 s2x0
s3t1| s3t1 s3x0 x0t3 x0t2
s3t2| s3t3 s3x0 x0t3 x0t2
s3t3| s3t3 s3x0 x0t3 x0x0

OEIS/DFSA - Revision history

imported>Gfis: ref. OESI wiki

imported>Gfis: First version