On the reversibility of word and phrase alignment

P2P notion x_1-x_2 y_1-y_2 which spans the rectangle
x_1,y_1 to x_2,y_2

generate all possible P2P alignments from W2W alignments 

Reversible w2w alignment pattern:

sequence of w2w alignments

   -------------
6  | | | | | |x|
   |-+-+-+-+-o-| 
5  | | | | |x| | 
   |-+-+-+-o-+-|     
4  | | | |x| | | 
   |-+-+-o-+-+-|   
3  | | |x| | | | 
   |-+-o-+-+-+-| 
2  | |x| | | | | 
   |-o-+-+-+-+-| 
1  |x| | | | | |
   o-----------
    1 2 3 4 5 6

6       x
5      x 
4     x  
3    x   
2   x    
1  x     
   123456


1 1
2 2
3 3
4 4
5 5
6 6


1-1 1-1
1-2 1-2
1-3 1-3
1-4 1-4
1-5 1-5
1-6 1-6
2-2 2-2
2-3 2-3
2-4 2-4
2-5 2-5
2-6 2-6
3-3 3-3
3-4 3-4
3-5 3-5
3-6 3-6
4-4 4-4
4-5 4-5
4-6 4-6
5-5 5-5
5-6 5-6
6-6 6-6

-----------------------------------------
Analogue:

6  x     
5   x    
4    x   
3     x  
2      x 
1       x
   123456

   -------------
6  |x| | | | | |
   o-+-+-+-+-+-| 
5  | |x| | | | | 
   o-o-+-+-+-+-|     
4  | | |x| | | | 
   o-o-o-+-+-+-|   
3  | | | |x| | | 
   o-o-o-o-+-+-| 
2  | | | | |x| | 
   o-o-o-o-o-+-| 
1  | | | | | |x|
   o-o-o-o-o-o-
    1 2 3 4 5 6


-----------------------------------------
   -----------
5  | | |   |x|
   |-+-+---o-|
4  | | |x x| |
   |-+-o---+-|
3  | |x|   | |
   | | |   | |
2  | |x|   | |
   |-o-+---+-|
1  |x| |   | |
   o----------
    1 2 3 4 5 
1      x
1    xx 
1   x   
1   x   
1  x    

1 1
2 2
2 3
3 4
4 4
5 5
1-1 1-1
1-2 1-3
1-4 1-4
1-5 1-5
2-2 2-3
2-4 2-4
2-5 2-5
3-4 4-4
3-5 4-5
5-5 5-5


-----------------------------------------
exhaustive w2w alignment

   -----------
5  | |     |x|
   |-+-----o-|
4  | |x x x| |
   | |     | |
3  | |x x x| |
   | |     | |
2  | |x x x| |
   |-o-----+-|
1  |x|     | |
   o----------
    1 2 3 4 5 

5      x
4   xxx 
3   xxx 
2   xxx 
1  x    
   12345

1 1
2 2
2 3
2 4
3 2
3 3
3 4
4 2
4 3
4 4
5 5
 
1-1 1-1
1-4 1-4
1-5 1-5
2-4 2-4
2-5 2-5
5-5 5-5

-----------------------------------------

exhaustive unambiguous w2w alignment
   -------------
6  |         |x|
   |-------+-o-| 
5  |     |x| | | 
   |-----o-| | |     
4  | |x| | | | | 
   |-o-| | | | |   
3  |x| | | | | | 
   o---+-| | | | 
2  |   |x| | | | 
   o---o---+-| | 
1  |       |x| |
   o-------o----
    1 2 3 4 5 6

6       x
5     x  
4   x    
3  x     
2    x   
1      x 
   123456    

1 3
2 4
3 2
4 5
5 1
6 6

1-1 3-3
1-2 3-4
1-3 2-4
1-4 2-5
1-5 1-5
1-6 1-6
2-2 4-4
3-3 2-2
4-4 5-5
5-5 1-1
6-6 6-6

-----------------------------------------
5  x   x
4   x x 
3    x  
2   x x 
1  x   x
   12345
      
   -----------
5  |x       x|
   | ------- |
4  | |x   x| |
   | | --- | |
3  | | |x| | |
   | | o-- | |
2  | |x   x| |
   | o------ |
1  |x       x|
   o----------
    1 2 3 4 5 

1 1
1 5
2 2
2 4
3 3
4 2
4 4
5 1
5 5

1-5 1-5
2-4 2-4
3-3 3-3

-----------------------------------------
Non-reversible:
w-null or null-w translations inside a P2P

spurious (null) elements are included in the phrase and
regenerated as exhaustive w2w alignments

4     x
3 x    
2 x    
1  x   
0   xx 
  01234  

   ---------
4  |     |x|
   |     o-|
3  |       |
   |       |
2  |       |
   |--     |
1  |x|     |
   o--------
    1 2 3 4 

1 1
2 0
3 0
4 4
0 2
0 3

1-1 1-1
1-4 1-4
4-4 4-4

1 1
2 2
2 3
3 2
3 3
4 4

4        x
3    x x 
2    x x 
1  x   
   1 2 3 4  

   ---------
4  |     |x|
   | ----o-|
3  | |x x| |
   | |   | |
2  | |x x| |
   |-o---- |
1  |x|     |
   o--------
    1 2 3 4 

-----------------------------------------
Non-reversible:
w-null or null-w translations inside a P2P

1  x     
1   x x  
1    x x 
1       x
   123456

   -------------
4  |x|       | |
   o---------| |
3  | |x   x  | |
   | |       | |
2  | |  x   x| |
   o-o-------+-|
1  | |       |x|
   o-o-------o--
    1 2 3 4 5 6


1 4
2 3
3 2
4 3
5 2
6 1

1-1 4-4
1-5 2-4
1-6 1-4
2-5 2-3
2-6 1-3
6-6 1-1

1 4
2 2
2 3
3 2
3 3
4 2
4 3
5 2
5 3
6 1

   -------------
4  |x|       | |
   o---------| |
3  | |x x x x| |
   | |       | |
2  | |x x x x| |
   o-o-------+-|
1  | |       |x|
   o-o-------o--
    1 2 3 4 5 6


-----------------------------------------
P2P reversibility

Usually not all possible phrase alignments are generated
but only a subset.

structure in phrase alignment 
   -------------
6  |           |
   |           | 
5  |           |
   |-------    | 
4  |       |   |
   |       |   | 
3  |       |   |
   |---    |   |   
2  |   |   |   |
   |-  |   |   |
1  | | |   |   |
   o------------ 
    1 2 3 4 5 6

1-1 1-1
1-2 1-2
1-4 1-4
1-6 1-6

1 1
2 2
3 3
3 4
4 3
4 4
5 5
5 6
6 5
6 6

1-1 1-1
1-2 1-2
1-4 1-4
1-6 1-6
2-2 2-2
2-4 2-4
2-6 2-6
3-4 3-4
3-6 3-6
5-6 5-6


   -------------
6  | | |   |x x|
   | | |   |   | 
5  | | |   |x x|
   |-+-+---o---| 
4  | | |x x|   |
   | | |   |   | 
3  | | |x x|   |
   |-+-o---+---|   
2  | |x|   |   |
   |-o-+---+---|
1  |x| |   |   |
   o-------------
    1 2 3 4 5 6

------------------------------
reversible p2p alignments

   -------------
5  |           |
   |   ---     | 
4  |   | |     |
   |-- ---     | 
3  | |         |
   |--         |   
2  |           |
   |       --- |
1  |       | | |
   --------------
    1 2 3 4 5 6

1-1 3-3
1-6 1-5
3-3 4-4
5-5 1-1

1 3
2 2
2 5
3 4
4 2
4 5
5 1
6 2
6 5

1-1 3-3
1-6 1-5
3-3 4-4
5-5 1-1

   -------------
5  |  x   x x x|
   |   ---     |
4  |   |x|     |
   |-- o--     |
3  |x|         |
   o--         |
2  |  x   x x x|
   |       --- |
1  |       |x| |
   o-------o-----
    1 2 3 4 5 6
 

-----------------------------------------

   -------
4  |     |   
   | ----+--
3  | |   | |
   | |   | |
2  | |   | |
   |-+---- |
1    |     |
     -------
    1 2 3 4 
 
1-3 2-4
2-4 1-3

1 4
2 2
2 3
3 2
3 3
4 1


1-1 4-4
1-3 2-4
1-4 1-4
2-3 2-3
2-4 1-3
4-4 1-1

 
   ---------
4  |x|   | | 
   o-----+--
3  | |x x| |
   | |   | |
2  | |x x| |
   o-o-----|
1  | |   |x|
   o-----o--
    1 2 3 4