Fundamenta Informaticae - Volume 93, issue 4

Authors: Czelakowski, Janusz

Article Type: Research Article

Abstract: Theorem 3.7 of [1] is corrected. Two coherence principles and the ultrafilter property for partial functions contained in a relation are formulated. The equivalence of the coherent principles with AC and the equivalence of the ultrafilter property with BPI is shown.

Keywords: coherence principle, ultrafilter property

DOI: 10.3233/FI-2009-107

Citation: Fundamenta Informaticae, vol. 93, no. 4, pp. 353-356, 2009

Authors: Dinu, Liviu P.

Article Type: Research Article

Abstract: In this paper we investigate insertion grammars and explore their capacity to generate words parallelly by introducing parallel derivation (where more than one rule can be applied to the string in parallel) and maximum parallel derivation (where as many rules as possible are applied to the string in parallel). We compare the generative power of these grammars with context sensitive and context free grammars and with different variants of contextual grammars. We apply these grammars to …syllabification in Romanian and provide arguments that they can also be used in a cognitive perspective. Show more

Keywords: insertion grammars, parallel derivation, contextual grammars, parallel syllabification

DOI: 10.3233/FI-2009-108

Citation: Fundamenta Informaticae, vol. 93, no. 4, pp. 357-369, 2009

Authors: van Glabbeek, Rob | Luttik, Bas | Trčka, Nikola

Article Type: Research Article

Abstract: We consider the relational characterisation of branching bisimilarity with explicit divergence. We prove that it is an equivalence and that it coincides with the original definition of branching bisimilarity with explicit divergence in terms of coloured traces. We also establish a correspondence with several variants of an action-based modal logic with until- and divergence modalities.

DOI: 10.3233/FI-2009-109

Citation: Fundamenta Informaticae, vol. 93, no. 4, pp. 371-392, 2009

Authors: Lei, Yuxia | Sui, Yuefei | Cao, Cungen

Article Type: Research Article

Abstract: Formal Concept Analysis (FCA) is a valid tool for data mining and knowledge discovery, which identifies conceptual structures from (formal) contexts. As many practical applications involve non-binary data, non-binary attributes are introduced via a many-valued context in FCA. In FCA, conceptual scaling provides a complete framework for transforming any many-valued context into a context, in which each non-binary attribute is given a scale, and the scale is a context. Each relation in relational databases is a …many-valued context of FCA. In this paper, we provide an approach toward normalizing scales, i.e., each scale can be represented by a nominal scale and/or a set of statements. One advantage of normalizing scales is to avoid generating huge (binary) derived relations. By the normalization, the concept lattice of a derived relation is reduced to a combination of the concept lattice of a derived nominal relation and a set of statements. Hence, without transforming a relation into a derived relation, one can not only determine concepts of the derived relation from concepts of given scales, but also determine concepts of the derived relation from concepts of a derived nominal relation and a set of statements. The connection between the concept lattice of a derived nominal relation and the concept lattice of a derived relation is also considered. Show more

Keywords: Relational databases, formal concept analysis, concept lattices, plain scaling, derived relations, normalized-scale relations

DOI: 10.3233/FI-2009-110

Citation: Fundamenta Informaticae, vol. 93, no. 4, pp. 393-409, 2009

Authors: Paszyński, Maciej

Article Type: Research Article

Abstract: The paper present the composite programmable (CP) graph grammar model of the selfadaptive hp Finite Element Method (hp-FEM) algorithm. The model incorporates the process of the initial mesh generation, direct solver execution, as well as mesh transformations resulting from selectedoptimal hp refinements. The computational mesh is represented by the CP-graph. The operations performed over the mesh are expressed by the graph grammar productions. The graph grammar model allows for the definition of the …computational tasks for the Partitioning, Communication, Agglomeration and Mapping (PCAM) method of the parallelization of the self-adaptive hp-FEM algorithm. Show more

Keywords: Graph grammar, Automatic hp adaptivity, Finite Element Method, Parallel computing

DOI: 10.3233/FI-2009-111

Citation: Fundamenta Informaticae, vol. 93, no. 4, pp. 411-434, 2009

Authors: Paszyński, Maciej

Article Type: Research Article

Abstract: The paper presents a general methodology for an efficient parallelization of the fully automatic hp-adaptive Finite Element Method (hp-FEM). The self-adaptive hp-FEM algorithm expressed in terms of the graph grammar productions is analyzed by utilizing the Partitioning Communication Agglomeration Mapping (PCAM) model. The computational tasks are defined over a graph model of the computational mesh. It is done for all parts of the algorithm: the generation of an initial mesh, direct solver (including the …integration and elimination of degrees of freedom), mesh transformations (including the h and p refinements), as well as the selection of the optimal refinements. The computation and communication complexities of the resulting parallel algorithms are analyzed. The paper is concluded with the sequence of massive parallel computations. From the performed tests it implies that the code scales well up to 200 processors. Show more

Keywords: Large scale parallel computations, Automatic hp adaptivity, Finite Element Method, Parallel solvers, 3D resistivity logging simulations

DOI: 10.3233/FI-2009-112

Citation: Fundamenta Informaticae, vol. 93, no. 4, pp. 435-457, 2009

Authors: Zhang, Ling | He, Fu-gui | Zhang, Yan-ping | Zhao, Shu

Article Type: Research Article

Abstract: The optimal path finding problem in weighted edge networks is an old and interesting one in many fields. There were many well-known algorithms to deal with that issue. But they were confronted with the high computational complexity while the network becoming larger. We present a hierarchical quotient space model based algorithm that reduces the computational complexity. The basic idea is the following. The nodes of a given network are partitioned with respect to the weights of …their adjacent edges. We construct a variety of coarser versions of the given network with new nodes corresponding to the blocks of partitions at various levels of granularity. They are called the quotient spaces (networks) of the original network. The construction of the (sub- )optimal path is then done incrementally, throughout the hierarchy of quotient networks. Since each version of the network is much simpler than the original one, especially of the coarsest spaces, the computational complexity is reduced. In this paper, we present the basic principles of the algorithm and its experimental comparison to other well-known algorithms. Show more

Keywords: The path finding, weighted network, granularity, quotient space, computational complexity

DOI: 10.3233/FI-2009-113

Citation: Fundamenta Informaticae, vol. 93, no. 4, pp. 459-469, 2009