Decomposition tree of a lexicographic product of binary structures

Given a set S and a positive integer k , a binary structure is a function B : ( S × S ) ∖ { ( x , x ) ; x ∈ S } ⟶ { 1 , … , k } . The set S is denoted by V ( B ) and the integer k is denoted by rk ( B ) . With each subset X of V ( B ) associate the binary substructure B [ X ] of B induced by X defined by B [ X ] ( x , y ) = B ( x , y ) for any x ≠ y ∈ X . A subset X of V ( B ) is a clan of B if for any x , y ∈ X and v ∈ V ( B ) ∖ X , B ( x , v ) = B ( y , v ) and B ( v , x ) = B ( v , y ) . A subset X of V ( B ) is a hyperclan of B if X is a clan of B satisfying: for every clan Y of B , if X ∩ Y ≠ 0̸ , then X ⊆ Y or Y ⊆ X . With each binary structure B associate the family Π ( B ) of the maximal proper and nonempty hyperclans under inclusion of B . The decomposition tree of a binary structure B is constituted by the hyperclans X of B such that Π ( B [ X ] ) ≠ 0̸ and by the elements of Π ( B [ X ] ) . Given binary structures B and C such that rk ( B ) = rk ( C ) , the lexicographic product B ⌊ C ⌋ of C by B is defined on V ( B ) × V ( C ) as follows. For any ( x , y ) ≠ ( x ′ , y ′ ) ∈ V ( B ) × V ( C ) , B ⌊ C ⌋ ( ( x , x ′ ) , ( y , y ′ ) ) = B ( x , y ) if x ≠ y and B ⌊ C ⌋ ( ( x , x ′ ) , ( y , y ′ ) ) = C ( x ′ , y ′ ) if x = y . The decomposition tree of the lexicographic product B ⌊ C ⌋ is described from the decomposition trees of B and C .