Fundamenta Informaticae - Volume 12, issue 3

Article Type: Other

DOI: 10.3233/FI-1989-12301

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

Authors: Suchenek, Marek A.

Article Type: Research Article

Abstract: This paper concerns two aspects of incomplete information in data bases: - computations of answers to queries which are externally interpreted in some incomplete first-order structures with dependencies, and - the proper treatment of modal operators in such structures. We introduce the notion of an incomplete first-order structure with dependencies which seems to be an adequate model of data bases with incomplete information. We show that the widely accepted implicit assumption that first-order models (of a data base) have a unique domain, has no first-order consequences if the set of premises (represented in the data base) …contains only a finite amount of information explicitly involving the elements of this domain. This observation allows us to evaluate the degree of unsolvability of the problem of answering externally interpreted queries in the incomplete first-order structures. Moreover, we propose a forcing-based definition of the internal interpretation of modal queries in such structures, and investigate some of the properties of this interpretation. Show more

DOI: 10.3233/FI-1989-12302

Citation: Fundamenta Informaticae, vol. 12, no. 3, pp. 269-287, 1989

Authors: De Frutos Escrig, David | Indermark, Klaus

Article Type: Research Article

Abstract: We consider three different meanings of a non-deterministic Ianov-scheme with respect to infinite computations: trace-semantics, Plotkin-semantics, and Smyth-semantics. The corresponding equivalence relations are shown to be decidable.

Keywords: Program schemes, non-determinism, equivalence relations, decidability

DOI: 10.3233/FI-1989-12303

Citation: Fundamenta Informaticae, vol. 12, no. 3, pp. 289-315, 1989

Authors: Rine, David C.

Article Type: Research Article

Abstract: Partitioning and allocating of software components are two important parts of software design in distributed software engineering. This paper presents two general algorithms that can, to a limited extent, be used as tools to assist in partitioning software components represented as objects in a distributed software design environment. One algorithm produces a partition (equivalence classes) of the objects, and a second algorithm allows a minimum amount of redundancy. Only binary relationships of actions (use or non-use) are considered in this paper.

Keywords: distributed processing, computing in parallel, partitioning and allocating algorithms, object-oriented development

DOI: 10.3233/FI-1989-12304

Citation: Fundamenta Informaticae, vol. 12, no. 3, pp. 317-356, 1989

Authors: Batarekh, Aida | Subrahmanian, V.S.

Article Type: Research Article

Abstract: Given a first order language L , and a notion of a logic L w.r.t. L , we investigate the topological properties of the space of L -structures for L . We show that under a topology called the query topology which arises naturally in logic programming, the space of L -models (where L is a decent logic ) of any sentence (set of clauses) in L may be regarded as a (closed, compact) T 4 -space. We then investigate the properties of maps from structures to structures. …Our results allow us to apply various well-known results on the fixed-points of operators on topological spaces to the semantics of logic programming – in particular, we are able to derive necessary and sufficient topological conditions for the completion of covered general logic programs to be consistent. Moreover, we derive sufficient conditions guaranteeing the consistency of program completions, and for logic programs to be determinate. We also apply our results to characterize consistency of the unions of program completions. Show more

DOI: 10.3233/FI-1989-12305

Citation: Fundamenta Informaticae, vol. 12, no. 3, pp. 357-399, 1989

Authors: Novotný, Miroslav

Article Type: Research Article

Abstract: In [10] a reducing operator ρ was defined assigning a normed generalized grammar ρ (G) to any normed generalized grammar G in such a way that ρ (G) is in a certain sense less or equal to G and that both G and ρ (G) generate the same language. To any nontrivial language (V,L) a normed generalized grammar Gr(V,L) is assigned. Then ρ (Gr(V,L)) is proved to be a normed grammar if and only if (V,L) is a so called agreeable language.

Keywords: normed generalized grammar, normed grammar, reducing operator, permitting triple with derivatives, canonical permitting triple with derivatives, agreeable language

DOI: 10.3233/FI-1989-12306

Citation: Fundamenta Informaticae, vol. 12, no. 3, pp. 401-411, 1989

Authors: Banachowski, Lech

Article Type: Research Article

DOI: 10.3233/FI-1989-12307

Citation: Fundamenta Informaticae, vol. 12, no. 3, pp. 413-425, 1989