Fundamenta Informaticae - Volume 83, issue 4

Authors: Farina, Fabio | Dennunzio, Alberto

Article Type: Research Article

Abstract: We propose a lattice model to describe a predator-prey system where two species with significantly different size are considered. The biological analogy we refer to is the predatory interaction between bacteria and viruses. We assume simple environmental effects altering the dynamics. Preys (bacteria) procreate by mitosis and they do not move. They may die because of natural causes or under the predation. The predation is the consequence of a diffusive phenomenon by the predators (viruses). Predators …grow in number by infection and by prey self-immunity diseases, and they die by starvation. Show more

Keywords: cellular automata, population dynamics, predator-prey systems

Citation: Fundamenta Informaticae, vol. 83, no. 4, pp. 337-353, 2008

Authors: Meghini, Carlo | Tzitzikas, Yannis | Spyratos, Nicolas

Article Type: Research Article

Abstract: We consider a general form of information sources, consisting of a set of objects classified by terms arranged in a taxonomy. The query-based access to the information stored in sources of this kind, is plagued with uncertainty, due, among other things, to the possible linguisticmismatch between the user and the object classification. To overcome this uncertainty in all situations in which the user is not finding the desired information and is not willing or able to …state a new query, the study proposes to extend the classification, in a way that is as reasonable as possible with respect to the original one. By equating reasonableness with logical implication, the sought extension turns out to be an explanation of the classification, captured by abduction. The problem of query evaluation on information sources extended in this way is studied and a polynomial time algorithm is provided for the general case, in which no hypothesis is made on the structure of the taxonomy. The algorithm is successively specialized on a most common kind of information sources, namely sources whose taxonomy can be represented as a directed acyclic graph. It is shown that query evaluation on extended sources is easier for this kind of sources. Finally, two applications of the method are presented, which capture very important aspects of information access: information browsing and query result ranking. Show more

Keywords: Logic-based abduction, information systems, algorithms

Citation: Fundamenta Informaticae, vol. 83, no. 4, pp. 355-387, 2008

Authors: Simson, Daniel | Wojewódzki, Mariusz

Article Type: Research Article

Abstract: We give an algorithmic solution in a simple combinatorial data of Birkhoff0s type problem studied in [22] and [25], for the category rep_{ft} (I,K[t]/(t^m )) of filtered I-chains of modules over the K-algebra K[t]/(t^m ) of K-dimension m <∞, where m ⩾ 2, I is a finite poset with a unique maximal element, and K is an algebraically closed field. The problem is to decide when the indecomposable objects of the category rep_{ft} (I,K[t]/(t^m )) …admit a classification by means of a suitable parametrisation. A complete solution of this important problem of the modern representation theory is contained in Theorems 2.4 and 2.5. We show that rep_{ft} (I,K[t]/(t^m )) admits such a classification if and only if (I,m) is one of the pairs of the finite list presented in Theorem 2.4, and such a classification does not exist for rep_{ft} (I,K[t]/(t^m )) if and only if the pair (I,m) is bigger than or equal to one of the minimal pairs of the finite list presented in Theorem 2.5. The finite lists are constructed by producing computer accessible algorithms and computational programs written in MAPLE and involving essentially the package CREP (see Section 4). On this way the lists are obtained as an effect of computer computations. In particular, the solution we get shows an importance of the computer algebra technique and computer computations in solving difficult and important problems of modern algebra. Show more

Keywords: poset, indecomposable linear representations, Birkhoff type problem, chains of vector spaces with linear operators, tame representation type, classification problems

Citation: Fundamenta Informaticae, vol. 83, no. 4, pp. 389-410, 2008

Authors: Subramanian, K.G. | Van, Do Long | Chandra, P. Helen | Quyen, Nghiem Do

Article Type: Research Article

Abstract: In this paper, we consider a class of two-dimensional array grammars, called parallel contextual array grammars, that extend the contextual operations on strings to arrays in a naturalway and generate languages of pictures of rectangular arrays. Several classes of these array grammars and the resulting families of picture languages are considered. Necessary conditions for picture languages to be contained in these classes are obtained and the relations between these families are also established.

Keywords: Formal languages, Picture languages, Array grammars, Contextual grammars

Citation: Fundamenta Informaticae, vol. 83, no. 4, pp. 411-428, 2008

Authors: Winter, Michael

Article Type: Research Article

Abstract: In this paper we develop an algebraic/categorical theory of bisimulations using relational methods. We define a general notion, which is capable of handeling different version of bisimilarity in a common context. Furthermore, the approach relates bisimulations with the notion of a covering known from the theory of graphs and their applications in topology and complex analysis.

Citation: Fundamenta Informaticae, vol. 83, no. 4, pp. 429-449, 2008

Authors: Balbiani, Philippe | Iliev, Petar | Vakarelov, Dimiter

Article Type: Research Article

Abstract: The natural modal logic corresponding to Pawlak's approximation spaces is S5, based on the box modality [R]A (and the diamond modality 〈R〉A=¬[R]¬A), where R is the corresponding indiscernibility relation of the approximation space S=(W,R). However the expressive power of S5 is too weak and, for instance, we cannot express that the space S has exactly n equivalence classes (we say that S is roughly-finite and n is the rough cardinality of S). For this reason we …extend the modal logic S5 with a new box modality [S]A, where S is the complement of R i.e. the discernibility relation of W. We propose a complete axiomatization, in this new language, of the logic ROUGH^n corresponding to the class of approximation spaces with rough cardinality n. We prove that the satisfiability problem for ROUGH^n is NP-complete. Show more

Citation: Fundamenta Informaticae, vol. 83, no. 4, pp. 451-464, 2008