Portal de Periódicos da CAPES

On permutation lattices

1994; Elsevier BV; Volume: 27; Issue: 1 Linguagem: Inglês

10.1016/0165-4896(94)00733-0

1879-3118

Vincent Duquenne, Améziane Cherfouh,

Rough Sets and Fuzzy Logic

The lattice perm(n) of permutations of an n-element set n={1,…,n, 'rooted' at (1,…,n), is shown to be meet-and join-semidistributive, which implies known results such as the non-existene of M3-sublattices, and that the complementation defines a congruence relation in Perm(n) with 2n−1 classes. The meet-core of Perm(n) is shown to be the set of meet-irreducible elements together with all the elements that have two upper covers that moreover generate a covering sublattice isomorphic to Perm(3); this shows that the meet operation is completely expressible in terms of reversing adjacent pairs. A recursive construction of Perm(n) as a Galois lattice - via a kind ofsummation process - is given, which has been a key for obtaining clear drawings of Perm(4) and Perm(5) with our new PC/VGA graphic program GLAD (General Lattice Analysis and Design). Finally, the congruence lattice C(Perm(n)) is recursively characterized through the order of its meet-irreducible elements.