automaton.minimize(algo = "auto")

Minimize an automaton.

The algorithm can be:

  • "auto": same as "signature" for Boolean automata on free labelsets, otherwise "weighted".
  • "brzozowski": run determinization and codeterminization.
  • "hopcroft": requires free labelset and Boolean automaton.
  • "moore": requires a deterministic automaton.
  • "signature"
  • "weighted": same as "signature" but accept non Boolean weightsets.

Preconditions:

  • the automaton is trim
  • "brzozowski"
    • the labelset is free
    • the weightset is $\mathbb{B}$
  • "hopcroft"
    • the labelset is free
    • the weightset is $\mathbb{B}$
  • "moore"
    • the automaton is deterministic
    • the weightset is $\mathbb{B}$
  • "signature"
    • the weightset is $\mathbb{B}$

Postconditions:

  • the result is equivalent to the input automaton

Caveat:

  • the resulting automaton might not be minimal if the input automaton is not deterministic.

See also:

Examples


In [1]:
import vcsn


:0: FutureWarning: IPython widgets are experimental and may change in the future.

Weighted

Using minimize or minimize("weighted").


In [2]:
%%automaton a1
context = "lal_char(abc), z"
$ -> 0
0 -> 1 <2>a
0 -> 2 <3>a
1 -> 1 a
1 -> 3 <4>a
2 -> 2 a
2 -> 4 a
3 -> $
4 -> $


%3 I0 0 0 I0->0 F3 F4 1 1 0->1 ⟨2⟩a 2 2 0->2 ⟨3⟩a 1->1 a 3 3 1->3 ⟨4⟩a 2->2 a 4 4 2->4 a 3->F3 4->F4

In [3]:
a1.minimize()


Out[3]:
%3 I0 0 0 I0->0 F3 1 1 0->1 ⟨2⟩a 2 2 0->2 ⟨3⟩a 1->1 a 3 3, 4 1->3 ⟨4⟩a 2->2 a 2->3 a 3->F3

The following example is taken from lombardy.2005.tcs, Fig. 4.


In [4]:
%%automaton a
context = "lal_char, z"
$ -> 0
$ -> 1 <2>
0 -> 0 a
0 -> 1 b
0 -> 2 <3>a,b
0 -> 3 b
1 -> 1 a, b
1 -> 2 a, <2>b
1 -> 3 <2>a
2 -> $ <2>
3 -> $ <2>


%3 I0 0 0 I0->0 I1 1 1 I1->1 ⟨2⟩ F2 F3 0->0 a 0->1 b 2 2 0->2 ⟨3⟩a, b 3 3 0->3 b 1->1 a, b 1->2 a, ⟨2⟩b 1->3 ⟨2⟩a 2->F2 ⟨2⟩ 3->F3 ⟨2⟩

In [5]:
a.minimize()


Out[5]:
%3 I0 0 0, 1 I0->0 ⟨3⟩ F1 0->0 a, b 1 2, 3 0->1 ⟨3⟩a, ⟨2⟩b 1->F1 ⟨2⟩

Signature


In [6]:
%%automaton a2
context = "lal_char(abcde), b"
$ -> 0
0 -> 1 a
0 -> 3 b
1 -> 1 a
1 -> 2 b
2 -> 2 a
2 -> 5 b
3 -> 3 a
3 -> 4 b
4 -> 4 a
4 -> 5 b
5 -> 5 a, b
5 -> $


%3 I0 0 0 I0->0 F4 1 1 0->1 a 2 2 0->2 b 1->1 a 3 3 1->3 b 2->2 a 5 5 2->5 b 3->3 a 4 4 3->4 b 4->F4 4->4 a, b 5->4 b 5->5 a

In [7]:
a2.minimize("signature")


Out[7]:
%3 I0 0 0 I0->0 F3 1 1, 2 0->1 a, b 1->1 a 2 3, 5 1->2 b 2->2 a 3 4 2->3 b 3->F3 3->3 a, b

Moore


In [8]:
a2.is_deterministic()


Out[8]:
True

In [9]:
a2.minimize("moore")


Out[9]:
%3 I0 0 0 I0->0 F3 1 1, 2 0->1 a, b 1->1 a 2 3, 5 1->2 b 2->2 a 3 4 2->3 b 3->F3 3->3 a, b

Brzozowski


In [10]:
a2.minimize("brzozowski")


Out[10]:
%3 I0 0 {0, 1, 2, 3, 4, 5} I0->0 F3 1 {1, 2, 3, 4, 5}, {0, 1, 2, 3, 4, 5} 0->1 a, b 1->1 a 2 {3, 4, 5}, {1, 2, 3, 4, 5}, {0, 1, 2, 3, 4, 5} 1->2 b 2->2 a 3 {4}, {3, 4, 5}, {1, 2, 3, 4, 5}, {0, 1, 2, 3, 4, 5} 2->3 b 3->F3 3->3 a, b

Hopcroft


In [ ]:
a2.minimize("hopcroft")

Minimization of transposed automaton

For minimization and cominimization to produce automata of the same implementation types, the minimization of a transposed automaton produces a transposed partition automaton, instead of the converse.


In [11]:
a = vcsn.b.expression('ab+ab').standard()
a.transpose().type()


Out[11]:
'transpose_automaton<mutable_automaton<letterset<char_letters(ab)>, b>>'

In [12]:
a.transpose().minimize().type()


Out[12]:
'transpose_automaton<partition_automaton<mutable_automaton<letterset<char_letters(ab)>, b>>>'

In [13]:
a.minimize().transpose().type()


Out[13]:
'transpose_automaton<partition_automaton<mutable_automaton<letterset<char_letters(ab)>, b>>>'

Repeated Minimization/Cominimization

The minimizations algorithms other than Brzozowski build decorated automata (whose type is partition_automaton). Repeated minimizarion and/or cominization does not stack these decorations, they are collapsed into a single layer.

For instance:


In [14]:
z = vcsn.context('lal_char, z')
a1 = z.expression('<2>abc').standard()
a2 = z.expression('ab<2>c').standard()
a = a1 | a2
a


Out[14]:
%3 I0 0 0 I0->0 I4 4 4 I4->4 F3 F7 1 1 0->1 ⟨2⟩a 2 2 1->2 b 3 3 2->3 c 3->F3 5 5 4->5 ⟨2⟩a 6 6 5->6 b 7 7 6->7 c 7->F7

In [15]:
a.minimize()


Out[15]:
%3 I0 0 0, 4 I0->0 ⟨2⟩ F3 1 1, 5 0->1 ⟨2⟩a 2 2, 6 1->2 b 3 3, 7 2->3 c 3->F3

In [16]:
m = a.minimize().cominimize()
m


Out[16]:
%3 I0 0 0, 4 I0->0 ⟨2⟩ F3 1 1, 5 0->1 ⟨2⟩a 2 2, 6 1->2 b 3 3, 7 2->3 c 3->F3

Note that the initial and final states are labeled 0,4 and 3,7 , not {0}, {4} and {3,7} as would have been the case if the two levels of decorations had been kept. Indeed, the type of m is simple:


In [17]:
m.type()


Out[17]:
'partition_automaton<mutable_automaton<letterset<char_letters(abc)>, z>>'

We obtain the exact same result (including decorations) even with repeated invocations, even in a different order:


In [18]:
m2 = a.cominimize().cominimize().minimize().minimize()
m2


Out[18]:
%3 I0 0 0, 4 I0->0 F3 1 1, 5 0->1 ⟨2⟩a 2 2, 6 1->2 b 3 3, 7 2->3 c 3->F3 ⟨2⟩

In [19]:
m == m2


Out[19]:
False