automaton.infiltrate

Create the (accessible part of the) infiltration product of two automata. In a way the infiltration product combines the conjunction (synchronized) and the shuffle product.

Preconditions:

  • all the labelsets are letterized

See also:

Examples

In [1]:
import vcsn
c = vcsn.context('lal_char, seriesset<lal_char, z>')
std = lambda exp: c.expression(exp).standard()
c
Out[1]:
$\{\ldots\}\to\mathsf{Series}[\{\ldots\}\to\mathbb{Z}]$

The following simple example aims at emphasizing that the transitions of the infiltration combine those of the shuffle and the conjunction products.

In [2]:
x = std("<x>a"); x
Out[2]:
%3 I0 0 0 I0->0 F1 1 1 0->1 ⟨x⟩a 1->F1
In [3]:
y = std("<y>a"); y
Out[3]:
%3 I0 0 0 I0->0 F1 1 1 0->1 ⟨y⟩a 1->F1
In [4]:
x & y
Out[4]:
%3 I0 0 0, 0 I0->0 F1 1 1, 1 0->1 ⟨xy⟩a 1->F1
In [5]:
x.shuffle(y)
Out[5]:
%3 I0 0 0, 0 I0->0 F3 1 1, 0 0->1 ⟨x⟩a 2 0, 1 0->2 ⟨y⟩a 3 1, 1 1->3 ⟨y⟩a 2->3 ⟨x⟩a 3->F3
In [6]:
x.infiltrate(y)
Out[6]:
%3 I0 0 0, 0 I0->0 F1 1 1, 1 0->1 ⟨xy⟩a 2 1, 0 0->2 ⟨x⟩a 3 0, 1 0->3 ⟨y⟩a 1->F1 2->1 ⟨y⟩a 3->1 ⟨x⟩a

Don't be mistaken though: if in this example the sum of the shuffle and conjunction products indeed match the infiltration product, this no longer applies to larger automata. In the following example (which nicely highlights the features of these three types of product) the transition from $(1, 0)$ to $(2, 1)$ would be missing.

In [7]:
xx = x * x
xx
Out[7]:
%3 I0 0 0 I0->0 F2 1 1 0->1 ⟨x⟩a 2 2 1->2 ⟨x⟩a 2->F2
In [8]:
yy = y * y
xx & yy
Out[8]:
%3 I0 0 0, 0 I0->0 F2 1 1, 1 0->1 ⟨xy⟩a 2 2, 2 1->2 ⟨xy⟩a 2->F2
In [9]:
xx.shuffle(yy)
Out[9]:
%3 I0 0 0, 0 I0->0 F8 1 1, 0 0->1 ⟨x⟩a 2 0, 1 0->2 ⟨y⟩a 3 2, 0 1->3 ⟨x⟩a 4 1, 1 1->4 ⟨y⟩a 2->4 ⟨x⟩a 5 0, 2 2->5 ⟨y⟩a 6 2, 1 3->6 ⟨y⟩a 4->6 ⟨x⟩a 7 1, 2 4->7 ⟨y⟩a 5->7 ⟨x⟩a 8 2, 2 6->8 ⟨y⟩a 7->8 ⟨x⟩a 8->F8
In [10]:
xx.infiltrate(yy)
Out[10]:
%3 I0 0 0, 0 I0->0 F4 1 1, 1 0->1 ⟨xy⟩a 2 1, 0 0->2 ⟨x⟩a 3 0, 1 0->3 ⟨y⟩a 4 2, 2 1->4 ⟨xy⟩a 5 2, 1 1->5 ⟨x⟩a 6 1, 2 1->6 ⟨y⟩a 2->1 ⟨y⟩a 2->5 ⟨xy⟩a 7 2, 0 2->7 ⟨x⟩a 3->1 ⟨x⟩a 3->6 ⟨xy⟩a 8 0, 2 3->8 ⟨y⟩a 4->F4 5->4 ⟨y⟩a 6->4 ⟨x⟩a 7->5 ⟨y⟩a 8->6 ⟨x⟩a

Associativity

This operator is associative.

In [11]:
x = std('<x>a')
y = std('<y>a')
z = std('<z>a')
In [12]:
a = x.infiltrate(y).infiltrate(z); a
Out[12]:
%3 I0 0 (0, 0), 0 I0->0 F1 1 (1, 1), 1 0->1 ⟨xyz⟩a 2 (1, 0), 1 0->2 ⟨xz⟩a 3 (0, 1), 1 0->3 ⟨yz⟩a 4 (1, 1), 0 0->4 ⟨xy⟩a 5 (1, 0), 0 0->5 ⟨x⟩a 6 (0, 1), 0 0->6 ⟨y⟩a 7 (0, 0), 1 0->7 ⟨z⟩a 1->F1 2->1 ⟨y⟩a 3->1 ⟨x⟩a 4->1 ⟨z⟩a 5->1 ⟨yz⟩a 5->2 ⟨z⟩a 5->4 ⟨y⟩a 6->1 ⟨xz⟩a 6->3 ⟨z⟩a 6->4 ⟨x⟩a 7->1 ⟨xy⟩a 7->2 ⟨x⟩a 7->3 ⟨y⟩a
In [13]:
b = x.infiltrate(y.infiltrate(z)); b
Out[13]:
%3 I0 0 0, (0, 0) I0->0 F1 1 1, (1, 1) 0->1 ⟨xyz⟩a 2 1, (1, 0) 0->2 ⟨xy⟩a 3 1, (0, 1) 0->3 ⟨xz⟩a 4 1, (0, 0) 0->4 ⟨x⟩a 5 0, (1, 1) 0->5 ⟨yz⟩a 6 0, (1, 0) 0->6 ⟨y⟩a 7 0, (0, 1) 0->7 ⟨z⟩a 1->F1 2->1 ⟨z⟩a 3->1 ⟨y⟩a 4->1 ⟨yz⟩a 4->2 ⟨y⟩a 4->3 ⟨z⟩a 5->1 ⟨x⟩a 6->1 ⟨xz⟩a 6->2 ⟨x⟩a 6->5 ⟨z⟩a 7->1 ⟨xy⟩a 7->3 ⟨x⟩a 7->5 ⟨y⟩a
In [14]:
a.strip().is_isomorphic(b.strip())
Out[14]:
True

Variadicity

As a convenience, infiltrate is variadic: it may accept more than two arguments. However, it's (currently) only a wrapper around repeated calls to the binary operation (as can be seen by the parentheses in the state names below).

In [15]:
c = x.infiltrate(y, z); c
Out[15]:
%3 I0 0 (0, 0), 0 I0->0 F1 1 (1, 1), 1 0->1 ⟨xyz⟩a 2 (1, 0), 1 0->2 ⟨xz⟩a 3 (0, 1), 1 0->3 ⟨yz⟩a 4 (1, 1), 0 0->4 ⟨xy⟩a 5 (1, 0), 0 0->5 ⟨x⟩a 6 (0, 1), 0 0->6 ⟨y⟩a 7 (0, 0), 1 0->7 ⟨z⟩a 1->F1 2->1 ⟨y⟩a 3->1 ⟨x⟩a 4->1 ⟨z⟩a 5->1 ⟨yz⟩a 5->2 ⟨z⟩a 5->4 ⟨y⟩a 6->1 ⟨xz⟩a 6->3 ⟨z⟩a 6->4 ⟨x⟩a 7->1 ⟨xy⟩a 7->2 ⟨x⟩a 7->3 ⟨y⟩a
In [16]:
c.strip().is_isomorphic(a.strip())
Out[16]:
True