automaton.has_twins_property

Whether the automaton has twins property.

  • Sibling states: Two states $p$, $q$ are siblings if exist two labels $x$ and $y$ such that $p$ and $q$ can be reached from initial state $I$ 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

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

In [2]: 
a = vcsn.context('lal_char(ab), q').ratexp('(ab)*+(ab)*').standard()
a
Out[2]:
%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 b 3->F3 3->1 a 6 6 4->6 b 6->F6 6->4 a

State $1$ and $4$ 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 they are not twins because the weight of two cycles are different ($1$ != $2$).

In [4]: 
a = vcsn.context('lal_char(abc), q').ratexp('(<2>ab)*+(ab)*').standard()
a
Out[4]:
%3 I0 0 0 I0->0 F0 F3 F6 0->F0 ⟨2⟩ 1 1 0->1 ⟨2⟩a 4 4 0->4 a 3 3 1->3 b 3->F3 3->1 ⟨2⟩a 6 6 4->6 b 6->F6 6->4 a
In [5]: 
a.has_twins_property()
Out[5]:
False

When the automaton has not any sibling, it has twins property.

In [6]: 
a = vcsn.context("lal_char(abc), b").ratexp("(aa)*+(ab)*").standard()
a
Out[6]:
%3 I0 0 0 I0->0 F0 F3 F6 0->F0 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 tropical semiring ($\mathbb{Z}_{\text{min}}$), an automaton is determinizable iff the automaton has twins property.

In [8]: 
%%automaton a dot
digraph
{
  vcsn_context = "lal_char(abcd), zmin"
  I0 -> 0
  0 -> 1 [label = "<1>a"]
  0 -> 2 [label = "<2>a"]
  1 -> 1 [label = "<3>b"]
  1 -> 3 [label = "<5>c"]
  2 -> 2 [label = "<3>b"]
  2 -> 3 [label = "<6>d"]
  3 -> F3 [label = "<0>"]
}
%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 twins property because 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⟩

Twins property can also work in $Z$ as bellow:

In [10]: 
%%automaton a dot
digraph {
  vcsn_context = "lal_char(abcd), z"
  I0 -> 0
  0 -> 1 [label = "<1>a"]
  0 -> 2 [label = "<2>a"]
  1 -> 1 [label = "<3>b"]
  1 -> 3 [label = "<5>c"]
  2 -> 2 [label = "<3>b"]
  2 -> 3 [label = "<6>d"]
  3 -> F3
}
%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 a tuple of weightset as $\mathbb{Z} \times \mathbb{Z}_\text{min}$, for example:

In [12]: 
%%automaton a dot
digraph {
  vcsn_context = "lal_char(abc), lat<z,zmin>"
  I0 -> 0
  0 -> 1 [label = "<(1, 3)>a"]
  0 -> 2 [label = "<(1, 5)>a"]
  1 -> 3 [label = "<(4, 8)>b"]
  3 -> F3
  2 -> 4 [label = "<(6, 4)>b"]
  4 -> F4
  3 -> 1 [label = "<(9, 3)>a"]
  4 -> 2 [label = "<(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