Fundamenta Informaticae

In this paper, we study indiscernibility relations and complementarity relations in information systems. The first-order characterization of indiscernibility and complementarity is obtained through a duality result between information systems and certain structures of relational type characterized by first-order conditions. The modal analysis of indiscernibility and complementarity is performed through a modal logic which modalities correspond to indiscernibility relations and complementarity relations in information systems.

The article considers the representation of Boolean functions in the form of decision trees. It presents the bounds on average time complexity of decision trees for all classes of Boolean functions that are closed over substitution, and the insertion and deletion of unessential variables (the structure of these classes is described in the book by Jablonsky, Gavrilov and Kudriavtzev [5]. The obtained results are compared with the results developed by Moshkov in [6] that describe the worst case time complexity of decision trees.

After a sketchy historical account on the question of self-describeness and self-reproduction, and after discussing the definition of suitable encodings for self-describeness, we give the construction of several self-describing Turing machines, namely self-describing machines with, respectively, 350, 267, 224 and 206 instructions.

The notions of an exact as well as a rough set are well--grounded as basic notions in Rough Set Theory [13]. They are however defined in the setting of a finite information system i.e. an information system having finite numbers of objects as well as attributes. In theoretical studies e.g. of topological properties of rough sets [16], one has to trespass this limitation and to consider information systems with potentially unbound number of attributes. In such setting, the notions of rough and exact sets may be defined in terms of topological operators of interior and closure with respect to an appropriate topology [16] following the ideas from the finite case cf. e.g. [14], where it is noticed that in the finite case rough-set-theoretic operators of lower and upper approximation are identical with the interior, respectively, closure operators in topology induced by equivalence classes of the indiscernibility relation. Extensions of finite information systems are also desirable from application point of view in the area of Knowledge Discovery and Data Mining, when demands of e.g. mass collaboration and/or huge experimental data e.g. in genomic studies [2,17], call for need of working with large data tables so the sound theoretical generalization of these cases is an information system with the number of attributes not bound in advance by a fixed integer i.e. an information system with countably but infinitely many attributes. In large information systems, a need arises for qualitative measures of complexity of concepts involved free of parameters, cf. e.g. applications for the Vapnik–Czervonenkis dimension [1].We study here in the theoretical setting of infinite information system a proposal to apply fractal dimensions suitably modified as measures of concept complexity. In the finite case, exact sets form a field of sets E cf. e.g. [14]. Clearly, from topological point of view E is a compact metric space under the discrete metric on equivalence classes of the indiscernibility relation. The question poses itself, whether it is possible to define exact sets in the setting of an infinite information system in such a way that the space of exact sets E_∞ will be a compact metric space and a field of sets as well. We study in this note a way to define exact and rough sets which stems from the orthodox notion of an approximation. We apply to this end the notion of a fractal dimension adopted to the case of an information system i.e. rid of the geometric content and underlying metric characterization. We introduce notions of a lower and an upper fractal dimensions and we define exact sets as those sets for which the two dimensions coincide; otherwise, we declare the set as rough. It turns out that exact sets defined in this way extend the classical notion of an exact set and as in the classical finite case they form a field of sets. From topological point of view, exact sets form a compact metric space under the metric D defined originally for topological rough sets [16] and extended here over topological exact sets as well.

MC games are infinite duration two-player games played on graphs. Deciding the winner in MC games is equivalent to the the modal mu-calculus model checking. In this article we provide a linear time algorithm for a class of MC games. We show that, if all cycles in each strongly connected component of the game graph have at least one common vertex, the winner can be found in linear time. Our results hold also for parity games, which are equivalent to MC games.

This paper presents a new model of computation that differs from prior models in that it emphasizes data over flow control, has no named variables and has an object-oriented flavor. We prove that this model is a complete and confluent acceptable programming system and has a usable type theory. A new data synchronization primitive is introduced in order to achieve the above properties. Subtle variations of the model are shown to fall short of having all these necessary properties.

In [25] a straightforward extension of the process algebra μCRL was proposed to explicitly deal with time. The process algebra μCRL has been especially designed to deal with data in a process algebraic context. Using the features for data, only a minor extension of the language was needed to obtain a very expressive variant of time. But [25] contains syntax, operational semantics and axioms characterising timed μCRL. It did not contain an in depth analysis of theory of timed μCRL. This paper fills this gap, by providing soundness and completeness results. The main tool to establish these is a mapping of timed to untimed μCRL and employing the completeness results obtained for untimed μCRL.