Fundamenta Informaticae - Volume 71, issue 2-3

Authors: Banerjee, Mohua

Article Type: Research Article

Abstract: Pawlak had proposed the notion of rough truth in 1987 [16]. The article takes a fresh look at this "soft" truth, and presents a formal system L_R , that is shown to be sound and complete with respect to a semantics determined by this notion. L_R is based on the modal logic S5. Notable is the rough consequence relation defining L_R (a first version introduced in [9]), and rough consistency (also …introduced in [9]), used to prove the completeness result. The former is defined in order to be able to derive roughly true propositions from roughly true premisses in an information system. The motivation for the latter stems from the observation that a proposition and its negation may well be roughly true together. A characterization of L_R -consequence shows that the paraconsistent discussive logic J of Jaśkowski is equivalent to L_R . So, L_R , developed from a totally independent angle, viz. that of rough set theory, gives an alternative formulation to this well-studied logic. It is further observed that pre-rough logic [3] and 3-valued Łukasiewicz logic are embeddable into L_R . Show more

Keywords: Rough sets, Modal logic S5, Consequence relation, Consistency

Citation: Fundamenta Informaticae, vol. 71, no. 2-3, pp. 139-151, 2006

Authors: Bergstra, J.A. | Middelburg, C.A.

Article Type: Research Article

Abstract: In a previous paper, we developed an algebraic theory about threads and multi-threading based on the assumption that a deterministic interleaving strategy determines how threads are interleaved. The theory includes interleaving operators for a number of plausible deterministic interleaving strategies. The interleaving of different threads constitutes a multi-thread. Several multi-threads may exist concurrently on a single host in a network, several host behaviors may exist concurrently in a single network on the …internet, etc. In the current paper, we assume that the above-mentioned kind of interleaving is also present at these other levels. We extend the theory developed so far with features to cover the multi-level case. We use the resulting theory to develop a simplified formal representation schema of systems that consist of several multi-threaded programs on various hosts in different networks. We also investigate the connections of the resulting theory with the algebraic theory of processes known as ACP. Show more

Keywords: thread, multi-thread, host, network, service, thread algebra, strategic interleaving, thread-service composition, delayed processing, exception handling, formal design prototype, process algebra

Citation: Fundamenta Informaticae, vol. 71, no. 2-3, pp. 153-182, 2006

Authors: Calimeri, Francesco | Faber, Wolfgang | Pfeifer, Gerald | Leone, Nicola

Article Type: Research Article

Abstract: Disjunctive Logic Programming (DLP) is an advanced formalism for knowledge representation and reasoning. The language of DLP is very expressive and supports the representation of problems of high computational complexity (specifically, all problems in the complexity class Σ^p_2 =NP^{NP} ). The DLP encoding of a large variety of problems is often very concise, simple, and elegant. In this paper, we explain the computational process commonly performed by DLP systems, with a focus …on search space pruning, which is crucial for the efficiency of such systems. We present two suitable operators for pruning (Fitting's and Well-founded), discuss their peculiarities and differences with respect to efficiency and effectiveness. We design an intelligent strategy for combining the two operators, exploiting the advantages of both. We implement our approach in DLV – the state-of-the-art DLP system – and perform some experiments. These experiments show interesting results, and evidence how the choice of the pruning operator affects the performance of DLP systems. Show more

Keywords: Artificial Intelligence, Disjunctive Logic Programming, DLP, Non-Monotonic Reasoning, DLP Computation

Citation: Fundamenta Informaticae, vol. 71, no. 2-3, pp. 183-214, 2006

Authors: Chang, Chin-Chen | Chen, Guei-Mei | Hu, Yu-Chen

Article Type: Research Article

Abstract: A novel method for the compression of the index table of vector quantization (VQ) is proposed in this paper. This method is designed based on the observation that neighboring image blocks are highly correlated. In other words, VQ-encoded neighboring image blocks tend to have similar indices if the codebook used in VQ is previously sorted by the principal component analysis technique. According to this characteristic, we find the same or similar indices around the current processing …index to process it. In addition, the pre-statistics technique is employed to gather differences that appear most often in the index table. Simulation results indicate that the newly proposed scheme achieves significant reduction of bit rate without losing any image quality by the original VQ encoding. Show more

Citation: Fundamenta Informaticae, vol. 71, no. 2-3, pp. 215-227, 2006

Authors: Czyzowicz, Jurek | Kowalski, Dariusz | Markou, Euripides | Pelc, Andrzej

Article Type: Research Article

Abstract: A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node, without leaving any trace. We consider the task of locating a black hole in a (partially) synchronous network, assuming an upper bound on the time of any edge traversal by an agent. The minimum number of agents capable to identify a black hole is two. For a given graph and given starting node we are interested …in the fastest possible black hole search by two agents, under the general scenario in which some subset of nodes is safe and the black hole can be located in one of the remaining nodes. We show that the problem of finding the fastest possible black hole search scheme by two agents is NP-hard, and we give a 9.3-approximation for it. Show more

Keywords: approximation algorithm, black hole, graph, mobile agent, NP-hard problem

Citation: Fundamenta Informaticae, vol. 71, no. 2-3, pp. 229-242, 2006

Authors: van Hee, Kees | Sidorova, Natalia | Voorhoeve, Marc

Article Type: Research Article

Abstract: We study concurrent processes modelled as workflow Petri nets extended with resource constrains. Resources are durable units that can be neither created nor destroyed: they are claimed during the handling procedure and then released again. Typical kinds of resources are manpower, machinery, computer memory. We define structural criteria based on traps and siphons for the correctness of workflow nets with resource constraints. We also extend the soundness notion for workflow nets to the workflow nets with …resource constraints; extra conditions concern the durability of resources. We prove some properties of sound resource-constrained workflow nets. Show more

Keywords: Petri nets, concurrency, workflow, resources, verification

Citation: Fundamenta Informaticae, vol. 71, no. 2-3, pp. 243-257, 2006

Authors: Iliopoulos, Costas S. | Makris, Christos | Panagis, Yannis | Perdikuri, Katerina | Theodoridis, Evangelos | Tsakalidis, Athanasios

Article Type: Research Article

Abstract: In this paper we introduce the Weighted Suffix Tree, an efficient data structure for computing string regularities in weighted sequences of molecular data. Molecular Weighted Sequences can model important biological processes such as the DNA Assembly Process or the DNA-Protein Binding Process. Thus pattern matching or identification of repeated patterns, in biological weighted sequences is a very important procedure in the translation of gene expression and regulation. We present time and space efficient algorithms for …constructing the weighted suffix tree and some applications of the proposed data structure to problems taken from the Molecular Biology area such as pattern matching, repeats discovery, discovery of the longest common subsequence of two weighted sequences and computation of covers. Show more

Keywords: Molecular Weighted Sequences, Suffix Tree, Pattern Matching, Identifications of repetitions, Covers

Citation: Fundamenta Informaticae, vol. 71, no. 2-3, pp. 259-277, 2006

Authors: Ionescu, Mihai | Păun, Gheorghe | Yokomori, Takashi

Article Type: Research Article

Abstract: This paper proposes a way to incorporate the idea of spiking neurons into the area of membrane computing, and to this aim we introduce a class of neural-like P systems which we call spiking neural P systems (in short, SN P systems). In these devices, the time (when the neurons fire and/or spike) plays an essential role. For instance, the result of a computation is the time between the moments when a specified neuron spikes. Seen as number computing …devices, SN P systems are shown to be computationally complete (both in the generating and accepting modes, in the latter case also when restricting to deterministic systems). If the number of spikes present in the system is bounded, then the power of SN P systems falls drastically, and we get a characterization of semilinear sets. A series of research topics and open problems are formulated. Show more

Keywords: Spiking neurons, membrane computing, Turing computability, semilinear set

Citation: Fundamenta Informaticae, vol. 71, no. 2-3, pp. 279-308, 2006

Authors: De Loof, Karel | De Meyer, Hans | De Baets, Bernard

Article Type: Research Article

Abstract: In this paper, we demonstrate how some simple graph counting operations on the ideal lattice representation of a partially ordered set (poset)P allow for the counting of the number of linear extensions of P, for the random generation of a linear extension of P, for the calculation of the rank probabilities for every x∈P, and, finally, for the calculation of the mutual rank probabilities Prob(x>y) for every (x,y)∈P^2 . We show that all …linear extensions can be counted and a first random linear extension can be generated in O(∣I(P)∣·w(p)) time, while every subsequent random linear extension can be obtained in O(∣P∣·w(P)) time, where ∣I(P)∣ denotes the number of ideals of the poset P and w(P) the width of the poset P. Furthermore, we show that all rank probability distributions can be computed in O(∣I(P)∣·w(P)) time, while the computation of all mutual rank probabilities requires O(∣I(P)∣·∣P∣·w(P)) time, to our knowledge the fastest exact algorithms currently known. It is well known that each of the four problems described above resides in the class of #P-complete counting problems, the counterpart of the NP-complete class for decision problems. Since recent research has indicated that the ideal lattice representation of a poset can be obtained in constant amortized time, the stated time complexity expressions also cover the time needed to construct the ideal lattice representation itself, clearly favouring the use of our approach over the standard ap-proach consisting of the exhaustive enumeration of all linear extensions. Show more

Keywords: poset, ideal lattice, random linear extension, number of linear extensions, rank probability distribution, mutual rank probabilities

Citation: Fundamenta Informaticae, vol. 71, no. 2-3, pp. 309-321, 2006

Authors: Peters, James F. | Henry, Christopher

Article Type: Research Article

Abstract: This paper introduces a rough set approach to reinforcement learning by swarms of cooperating agents. The problem considered in this paper is how to guide reinforcement learning based on knowledge of acceptable behavior patterns. This is made possible by considering behavior patterns of swarms in the context of approximation spaces. Rough set theory introduced by Zdzisław Pawlak in the early 1980s provides a ground for deriving pattern-based rewards within approximation spaces. Both conventional and …approximation space-based forms of reinforcement comparison and the actor-critic method as well as two forms of the off-policy Monte Carlo learning control method are investigated in this article. The study of swarm behavior by collections of biologically-inspired bots is carried out in the context of an artificial ecosystem testbed. This ecosystem has an ethological basis that makes it possible to observe and explain the behavior of biological organisms that carries over into the study of reinforcement learning by interacting robotic devices. The results of ecosystem experiments with six forms of reinforcement learning are given. The contribution of this article is the presentation of several viable alternatives to conventional reinforcement learning methods defined in the context of approximation spaces. Show more

Keywords: Approximation space, ecosystem, ethology, Monte Carlo method, reinforcement learning, rough sets, swarm

Citation: Fundamenta Informaticae, vol. 71, no. 2-3, pp. 323-349, 2006