A054747
Number of inequivalent n-state 2-input 2-output automata with respect to an input permutation.
Original entry on oeis.org
3, 76, 4003, 352744, 41876694, 6217447912, 1106509486839, 229553329028386, 54393886281136386, 14493994916221695566, 4289933406949379595583, 1396384878753272032544946, 495758886710258565409900342, 190649910996342815795394676340, 78947451456044942567072721038672, 35023754187171124856459358053765838
Offset: 1
- F. Harary and E. Palmer, Graphical Enumeration, 1973.
- Michael A. Harrison, A census of finite automata, Canad. J. Math., 17, No. 1, (1965), 100-113. [See Theorem 6.2 with k = p = 2 (p. 107) and Table IV (p. 112).]
-
A054747(n)={local(p=vector(n)); local(q=matrix(2,2)); q[1,1] = 2; q[1,2] = 0; q[2,1]=0; q[2,2]=1; my(S=0, A() = sum(j=1, 2, prod(r=1, n, prod(s=1, 2, (2*sumdiv(lcm(r,s), d, if(d < n+1, d*p[d], 0)))^(p[r]*q[j,s]*gcd(r,s)))))/2,
inc()=!forstep(i=n, 1, -1, p[i]n, p[i]=n); next(2))); t==n && S+ = A()/prod(i=1, n, i^p[i]*p[i]!)); S} \\ This is a modification of M. F. Hasler's PARI program from A002854. - Petros Hadjicostas, Mar 08 2021
A054053
Number of nonisomorphic connected n-state automata with binary inputs and outputs.
Original entry on oeis.org
4, 126, 7336, 665120, 80038860, 11992785628, 2148752458832, 448000621008112, 106551292402319492, 28471977293653977714, 8445425847422222518488, 2753705028193531309816184, 978990839708922602845440908, 376905974468378563863272876248, 156221832236610857130449469228920, 69360325968752963320307268181976608
Offset: 1
- F. Harary and E. Palmer, Graphical Enumeration, 1973. [See Section 6.5, pp. 146-150.]
- Christian G. Bower, PARI programs for transforms, 2007.
- Michael A. Harrison, A census of finite automata, Canad. J. Math., 17, No. 1 (1965), 100-113. [See Table III, p. 112.]
- N. J. A. Sloane, Maple program for transforms, 2001-2020.
-
/* This program is a modification of Christian G. Bower's PARI program for the inverse Euler transform from the link above. */
lista(nn) = {local(A=vector(nn+1)); for(n=1, nn+1, A[n]=if(n==1, 1, A054052(n-1))); local(B=vector(#A-1, n, 1/n), C); A[1] = 1; C = log(Ser(A)); A=vecextract(A, "2.."); for(i=1, #A, A[i] = polcoeff(C, i)); A = dirdiv(A, B); } \\ Petros Hadjicostas, Mar 08 2021
A129622
Number of minimal deterministic finite automata (DFA) with n states on a two-letter alphabet.
Original entry on oeis.org
0, 2, 24, 1028, 56014, 3705306, 286717796, 25493886852
Offset: 0
Johnicholas Hines (johnicholas.hines(AT)gmail.com), May 30 2007
From _Arthur O'Dwyer_, Jul 26 2024: (Start)
For n=1 the a(1)=2 distinct DFAs are
State 1: a->1, b->1
State 1: a->1, b->1, accepting
The first of these accepts the empty language; the second accepts the universal language.
For n=3, the following two DFAs are equivalent, since they accept the same language:
State 1: a->2, b->2, accepting; State 2: a->1, b->3; State 3: a->2, b->2
State 1: a->3, b->3, accepting; State 2: a->3, b->3; State 3: a->1, b->2
The following DFA is not counted at all, because it is minimizable to (that is, accepts the same language as) a two-state DFA:
State 1: a->1, b->2; State 2: a->2, b->3, accepting; State 3: a->3, b->2, accepting
(End)
- M. Almeida, N. Moreira, and R. Reis, Enumeration and generation with a string automata representation, Theor. Comp. Sci. 387 (2007) 93-102, gives a(7) in Section 5.
- Frederique Bassino, Julien David and Cyril Nicaud, REGAL: a library to randomly and exhaustively generate automata, also at HAL-00459643.
- Michael Domaratzki, Derek Kisman, and Jeffrey Shalit. On the number of distinct languages accepted by finite automata with n states, Journal of Automata, Languages and Combinatorics 7 (2002) 4-18, Section 6, a(n) = f_2(n).
Showing 1-3 of 3 results.
Comments