Fundamenta Informaticae - Volume 11, issue 1

Article Type: Other

DOI: 10.3233/FI-1988-11101

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

Authors: Rowicki, Andrzej

Article Type: Research Article

Abstract: The purpose of the paper is to consider an algorithm for preemptive scheduling for two-processor systems with identical processors. Computations submitted to the systems are composed of dependent tasks with arbitrary execution times and contain no loops and have only one output. We assume that preemptions times are completely unconstrained, and preemptions consume no time. Moreover, the algorithm determines the total execution time of the computation. It has been proved that this algorithm is optimal, that is, the total execution time of the computation (schedule length) is minimized.

Keywords: execution time, network, nonpreemptive scheduling, preemptive scheduling, reduct, reduction

DOI: 10.3233/FI-1988-11102

Citation: Fundamenta Informaticae, vol. 11, no. 1, pp. 1-19, 1988

Authors: Urzyczyn, Pawel

Article Type: Research Article

Abstract: We discuss the computational power of programs with boolean (propositional) push-down stores and arrays, and the expressive power of logics based on these programs. In particular we show that over unary structures, the mentioned logics occur to be equivalent to their “algebraic counterparts.

DOI: 10.3233/FI-1988-11103

Citation: Fundamenta Informaticae, vol. 11, no. 1, pp. 21-40, 1988

Authors: Michalewicz, Zbigniew | Yeo, Anthony

Article Type: Research Article

Abstract: The goal of statistical databases is to provide statistics about groups of individuals while protecting their privacy. Sometimes. by correlating enough statistics, sensitive data about individual can be inferred. The problem of protecting against such indirect disclosures of confidential data is called the inference problem and a protecting mechanism – an inference control. A good inference control mechanism should be effective (it should provide security to a reasonable extent) and feasible (a practical way exists to enforce it). At the same time it should retain the richness of the information revealed to the users. During the last few years several …techniques were developed for controlling inferences. One of the earliest inference controls for statistical databases restricts the responses computed over too small or too large query-sets. However, this technique is easily subverted. In this paper we propose a new query-set size inference control which is based on the idea of multiranges and has better performance then the original one. Show more

DOI: 10.3233/FI-1988-11104

Citation: Fundamenta Informaticae, vol. 11, no. 1, pp. 41-48, 1988

Authors: Szalas, Andrzej

Article Type: Research Article

Abstract: In this paper we deal with a well known problem of specifying abstract data types. Up to now there were many approaches to this problem. We follow the axiomatic style of specifying abstract data types (cf. e.g. [1, 2, 6, 8, 9, 10]). We apply, however, the first-order temporal logic. We introduce a notion of first-order completeness of axiomatic specifications and show a general method for obtaining first-order complete axiomatizations. Some examples illustrate the method.

Keywords: abstract data type, consistency, first-order completeness, representation theorem, temporal logic

DOI: 10.3233/FI-1988-11105

Citation: Fundamenta Informaticae, vol. 11, no. 1, pp. 49-63, 1988

Authors: Winkowski, Jozef

Article Type: Research Article

Abstract: A new semantics for communicating processes is introduced which modifies the ideas of Milner (1980) and Winskel (1982, 1983, and 1986). This semantics, inspired by a model of Staples and Nguyen (1985) for nondeterministic data flow, allows one to avoid explicit representation of hidden events of processes, which simplifies the concept of observation equivalence of processes. It offers also a framework to cope with indivisible sets of communication events.

Keywords: process, state, event, configuration, communication, communication structure, sum, prefixing, composition, restriction, renaming, approximation order, fixed-point, equivalence

DOI: 10.3233/FI-1988-11106

Citation: Fundamenta Informaticae, vol. 11, no. 1, pp. 65-115, 1988