Fundamenta Informaticae - Volume 144, issue 1

Authors: Alexandru, Andrei | Ciobanu, Gabriel

Article Type: Research Article

Abstract: We present a theory of abstract interpretations in the framework of invariant sets by translating the notions of lattices and Galois connections into this framework, and presenting their properties in terms of finitely supported objects. We introduce the notions of invariant correctness relation and invariant representation function, emphasize an equivalence between them, and establish the relationship between these notions and invariant Galois connections. Finally, we provide some widening and narrowing techniques in order to approximate the least fixed points of finitely supported transition functions.

Keywords: Invariant sets, finitely supported object, invariant Galois connection, abstract analysis

DOI: 10.3233/FI-2016-1321

Citation: Fundamenta Informaticae, vol. 144, no. 1, pp. 1-22, 2016

Authors: Mrozek, Ireneusz | Yarmolik, Vyacheslav

Article Type: Research Article

Abstract: Controlled random tests, methods of their generation, as well as their application to the testing of both hardware and software systems are discussed. Available evidences suggest that high computational complexity is one of the main drawback of these methods. Therefore we propose a technique to overcome this problem. In the paper, we introduce the concept of multiple controlled random tests (MCRT ) and examine various numerical characteristics in terms of the development of those tests. We prove the effectiveness of the Euclidean distance, as well as we propose an easy computational method of its calculation, in the process of constructing …MCRT . The presented approach is evaluated through the experimental study in the context of testing of Random Access Memory (RAM). Show more

Keywords: antirandom tests, controlled random tests, multiple tests, RAM testing

DOI: 10.3233/FI-2016-1322

Citation: Fundamenta Informaticae, vol. 144, no. 1, pp. 23-43, 2016

Authors: Radzikowska, Anna Maria

Article Type: Research Article

Abstract: Duality via truth is a kind of correspondence between a class of algebras and a class of relational systems (frames). These classes are viewed as two kinds of semantics for some logic: algebraic semantics and Kripke-style semantics, respectively. Having defined the notion of truth, the duality principle states that a sequent/formula is true in one semantics if and only if it is true in the other one. In consequence, the algebras and their corresponding frames express equivalent notion of truth. In this paper we develop duality via truth between modal algebras based on De Morgan lattices and their corresponding frames. …Some axiomatic extensions of these algebras are considered. Basing on these results we present duality via truth between some classes of lattice-based information algebras and their corresponding frames. Show more

Keywords: Algebraic semantics, Kripke-style semantics, Modal algebras, De Morgan lattices, Information algebras, Duality theory

DOI: 10.3233/FI-2016-1323

Citation: Fundamenta Informaticae, vol. 144, no. 1, pp. 45-75, 2016

Authors: Song, Bosheng | Pan, Linqiang | Pérez-Jiménez, Mario J.

Article Type: Research Article

Abstract: Tissue P systems are a class of distributed parallel computing devices inspired by biochemical interactions between cells in a tissue-like arrangement, where objects can be exchanged by means of communication channels. In this work, inspired by the biological facts that the movement of most objects through communication channels is controlled by proteins and proteins can move through lipid bilayers between cells (if these cells are fused), we present a new class of variant tissue P systems, called tissue P systems with protein on cells, where multisets of objects (maybe empty), together with proteins between cells are exchanged. The computational power …of such P systems is studied. Specifically, an efficient (uniform) solution to the SAT problem by using such P systems with cell division is presented. We also prove that any Turing computable set of numbers can be generated by a tissue P system with protein on cells. Both of these two results are obtained by such P systems with communication rules of length at most 4 (the length of a communication rule is the total number of objects and proteins involved in that rule). Show more

Keywords: Bio-inspired computing, Membrane computing, Tissue P system, Cell protein, Cell division, Universality

DOI: 10.3233/FI-2016-1324

Citation: Fundamenta Informaticae, vol. 144, no. 1, pp. 77-107, 2016