notebook.community

Edit and run

automaton.infiltration

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



    


















    






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










    




















    
Out[1]:







$\{\ldots\}\rightarrow\mathsf{Series}[\{\ldots\}\rightarrow\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.infiltration(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.infiltration(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.infiltration(y).infiltration(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.infiltration(y.infiltration(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, infiltration 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.infiltration(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

Content source: pombredanne/https-gitlab.lrde.epita.fr-vcsn-vcsn

Similar notebooks:

notebook.community | gallery | about