Fundamenta Informaticae - Volume 18, issue 2-4

Article Type: Other

DOI: 10.3233/FI-1993-182-401

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. i-vii, 1993

Authors: Rauszer, Cecylia

Article Type: Editorial

DOI: 10.3233/FI-1993-182-402

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 107-107, 1993

Authors: Ophelders, W.M.J. | De Swart, H.C.M.

Article Type: Research Article

Abstract: In [13] we have presented the ideas underlying an automated theorem prover based on tableaux extended with unification under restrictions. In [6] a full description of an implementation of this theorem prover in PROLOG is given. In this paper we first shortly repeat the main ideas, referring to [13] for more details. Next we present the test results of our theorem prover mainly with respect to Pelletier’s 75 problems for testing automatic theorem provers ([7]). We also give a comparison of our results with the results obtained by the resolution-based theorem provers PCPROVE and OTTER and by the tableau-based theorem …provers of M. Fitting and S. Reeves. Short discussions of these theorem provers accompany the test results. For more elaborate discussions the reader is referred to [6]. Show more

DOI: 10.3233/FI-1993-182-403

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 109-127, 1993

Authors: Garlatti, Serge

Article Type: Research Article

Abstract: Representation systems based on inheritance networks are founded on the hierarchical structure of knowledge. Such representation is composed of a set of objects and a set of is -a links between nodes. Objects are generally defined by means of a set of properties. An inheritance mechanism enables us to share properties across the hierarchy, called an inheritance graph. It is often difficult, even impossible to define classes by means of a set of necessary and sufficient conditions. For this reason, exceptions must be allowed and they induce nonmonotonic reasoning. Many researchers have used default logic to give them formal semantics …and to define sound inferences. In this paper, we propose a survey of the different models of nonmonotonic inheritance systems by means of default logic. A comparison between default theories and inheritance mechanisms is made. In conclusion, the ability of default logic to take some inheritance mechanisms into account is discussed. Show more

DOI: 10.3233/FI-1993-182-404

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 129-149, 1993

Authors: Mundici, Daniele

Article Type: Research Article

Abstract: Ulam asked what is the minimum number of yes-no questions necessary to find an unknown number in the search space (1, …, 2n ), if up to l of the answers may be erroneous. The solutions to this problem provide optimal adaptive l error correcting codes. Traditional, nonadaptive l error correcting codes correspond to the particular case when all questions are formulated before all answers. We show that answers in Ulam’s game obey the (l +2)-valued logic of Łukasiewicz. Since approximately finite-dimensional (AF) C *-algebras can be interpreted in the infinite-valued sentential calculus, we discuss the relationship …between game-theoretic notions and their C *-algebraic counterparts. We describe the correspondence between continuous trace AF C *-algebras, and Ulam games with separable Boolean search space S . whose questions are the clopen subspaces of S . We also show that these games correspond to finite products of countable Post MV algebras, as well as to countable lattice-ordered Specker groups with strong unit. Show more

DOI: 10.3233/FI-1993-182-405

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 151-161, 1993

Authors: Leitsch, Alexander

Article Type: Research Article

Abstract: It is investigated, how semantic clash resolution can be used to decide some classes of clause sets. Because semantic clash resolution is complete, the termination of the resolution procedure on a class Γ gives a decision procedure for Γ. Besides generalizing earlier results we investigate the relation between termination and clause complexity. For this purpose we define the general concept of atom complexity measure and show some general results about termination in terms of such measures. Moreover, rather than using fixed resolution refinements we define an algorithmic generator for decision procedures, which constructs appropriate semantic refinements out of the syntactical …structure of the clause sets. This method is applied to the Bernays – Schönfinkel class, where it gives an efficient (resolution) decision procedure. Show more

DOI: 10.3233/FI-1993-182-406

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 163-182, 1993

Authors: Chen, Su-Shing

Article Type: Research Article

Abstract: This paper is concerned with a mathematical foundation of representation issues and reasoning schemes of spatial information and knowledge. Spatial mental models in cognitive systems using a hybrid symbolic AI and highly parallel (e.g., neural networks or connectionism) framework of deductive and inductive reasoning in spatial domains will be constructed. The framework for “induction” of Holland, Holyoak, Nisbett, and Thagard was proposed as the classifer system approach to inferential and learning processes in biological cognitive systems which remedies the inadequacies of the classical logical approaches to induction: formal inductive logics. In this paper, we use a hybrid symbolic and highly …parallel approach instead of the classifier system only. Show more

DOI: 10.3233/FI-1993-182-407

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 183-192, 1993

Authors: Grzymala-Busse, Jerzy W.

Article Type: Research Article

Abstract: This paper presents and compares two algorithms of machine learning from examples, ID3 and AQ, and one recent algorithm from the same class, called LEM2. All three algorithms are illustrated using the same example. Production rules induced by these algorithms from the well-known Small Soybean Database are presented. Finally, some advantages and disadvantages of these algorithms are shown.

DOI: 10.3233/FI-1993-182-408

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 193-207, 1993

Authors: Hadjimichael, Michael | Wasilewska, Anita

Article Type: Research Article

Abstract: We present here an application of Rough Set formalism to Machine Learning. The resulting Inductive Learning algorithm is described, and its application to a set of real data is examined. The data consists of a survey of voter preferences taken during the 1988 presidential election in the U.S.A. Results include an analysis of the predictive accuracy of the generated rules, and an analysis of the semantic content of the rules.

DOI: 10.3233/FI-1993-182-409

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 209-220, 1993

Authors: Baroglio, Cristina | Botta, Marco | Giordana, Attilio

Article Type: Research Article

Abstract: Inducing concept descriptions in first order logic is inherently a complex task; then, heuristics are needed to keep the problem to manageable size. In this paper we explore the effect of alternative search strategies, including the use of information gain and of a-priori knowledge, on the quality of the acquired relations, intended as the ability to reconstruct the rule used to generate the examples. To this aim, an artificial domain has been created, in which the experimental conditions can be kept under control, the “solulion” of the learning problem is known and a perfect theory is available. Another investigated aspect …is the impact of more complex description languages, such as, for instance, including numerical quantifiers. The resultS show that the information gain criterion is too greedy to be useful when the concepts have a complex internal structure; however, this drawback is more or less shared with any purely statistical evaluation criterion. The addition of parts of the available domain theory increases the obtained performance level. Similar results have been previously obtained on a number of real applications and of test-cases taken from standard machine learning data bases. Show more

DOI: 10.3233/FI-1993-182-410

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 221-232, 1993

Authors: Richter, Michael M.

Article Type: Research Article

DOI: 10.3233/FI-1993-182-411

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 233-248, 1993

Authors: Steinby, Magnus

Article Type: Research Article

Abstract: In this paper recognizable and rational subsets of general algebras of finite type are studied. These are natural generalizations of the familiar notions originally defined for monoids, but they also include as special cases recognizable and rational tree languages, for example. Some closure properties of the families of recognizable and rational subsets are studied. The operations considered seem to be intimately connected with the recognizability and rationality properties of subsets, and they can also be defined for subsets of abstract algebras, regardless of the nature of the elements. The last part of the paper is devoted to generalized forms of …Kleene’s theorem and related results. Show more

DOI: 10.3233/FI-1993-182-412

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 249-266, 1993

Authors: Proietti, Maurizio | Pettorossi, Alberto

Article Type: Research Article

Abstract: We study the problem of automating some development techniques for logic programs. These techniques are based on the application of semantics preserving transformation rules which are driven by strategies. We propose an abstract strategy which is parametrized by three mathematical functions called definition-folding , selection , and replacement . Once these three functions are supplied, our abstract strategy becomes a concrete one which can be used during program development for driving the application of the Definition, Folding, Unfolding, and Goal Replacement Rules. We show that the definition-folding function can be determined in an automatic way from the description …of the syntactic properties of the program we wish to derive. We also show through some examples that many program derivation strategies described in the literature, such as the methodology for eliminating unnecessary variables, the tupling strategy, the partial deduction techniques, and the promotion strategy, can be viewed as particular instances of our abstract strategy. Show more

DOI: 10.3233/FI-1993-182-413

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 267-286, 1993

Authors: Korec, Ivan

Article Type: Research Article

Abstract: For almost all binary relations R ⊆ N 2 the addition and multiplication on the set N of nonnegative integers (and hence all arithmetical relations) are first order definable in the structure (N ; ⩽, R ). The defining formulae can be chosen independently on R and the words “for almost all” mean “with probability 1” by a very natural probability measure.

DOI: 10.3233/FI-1993-182-414

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 287-296, 1993

Authors: Perlis, Donald

Article Type: Research Article

Abstract: There have been two major efforts at a synthesis of logic and artificial intelligence, one building on the other. I will review these and argue that yet another addition is needed.

DOI: 10.3233/FI-1993-182-415

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 297-305, 1993

Authors: Van Benthem, Johan

Article Type: Research Article

Abstract: We re-analyze the original algebraic proof of the Goldblatt-Thomason theorem characterizing modally definable frame classes, providing an alternative model-theoretic argument. The analysis also provides a more general perspective on the use of algebraic versus model-theoretic methods in Modal Logic.

DOI: 10.3233/FI-1993-182-416

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 307-317, 1993

Authors: Rebagliato, Jordi | Verdú, Ventura

Article Type: Research Article

Abstract: In this paper we study the algebraization of two Gentzen systems, both of them generating the implication-less fragment of the intuitionistic propositional calculus. We prove that they are algebraizable, the variety of pseudocomplemented distributive lattices being an equivalent algebraic semantics for them, in the sense that their Gentzen deduction and the equational deduction over this variety are interpretable in one another, these interpretations being essentially inverse to one another. As a consequence, the consistent deductive systems that satisfy the properties of Conjunction, Disjunction and Pseudo-Reductio ad Absurdum are described by giving apropriate Gentzen systems for them. All these Gentzen systems …are algebraizable, the subvarieties of the variety of pseudocomplemented distributive lattices being their equivalent algebraic semantics respectively. Finally we give a Gentzen system for the conjunction and disjunction fragment of the classical propositional calculus, prove that the variety of distributive lattices is an equivalent algebraic semantics for it and give a Gentzen system, weaker than the latter, the variety of lattices being an equivalent algebraic semantics for it. Show more

DOI: 10.3233/FI-1993-182-417

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 319-338, 1993

Authors: Volger, Hugo

Article Type: Research Article

Abstract: We have shown earlier that the theories which uniformly admit initial families of models resp. disjoint initial families of models resp. initial models are exactly those which are closed under equalizers resp. equalizers and pullbacks (= connected limits) resp. equalizers and products (= arbitrary limits). In addition, syntactical characterizations had been given. To obtain an analogous result for pullbacks we have to weaken the initiality notions. Weakening the uniqueness of the morphism to a uniqueness up to an isomorphism we arrive at the corresponding quasiinitiality notions. As a new result we shall show that the theories which uniformly admit …disjoint quasiinitial families of models resp. quasiinitial models are exactly those which are closed under pullbacks resp. pullbacks and products (= arbitrary limits). As a tool we use a localized version of initiality which was suggested by J.Adamek. Using our result Hébert recently obtained a syntactical characterization for the case of disjoint quasiinitial families. In the case of quasiinitial families the characterization by means of certain class of limit constructions is still an open problem. Show more

DOI: 10.3233/FI-1993-182-418

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 339-362, 1993