Volume 188, Issue 4


1. Formal Concepts and Residuation on Multilattices

Blaise B. Koguep Njionou ; Leonard Kwuida ; Celestin Lele.
Multilattices are generalisations of lattices introduced by Mihail Benado. Hereplaced the existence of unique lower (resp. upper) bound by the existence ofmaximal lower (resp. minimal upper) bound(s). A multilattice will be calledpure if it is not a lattice. Multilattices could be endowed with a residuation,and therefore used as set of truth-values to evaluate elements in fuzzysetting. In this paper we exhibit the smallest pure multilattice and show thatit is a sub-multilattice of any pure multilattice. We also prove that anybounded residuated multilattice that is not a residuated lattice has at leastseven elements. We apply the ordinal sum construction to get more examples ofresiduated multilattices that are not residuated lattices. We then use theseresiduated multilattices to evaluate objects and attributes in formal conceptanalysis setting, and describe the structure of the set of corresponding formalconcepts. More precisely, if $\mathcal{A}_i:=(A_i,\le_i,\top_i,\odot_i,\to_i,\bot_i)$, $i=1,2$ are two complete residuatedmultilattices, $G$ and $M$ two nonempty sets and $(\varphi, \psi)$ a Galoisconnection between $A_1^G$ and $A_2^M$ that is compatible with the residuation,then we show that \[\mathcal{C}: =\{(h,f)\in A_1^G\times A_2^M; \varphi(h)=f \text{ and }\psi(f)=h \}\] can be endowed with a complete residuated multilatticestructure. This is a generalization of a result by Ruiz-Calvi{\~n}o and Medinasaying that if the (reduct of the) algebras $\mathcal{A}_i$, $i=1,2$ […]

2. Exact Wirelength of Embedding 3-Ary n-Cubes into certain Cylinders and Trees

Rajeshwari S ; M Rajesh.
Graph embeddings play a significant role in the design and analysis ofparallel algorithms. It is a mapping of the topological structure of a guestgraph G into a host graph H, which is represented as a one-to-one mapping fromthe vertex set of the guest graph to the vertex set of the host graph. Inmultiprocessing systems the interconnection networks enhance the efficientcommunication between the components in the system. Obtaining minimumwirelength in embedding problems is significant in the designing of network andsimulating one architecture by another. In this paper, we determine thewirelength of embedding 3-ary n-cubes into cylinders and certain trees.

3. Maximal and minimal dynamic Petri net slicing

Marisa Llorens ; Javier Oliver ; Josep Silva ; Salvador Tamarit.
Context: Petri net slicing is a technique to reduce the size of a Petri netto ease the analysis or understanding of the original Petri net. Objective:Presenting two new Petri net slicing algorithms to isolate those places andtransitions of a Petri net (the slice) that may contribute tokens to one ormore places given (the slicing criterion). Method: The two algorithms proposedare formalized. The maximality of the first algorithm and the minimality of thesecond algorithm are formally proven. Both algorithms, together with threeother state-of-the-art algorithms, have been implemented and integrated into asingle tool so that we have been able to carry out a fair empirical evaluation.Results: Besides the two new Petri net slicing algorithms, a public, free, andopen-source implementation of five algorithms is reported. The results of anempirical evaluation of the new algorithms and the slices they produce are alsopresented. Conclusions: The first algorithm collects all places and transitionsthat may contribute tokens (in any computation) to the slicing criterion, whilethe second algorithm collects the places and transitions needed to fire theshortest transition sequence that contributes tokens to some place in theslicing criterion. Therefore, the net computed by the first algorithm canreproduce any computation that contributes tokens to any place of interest. Incontrast, the second algorithm loses this possibility, but it often produces amuch more reduced subnet (which still can […]