Fundamenta Informaticae - Volume 11, issue 3

Article Type: Other

DOI: 10.3233/FI-1988-11301

Citation: Fundamenta Informaticae, vol. 11, no. 3, pp. i-vi, 1988

Authors: Wasilewska, Anita

Article Type: Research Article

Abstract: The concept of an information system, with manipulation based on the rough set theory, was introduced by Pawlak in 1982. The information system is defined by its set of objects, set of attributes, set of values of attributes, and a function, which maps the direct product of the first two sets onto the set of values of attributes. We introduce here, after [Pawlak 1985(1)], concepts of the decision rule, decision algorithm, static learning and describe the automatic procedures of deciding whether a given decision rule or decision algorithm is correct.

Keywords: information system, decision rule, decision aigorithm, static learning, syntactic decision procedure

DOI: 10.3233/FI-1988-11302

Citation: Fundamenta Informaticae, vol. 11, no. 3, pp. 219-239, 1988

Authors: Marek, W. | Rauszer, C.

Article Type: Research Article

Abstract: In this paper, we address the problem of query optimization in distributed databases. We show that horizontal partitions of databases, generated by products of equivalence relations, induce optimization techniques for the basic database operations (i.e., the selection, projection, and join operators). In the case of selection, our method allows for restriction of the number of blocks to be searched in the selection process and subsequent simplification of the selection formula at each block. For the natural join operation, we propose an algorithm that reduces the computation of fragments. Proofs of the correctness of our algorithms are also included.

DOI: 10.3233/FI-1988-11303

Citation: Fundamenta Informaticae, vol. 11, no. 3, pp. 241-265, 1988

Authors: Kutylowski, Miroslaw

Article Type: Research Article

Abstract: Chains of finite automata are considered. We show that if the lowest automaton in a chain controls movements of the common reading head then computing power of the chain is very limited. This is a generalization of Krohn-Rhodes theorem on one-way automata.

DOI: 10.3233/FI-1988-11304

Citation: Fundamenta Informaticae, vol. 11, no. 3, pp. 267-273, 1988

Authors: Katajainen, Jyrki | Koppinen, Markku

Article Type: Research Article

Abstract: Recently Rex Dwyer [D87] presented an algorithm which constructs a Delaunay triangulation for a planar set of N sites in O (N log log N) expected time and O (N log N) worst-case time. We show that a slight modification of his algorithm preserves the worst-case running time, but has only O (N) average running time. The methcxl is a hybrid which combines the cell technique with the divide-and-conquer algorithm of Guibas & Stolfi [GS85]. First a square grid of size about N by N is placed on the set …of sites. The grid forms about N cells (buckets), each of which is implemented as a list of the sites which fall into the corresponding square of the grid. A Delaunay triangulation of the generally rather few sites within each cell is constructed with the Guibas & Stolfi algorithm. Then the triangulations are merged, four by four, in a quadtree-like order. Show more

Keywords: Voronoi diagrams, Delaunay triangulations, bucket methods, quadtrees

DOI: 10.3233/FI-1988-11305

Citation: Fundamenta Informaticae, vol. 11, no. 3, pp. 275-288, 1988

Authors: Nieminen, Juhani

Article Type: Research Article

Abstract: The rough equality concept of Z. Pawlak is modified and the rough top and the rough bottom tolerance equalities are given and characterized. The same tolerance idea is applied also to black box notion introduced by Novotný and Pawlak; the concept thus obtained is called tolerance black box. Tolerance black boxes are characterized and their properties are described.

Keywords: Rough sets, tolerance relations, rough equalities, black boxes

DOI: 10.3233/FI-1988-11306

Citation: Fundamenta Informaticae, vol. 11, no. 3, pp. 289-296, 1988

Authors: Penczek, Wojciech

Article Type: Research Article

Abstract: A temporal logic for event structures based on a partial order frame of local states is presented. Two modalities, for causality and conflict, are introduced. Completeness of the axiom system is proved. The finite model property and decidability are discussed.

Keywords: temporal logic, partial order, concurrent system, inevitability, invariant, event structures

DOI: 10.3233/FI-1988-11307

Citation: Fundamenta Informaticae, vol. 11, no. 3, pp. 297-326, 1988