automaton.has_twins_property

Whether the automaton has the twins property.

  • Sibling states: Two states $p$, $q$ are siblings if there exist two labels $x$ and $y$ such that $p$ and $q$ can be reached from an initial state by path labeled with $x$ and there is a cycle at $p$ and $q$ both labeled with $y$.
  • Twins states: Two sibling states $p$ and $q$ are twins iff for any label $y$: $w[P(p, y, p)] = w(P[q, y, q])$
  • Has twins property: An automaton has the twins property if any two sibling states of this automaton are twins.

Preconditions:

  • The automaton is not cycle ambiguous

See also:

Examples


In [1]:
import vcsn
q = vcsn.context('lal_char(ab), q')
def std(e):
    return q.expression(e).standard()


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

Consider the following $\mathbb{Q}$ automaton:


In [2]:
a = std('(ab)*')+std('(ab)*')
a


Out[2]:
%3 I0 0 0 I0->0 F0 F2 F4 0->F0 ⟨2⟩ 1 1 0->1 a 3 3 0->3 a 2 2 1->2 b 2->F2 2->1 a 4 4 3->4 b 4->F4 4->3 a

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]:
True

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]:
%3 I0 0 0 I0->0 F0 F3 F6 0->F0 ⟨2⟩ 1 1 0->1 a 4 4 0->4 ⟨2⟩a 3 3 1->3 b 3->F3 3->1 a 6 6 4->6 b 6->F6 6->4 ⟨2⟩a

In [5]:
a.has_twins_property()


Out[5]:
False

When the automaton has no sibling states, it has the twins property.


In [6]:
a = std("(aa)*+(ab)*")
a


Out[6]:
%3 I0 0 0 I0->0 F0 F3 F6 0->F0 ⟨2⟩ 1 1 0->1 a 4 4 0->4 a 3 3 1->3 a 3->F3 3->1 a 6 6 4->6 b 6->F6 6->4 a

In [7]:
a.has_twins_property()


Out[7]:
True

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 -> $


%3 I0 0 0 I0->0 ⟨0⟩ F3 1 1 0->1 ⟨1⟩a 2 2 0->2 ⟨2⟩a 1->1 ⟨3⟩b 3 3 1->3 ⟨5⟩c 2->2 ⟨3⟩b 2->3 ⟨6⟩d 3->F3 ⟨0⟩

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]:
%3 I0 0 ⟨0⟩0 I0->0 ⟨0⟩ F2 1 ⟨0⟩1, ⟨1⟩2 0->1 ⟨1⟩a 1->1 ⟨3⟩b 2 ⟨0⟩3 1->2 ⟨5⟩c, ⟨7⟩d 2->F2 ⟨0⟩

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 -> $


%3 I0 0 0 I0->0 F3 1 1 0->1 a 2 2 0->2 ⟨2⟩a 1->1 ⟨3⟩b 3 3 1->3 ⟨5⟩c 2->2 ⟨3⟩b 2->3 ⟨6⟩d 3->F3

In [11]:
a.has_twins_property()


Out[11]:
True

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


%3 I0 0 0 I0->0 ⟨(1,0)⟩ F3 F4 1 1 0->1 ⟨(1,3)⟩a 2 2 0->2 ⟨(1,5)⟩a 3 3 1->3 ⟨(4,8)⟩b 4 4 2->4 ⟨(6,4)⟩b 3->F3 ⟨(1,0)⟩ 3->1 ⟨(9,3)⟩a 4->F4 ⟨(1,0)⟩ 4->2 ⟨(6,7)⟩a

In [13]:
a.has_twins_property()


Out[13]:
True