Fundamenta Informaticae - Volume 188, issue 4

Authors: Koguep Njionou, Blaise B. | Kwuida, Leonard | Lele, Celestin

Article Type: Research Article

Abstract: Multilattices are generalisations of lattices introduced by Mihail Benado in [4]. He replaced the existence of unique lower (resp. upper) bound by the existence of maximal lower (resp. minimal upper) bound(s). A multilattice will be called pure 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 fuzzy setting. In this paper we exhibit the smallest pure multilattice and show that it is a sub-multilattice of any pure multilattice. We also prove that any bounded residuated multilattice that is not a residuated lattice has at least …seven elements. We apply the ordinal sum construction to get more examples of residuated multilattices that are not residuated lattices. We then use these residuated multilattices to evaluate objects and attributes in formal concept analysis setting, and describe the structure of the set of corresponding formal concepts. More precisely, if 𝒜i := (A i , ≤i , ⊤i , ⊙i , →i , ⊥i ), i = 1, 2 are two complete residuated multilattices, G and M two nonempty sets and (ϕ , ψ ) a Galois connection between A 1 G and A 2 M that is compatible with the residuation, then we show that 𝒞     : =   { ( h ,   f )   ∈   A 1 G   ×   A 2 M ;   φ ( h )   =   f   and   ψ ( f )   =   h }   can be endowed with a complete residuated multilattice structure. This is a generalization of a result by Ruiz-Calviño and Medina [20] saying that if the (reduct of the) algebras 𝒜i , i = 1; 2 are complete multilattices, then 𝒞 is a complete multilattice. Show more

Keywords: multilattices, sub-multilattices, residuated multilattices, Formal Concept Analysis, ordinal sum of residuated multilattices

DOI: 10.3233/FI-222147

Citation: Fundamenta Informaticae, vol. 188, no. 4, pp. 217-237, 2022

Authors: Llorens, M. | Oliver, J. | Silva, J. | Tamarit, S.

Article Type: Research Article

Abstract: Context: Petri net slicing is a technique to reduce the size of a Petri net to ease the analysis or understanding of the original Petri net. Objective: Presenting two new Petri net slicing algorithms to isolate those places and transitions of a Petri net (the slice) that may contribute tokens to one or more places given (the slicing criterion). Method: The two algorithms proposed are formalized. The maximality of the first algorithm and the minimality of the second algorithm are formally proven. Both algorithms together with three other state-of-the-art algorithms have been implemented and integrated into …a single 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, and open-source implementation of five algorithms is reported. The results of an empirical evaluation of the new algorithms and the slices they produce are also presented. Conclusions: The first algorithm collects all places and transitions that may contribute tokens (in any computation) to the slicing criterion, while the second algorithm collects the places and transitions needed to fire the shortest transition sequence that contributes tokens to some place in the slicing criterion. Therefore, the net computed by the first algorithm can reproduce any computation that contributes tokens to any place of interest. In contrast, the second algorithm loses this possibility, but it often produces a much more reduced subnet (which still can reproduce some computations that contribute tokens to some places of interest). The first algorithm is proven maximal, and the second one is proven minimal. Show more

Keywords: Petri nets, Program slicing, Petri net slicing

DOI: 10.3233/FI-222148

Citation: Fundamenta Informaticae, vol. 188, no. 4, pp. 239-267, 2022

Authors: Rajeshwari, S. | Rajesh, M.

Article Type: Research Article

Abstract: Graph embeddings play a significant role in the design and analysis of parallel algorithms. It is a mapping of the topological structure of a guest graph G into a host graph H , which is represented as a one-to-one mapping from the vertex set of the guest graph to the vertex set of the host graph. In multiprocessing systems, the interconnection networks enhance the efficient communication between the components in the system. Obtaining minimum wirelength in embedding problems is significant in the designing of networks and simulating one architecture by another. In this paper, we determine the wirelength of …embedding 3-ary n -cubes into cylinders and certain trees. Show more

Keywords: embedding, edge isoperimetric problem, congestion, wirelength, 3-ary n-cube

DOI: 10.3233/FI-222149

Citation: Fundamenta Informaticae, vol. 188, no. 4, pp. 269-284, 2022