Whether the automaton has the twins property.
Preconditions:
See also:
In [1]:
import vcsn
q = vcsn.context('lal_char(ab), q')
def std(e):
return q.expression(e).standard()
Consider the following $\mathbb{Q}$ automaton:
In [2]:
a = std('(ab)*')+std('(ab)*')
a
Out[2]:
State $1$ and $3$ are siblings: they can be reached from $0$ with label "a" and there are two cycles in them with the same label "ba". Since the weights of these cycles equals $1$ (in $\mathbb{Q}$), they are twins. This automaton has two sibling states only and they are twins so it has twins property.
In [3]:
a.has_twins_property()
Out[3]:
Conversely, the following automaton does not have the twins property because state $1$ and state $4$ are siblings but not twins: the weights of cycles differ ($1$ != $2$).
In [4]:
a = std('(<2>ab)*+(ab)*')
a
Out[4]:
In [5]:
a.has_twins_property()
Out[5]:
When the automaton has no sibling states, it has the twins property.
In [6]:
a = std("(aa)*+(ab)*")
a
Out[6]:
In [7]:
a.has_twins_property()
Out[7]:
In the tropical semiring ($\mathbb{Z}_{\text{min}}$), an automaton is determinizable iff the automaton has the twins property.
In [8]:
%%automaton a
context = "lal_char(abcd), zmin"
$ -> 0
0 -> 1 <1>a
0 -> 2 <2>a
1 -> 1 <3>b
1 -> 3 <5>c
2 -> 2 <3>b
2 -> 3 <6>d
3 -> $
This automaton has the twins property (the two sibling states $1$ and $2$ are twins), so it is determinizable (in $\mathbb{Z}_{\text{min}}$).
In [9]:
a.determinize()
Out[9]:
The twins property can also be check in $\mathbb{Z}$:
In [10]:
%%automaton a
context = "letterset<char_letters(abcd)>, z"
$ -> 0
0 -> 1 a
0 -> 2 <2>a
1 -> 1 <3>b
1 -> 3 <5>c
2 -> 2 <3>b
2 -> 3 <6>d
3 -> $
In [11]:
a.has_twins_property()
Out[11]:
Or with tuples of weightsets:
In [12]:
%%automaton a
context = "lal_char(abc), lat<z,zmin>"
$ -> 0
0 -> 1 <(1, 3)>a
0 -> 2 <(1, 5)>a
1 -> 3 <(4, 8)>b
3 -> $
2 -> 4 <(6, 4)>b
4 -> $
3 -> 1 <(9, 3)>a
4 -> 2 <(6, 7)>a
In [13]:
a.has_twins_property()
Out[13]: