Fundamenta Informaticae - Volume 12, issue 2

Article Type: Other

DOI: 10.3233/FI-1989-12201

Citation: Fundamenta Informaticae, vol. 12, no. 2, pp. i-vii, 1989

Authors: Michalewicz, Zbigniew | Yeo, Alvin

Article Type: Research Article

Abstract: In the conceptual design of relational databases one of the main goals is to create a conceptual scheme, which minimize redundancies and eliminate deletion and addition anomalies, i.e. to create relation schemes in some good normal form. The study of relational databases has produced a host of normal forms: 2NF, 3NF, BCNF, Elementary-Key Normal Form, 4NF, Weak 4NF, PJ/NF, DK/NF, LTKNF, (3,3)NF, etc . There are two features which characterize these normal forms. First, they consider each relation separately. We believe that a normal form (which reflects the goodness of the conceptual design) should be related to the …whole conceptual scheme. Second, the usefullness of all normal forms in relational database design have been based on the assumption that a data definition language (DDL) of a database management system (DBMS) is able to enforce key dependencies. However, different DDLs have different capabilities in defining constraints. In this paper we will discuss the design of conceptual relational schemes in general. We will also define a good normal form (GNF) which requires a minimally rich DDL; this normal form is based only on a primitive concept of constraints. We will not, however, discuss the normalization process itself – how one might, if possible, convert a relation scheme that is not in some normal form into a collection of relation schemes each of which is in that normal form. Show more

DOI: 10.3233/FI-1989-12202

Citation: Fundamenta Informaticae, vol. 12, no. 2, pp. 129-138, 1989

Authors: Weijland, W.P.

Article Type: Research Article

Abstract: An algebraical theory called ASP is presented, describing synchronous cooperation of processes. The theory ASP was first mentioned in BERGSTRA & KLOP [4] as an alternative for the theory ACP, which works with asynchronous cooperation (see also in [5]). One of the main differences between ASP, as it is presented here, and the algebraic theory SCCS of MILNER [9] is the representation of parallelism, which is done by considering a computation step as a vector, each component of which represents an atomic action on a corresponding channel. This paper concludes with an example, to give an idea how to …work with ASP. Show more

DOI: 10.3233/FI-1989-12203

Citation: Fundamenta Informaticae, vol. 12, no. 2, pp. 139-162, 1989

Authors: Moser, Louise E.

Article Type: Research Article

Abstract: A decision procedure is given for determining the validity of unquantified formulas in graph theory. The procedure, which decides equality and containment relations for vertex, edge, and graph terms, reduces to a decision procedure for propositional calculus. The correctness of the procedure is proved using model theory based on the axioms for graph theory provided. The complexity of the algorithm and its limitations are discussed.

DOI: 10.3233/FI-1989-12204

Citation: Fundamenta Informaticae, vol. 12, no. 2, pp. 163-180, 1989

Authors: Zaionc, Marek

Article Type: Research Article

Abstract: The purpose of this work is to show the methods of representing higher order boolean functionals in the simple typed λ calculus. In the paper is presented an algorithm for construction the λ representation of a functional given by generalized truth table. This technique is useful especially in functional programming languages such as ML in which functionals are expressed in the form of typed λ terms. Also λ representability of higher order functionals in many valued logics is discussed.

Keywords: boolean operations, typed λ calculus, representability

DOI: 10.3233/FI-1989-12205

Citation: Fundamenta Informaticae, vol. 12, no. 2, pp. 181-189, 1989

Authors: Szalas, Andrzej | Petermann, Uwe

Article Type: Research Article

Abstract: We present a temporal logic suitable for axiomatic specification of properties of distributed systems. The temporal logic considered is first-order with atnext operators interpreted as local modalities. Its semantics, different from those provided in other approaches, does not rely on a succesor relation in a set of global states, and mirrors the nature of distributed computations. The logic introduced is applied to axiomatization of a process communication scheme based on sending and handling interrupts.

Keywords: axiom system, communication mechanism, distributed system, interrupt, semantic consequence, semantics of concurrent computations, temporal logic

DOI: 10.3233/FI-1989-12206

Citation: Fundamenta Informaticae, vol. 12, no. 2, pp. 191-203, 1989

Authors: Becker, Bernd | Kolla, Reiner

Article Type: Research Article

Abstract: In this paper we present the design of a novel optimal time adder: the conditional carry adder. In order to perform addition a tree-like combination of multiplexer cells is used in the carry computation part. We show that, for the complete conditional carry adder, this results in an overall computation time which seems to be substantially shorter than for any other known (optimal time) adder (e.g. carry look ahead adders ([5]) or conditional sum adders ([12])). The second part of this paper contains a uniform approach to the computation of the carry function resulting in seven different classes of optimal …time adders. It is shown that the conditional carry adder and the carry look ahead adder are representatives of two different classes. While section 1 defines the conditional carry adder and proposes a realization which is very time efficient, section 2 provides the possibility to compare this choice with other possible realizations and to choose a different design depending e.g. on specific properties of a given technology. Show more

DOI: 10.3233/FI-1989-12207

Citation: Fundamenta Informaticae, vol. 12, no. 2, pp. 205-220, 1989

Authors: Baeten, J.C.M. | Van Glabbeek, R.J.

Article Type: Research Article

Abstract: In this paper, we combine the hidden step η of the authors’ paper [2] with the empty process ε of VRANCKEN [12] and the authors’ [3]. We formulate a system ACPc, which is a conservative extension of the systems ACPη , ACP√ , but also of ACPτ . This is a general system, in which most relevant issues can be discussed. Abstraction from internal steps can be achieved in two ways, in two stages: we can abstract to the hidden step η , and then from η to Milner’s silent step τ .

DOI: 10.3233/FI-1989-12208

Citation: Fundamenta Informaticae, vol. 12, no. 2, pp. 221-241, 1989

Authors: Marek, W.

Article Type: Research Article

Abstract: We investigate the operator producing a stable theory out of its objective part (A stable theory is a set of beliefs of a rational agent). We characterize the objective parts of stable theories. Finally, we discuss the predicate calculus case.

DOI: 10.3233/FI-1989-12209

Citation: Fundamenta Informaticae, vol. 12, no. 2, pp. 243-254, 1989

Authors: Marek, W. | Truszczynski, M.

Article Type: Research Article

Abstract: We investigate solutions of fixed point equations related to the negation as “failure to prove” rule, and show their relevance to minimal models.

Keywords: Closed World Assumption, negation as failure to prove, logic, fixed points

DOI: 10.3233/FI-1989-12210

Citation: Fundamenta Informaticae, vol. 12, no. 2, pp. 255-267, 1989