Fundamenta Informaticae - Volume 46, issue 4

Authors: Bělohlávek, Radim

Article Type: Research Article

Abstract: Presented is a reduction of fuzzy Galois connections and fuzzy concept lattices to (crisp) Galois connections and concept lattices: each fuzzy concept lattice can be viewed as a concept lattice (in a natural way). As a result, a simple proof of the characterization theorem for fuzzy concept lattices is obtained. The reduction enables us to apply the results worked out for concept lattices to fuzzy concept lattices.

Keywords: fuzzy concept lattice, fuzzy Galois connection

Citation: Fundamenta Informaticae, vol. 46, no. 4, pp. 277-285, 2001

Authors: Dietzfelbinger, Martin | Gambin, Anna | Lasota, Sławomir

Article Type: Research Article

Abstract: Multistage interconnection networks (MINs) have a number of applications in many areas, for example in parallel computing systems or high-speed communication networks. In the paper we define Markov chains describing several models of packet flow through the buffered MIN with a butterfly interconnection structure and 2×2 switching elements. We develop a notation together with a mathematical framework enabling to prove certain results relating the models. Moreover, we show that all considered Markov …chains are ergodic and discuss relationships between stationary distributions. The important novelty is that our approach is compositional, which allows to keep the complexity of description of a very complicated network's behaviour on a reasonable and tractable level. Considerations are mostly independent of specific network topology and routing protocol, hence we expect our method to be applicable also in other contexts for stochastic models of massively parallel systems. Show more

Keywords: Multistage Interconnection Networks, continuous routing, throughput, Markov chains

Citation: Fundamenta Informaticae, vol. 46, no. 4, pp. 287-314, 2001

Authors: Nguyen, Linh Anh

Article Type: Research Article

Abstract: We propose a modal query language called MDatalog. A rule of an MDatalog program is a universally quantified modal Horn clause. This language is interpreted in fixed-domain first-order modal logics over signatures without functions. We give algorithms to construct the least models for MDatalog programs. We show PTIME complexity of computing queries for a given MDatalog program in the logics KD, T, KB, KDB, B, K5, KD5, K45, KD45, KB5, and S5, provided that the quantifier …depths of queries and the program are finitely bounded, and that the modal depth of the program is finitely bounded in the case when the considered logic is not an extension of K5. Some examples are given to illustrate application of the techniques to reason about belief and knowledge. Show more

Citation: Fundamenta Informaticae, vol. 46, no. 4, pp. 315-342, 2001

Authors: Ostravský, Jan

Article Type: Research Article

Abstract: In [9] submonoids of a commutative monoid are characterized by means of their relations of domination, subgroups of a commutative monoid are characterized by means of their relations of double domination. The main purpose of this paper is to transfer these results to general monoids. The important means will be certain relations, which we shall study in detail.

Keywords: monoid, submonoid, pregrammar, prelanguage, relation of left domination of a prelanguage, relation of left double, domination of a prelanguage

Citation: Fundamenta Informaticae, vol. 46, no. 4, pp. 343-348, 2001

Authors: Ronse, Christian | Serra, Jean

Article Type: Research Article

Abstract: This paper generalizes the notion of symmetrical neighbourhoods, which have been used to define connectivity in the case of sets, to the wider framework of complete lattices having a sup-generating family. Two versions (weak and strong) of the notion of a symmetrical dilation are introduced, and they are applied to the generation of "connected components" from the so-called "geodesic dilations". It turns out that any "climbing" "weakly symmetrical" extensive dilation induces a "geodesic" connectivity. When the …lattice is the one of subsets of a metric space, the connectivities which are obtained in this way may coincide with the usual ones under some conditions, which are clarified. The abstract theory can be applied to grey-level and colour images, without any assumption of translation-invariance of operators. Show more

Keywords: neighbourhood, symmetry, connectivity, geodesy, complete, lattices, mathematical morphology, metrics

Citation: Fundamenta Informaticae, vol. 46, no. 4, pp. 349-395, 2001