Fundamenta Informaticae - Volume 19, issue 3-4

Article Type: Other

DOI: 10.3233/FI-1993-193-401

Citation: Fundamenta Informaticae, vol. 19, no. 3-4, pp. i-vi, 1993

Authors: Sakai, Hiroshi

Article Type: Research Article

Abstract: A framework for Logic Programming with Incomplete Information is proposed. Recently, an important problem has been much discussed in the field of knowledge bases, logic programming and AI, namely how effectively we use information which may have incompleteness, especially disjunctive information. In order to express disjunctive information, we use the predicate symbol or m , where the superscript m implies its arity, and as arguments we put every disjunctive information in or m , which we call an or-type atom . Based on or-type atoms, we define a new language called or-type language. Logic Program …with Incomplete Information(LPII) is a subset of the or-type language. First, in a special case our framework is reduced to that of near-Horn prolog by Loveland and disjunctive logic programming by Minker. Then, we consider a general case, which is seen as an advancement from Lipski’s incomplete information system. In this case, we show the model intersection property, fixpoint theorem, the soundness and the completeness of a resolution which we call Box -resolution. Show more

DOI: 10.3233/FI-1993-193-402

Citation: Fundamenta Informaticae, vol. 19, no. 3-4, pp. 223-234, 1993

Authors: Rauszer, Cecylia M.

Article Type: Research Article

Abstract: Functional and multivalued dependencies are expressed in terms of special equivalence relations, called indiscernibility relations. Subsequently, an algebra of indiscernibility relations of a given relational database is introduced and examined. It is shown that a dependency holds in a database if and only if a corresponding algebraic formula is equal to the greatest element in the algebra. In addition, a formal deductive system, called D-logic is defined. This system corresponds to a fragment of non-classical logic. An equivalence theorem showing that D-logic describes, in an adequate way, properties of functional and multivalued dependencies is stated. D-logic and D-lattices …are instrumental in proving several properties of dependencies. Examples showing how these techniques are valuable in proving theorems about dependencies are given. Show more

DOI: 10.3233/FI-1993-193-403

Citation: Fundamenta Informaticae, vol. 19, no. 3-4, pp. 235-274, 1993

Authors: Biela, Andrzej

Article Type: Research Article

Abstract: In this paper we shall introduce a formal system of algorithmic logic which enables us to formulate some problems connected with a retrieval system which provides a comprehensive tool in automated theorem proving of theorems consisting of programs, procedures and functions. The procedures and functions may occur in considered theorems while the program of the above mentioned system is being executed. We can get an answer whether some relations defined by programs hold and we can prove functional equations in a dynamic way by looking for a special set of axioms /assumptions/ during the execution of system. We formulate RS-algorithm …which enables us to construct the set of axioms for proving some properties of functions and relations defined by programs. By RS-algorithm we get the dynamic process of proving functional equations and we can answer the question whether some relations defined by programs hold. It enables us to solve some problems concerning the correctness of programs. This system can be used for giving an expert appraisement. We shall provide the major structures and a sketch of an implementation of the above formal system. Show more

Keywords: algorithmic logic, diagram, procedures, RS-algorithm, implementation, experimental results

DOI: 10.3233/FI-1993-193-404

Citation: Fundamenta Informaticae, vol. 19, no. 3-4, pp. 275-301, 1993

Authors: Levene, Mark | Loizou, George

Article Type: Research Article

Abstract: The nested relational model extends the fiat relational model by relaxing the first normal form assumption in order to allow the modelling of complex objects. Recently many extended algebras have been suggested for the nested relational model, but only few have incorporated null values into the attribute domains. Furthermore, some of the previously defined extended algebras are defined only over a subclass of nested relations, and all of them are difficult to use, since the user must know the detailed structure of the nested relations being queried. Herein, we define an extended algebra for nested relations, which may contain …null values, called the null extended algebra . The null extended algebra is defined over the general class of nested relations with null values and, in addition, allows queries to be formulated without the user having to know the detailed structure of the nested relations being queried. In this sense, our null extended join operator of the null extended algebra is unique in the literature, since it joins two nested relations by taking into account all their common attributes at all levels of their structure, whilst operating directly on the two nested relations. All the operators of the null extended algebra are proved to be faithful and precise . The null extended algebra is a complete extended algebra in the context of nested relations, and, in addition, it includes the null extended powerset operator , which provides recursion and iteration facilities. Show more

Keywords: nested relations, null values, null extended algebra, faithful extended algebra operators, precise extended algebra operators

DOI: 10.3233/FI-1993-193-405

Citation: Fundamenta Informaticae, vol. 19, no. 3-4, pp. 303-342, 1993

Authors: Novotný, Jiři | Novotný, Miroslav

Article Type: Research Article

Abstract: A concept in Wille’s context can be generated starting with a set of features. The problem of finding a minimal subset of the given set of features that generates the same concept as the given one is solved using a suitable dependence space and constructing reducts of one of its subsets. This result can be applied to information systems where it enables to cancel superfluous values of attributes.

Keywords: dependence, reduct, dependence space, context, information system, descriptor, decision table

DOI: 10.3233/FI-1993-193-406

Citation: Fundamenta Informaticae, vol. 19, no. 3-4, pp. 343-353, 1993

Authors: Kari, Lila | Mateescu, Alexandru | Salomaa, Arto | Păun, Gheorghe

Article Type: Research Article

Abstract: We discuss questions related to the cardinality, the effective construction, and decidability of the so-called deletion sets: the sets of strings obtained by erasing from a word the subwords which appear as elements of a given language.

DOI: 10.3233/FI-1993-193-407

Citation: Fundamenta Informaticae, vol. 19, no. 3-4, pp. 355-370, 1993

Authors: Marongiu, Gabriele | Tulipani, Sauro

Article Type: Research Article

Abstract: In this paper we give a new proof of undecidability results about term algebras with subterm relation. This proof yields a novel result which states that, in presence of the subterm relation and in signatures with symbols of arity greater than one, the ∑ 1 theory of rational trees is properly included in the ∑ 1 theory of infinite trees. Moreover, these theories are quite different; in fact, the first is r.e. and the second has degree not less than ∑ 1 1 …. Here, in analogy with the arithmetical hierarchy, we call Δ 0 the prenex formulas, whose quantifiers are bounded by the predicate ⩽, and we call ∑ 1 the formulas which are existential quantification of Δ 0 formulas. Show more

DOI: 10.3233/FI-1993-193-408

Citation: Fundamenta Informaticae, vol. 19, no. 3-4, pp. 371-382, 1993

Authors: Amir, Amihood | Smith, Carl H.

Article Type: Research Article

Abstract: One of the problems associated with the introduction of parallel processors is the so called “dusty deck” problem. A solution entails the development of optimizing compilers that transform programs previously written for a conventional serial processor into functionally equivalent programs that exploit the parallel processing capabilities of the new multiprocessor machines. We introduce a function Composition Model that models parallel architectures as a hierarchy of syntactic function definitions. Position in the hierarchy is equivalent to parallel time complexity in the modelled architecture. Other parallel concepts such as global vs. local communications, concurrency or exclusivity of read and write, …and the number of processors used in a computation, are modelled as well. We rigorously prove that a compiler that optimizes a program for parallelism on a CREW PRAM is not effectively computable, even if it is also given an optimal serial program for the same task and a time bounding function. It turns out that the function composition model is similar to some traditional models, such as the Grzegorczyk Hierarchy. Our parallel interpretation of the Grzegorczyk Hierarchy offers new insights and admits a new cleaner and more elegant definition of the hierarchy with a single base class, as opposed to Grzegorczyk’s three. Show more

DOI: 10.3233/FI-1993-193-409

Citation: Fundamenta Informaticae, vol. 19, no. 3-4, pp. 383-402, 1993

Authors: Murphy, David

Article Type: Research Article

Abstract: The purpose of this paper is to present a real-timed concurrency theory in the noninterleaving tradition. The theory is based on the occurrences of actions; each occurrence or event has a start and a finish. Causality is modelled by assigning a strict partial order to these starts and finishes, while timing is modelled by giving them reals. The theory is presented in some detail. All of the traditional notions found in concurrency theories (such as conflict, confusion, liveness, and so on) are found to be expressible. Four notions of causality arise naturally from the model, leading to notions of …securing . Three of the notions give rise to underlying event structures, demonstrating that our model generalises Winskel’s. Infinite structures are then analysed: a poset of finite structures is defined and suitably completed to give one containing infinite structures. These infinite structures are characterised as just those arising as limits of finite ones. Our technique here, which relies on the structure of time, is of independent interest. Show more

Keywords: Concurrency, duration, event structure, noninterleaving models, real time

DOI: 10.3233/FI-1993-193-410

Citation: Fundamenta Informaticae, vol. 19, no. 3-4, pp. 403-416, 1993