It is important to increase computation efficiency of a system at a low cost while holding the system correct. For this realization, addition of new and efficient equivalent transformation rules, whose correctness is assured, is useful. As long as correct ET rules are added to a correct system, the computation result of the system is always correct. Improvement of rules is promoted further by improvement of data structure.In this paper, we improve data structure by introducing interval variables into the usual (...) term domain and add two correct and efficient ET rules, which are promoted by introduction of interval variables, for member constraints on interval variables. These rules are the candidate elimination rule and the common pattern specialization rule. We show by an experiment that computation efficiency is increased by using these rules. (shrink)

Representation and computation of negation is very important in problem solving in various application domains. The purpose of this paper is to propose a new approach to negation. While most theories for negation are based on the logic paradigm, this theory is constructed based on the equivalent transformation computation model, since the ET model provides us with “decomposability of programs,” i.e., a program in the ET model is a set of ET rules and can be synthesized by generating each ET (...) rule independently of other ET rules. To represent negation in the ET model, a constraint is introduced as a pair of an object and a domain. A constraint becomes true when the object is specialized to a ground object within the domain. A negative constraint has a domain that is the complement of the meaning of the corresponding declarative description. Computation of negation in the ET paradigm is realized by equivalent transformation of declarative descriptions including negative constraints. For each negative constraint in a definite clause, a new declarative description is produced and transformed equivalently. When it is transformed to a set of unit clauses, the negative constraint is solved. Each unit clause returns a simple constraint to the “caller” clause. This paper proves two theorems that provide a basis for such equivalent transformation of negative constraints. (shrink)

In this autobiographical sketch, which is followed by a bibliography of my writings, I try to relate my intellectual development to problems, ideas and results in proof-theoretic semantics on which I have worked and to which I have contributed.

In order to represent legal knowledge adequately, it is vital to create a formal device that can freely construct an individual concept directly from a predicate expression. For this purpose, a Compound Predicate Formula (CPF) is formulated for use in legal expert systems. In this paper, we willattempt to explain the nature of CPFs by rigorous logical foundation, i.e., establishing their syntax and semantics precisely through the use of appropriate examples. We note the advantages of our system over other such (...) systems and discuss the significance of CPFs with regard to the formalization of legal reasonings using examples from the United Nations Convention for the International Sale of Goods. (shrink)

The standard theory of logic programming is not applicable to Prolog programs even not to pure code. Modifying the theory to take account of reality more is the motivation of this article. For this purpose we introduce the ℓ-completion and the inductive extension of a logic program. Both are first-order theories in a language with operators for success, failure and termination of goals. The ℓ-completion of a logic program is a sound and complete axiomatization of the Prolog depth-first search under (...) certain natural conditions; the inductive extension of the ℓ-completion is a suitable theory for proving termination and equivalence of pure Prolog programs with negation. (shrink)

Most formalisms for representing common-sense knowledge allow incomplete and potentially inconsistent information. When strong negation is also allowed, contradictory conclusions can arise. A criterion for deciding between them is needed. The aim of this paper is to investigate an inherent and autonomous comparison criterion, based on specificity as defined in [POO 85, SIM 92]. In contrast to other approaches, we consider not only defeasible, but also strict knowledge. Our criterion is context-sensitive, i. e., preference among defeasible rules is determined dynamically (...) during the dialectical analysis.We show how specificity can be defined in terms of two different approaches: activation sets and derivation trees. This allows us to get a syntactic criterion that can be implemented in a computationally attractive way. The resulting definitions may be applied in general rulebased formalisms. We present theorems linking both characterizations. Finally we discuss other frameworks for defeasible reasoning in which preference handling is considered explicitly. (shrink)

Hypertext and knowledge based systems can be viewed as complementary technologies, which if combined into a composite system may be able to yield a whole which is greater than the sum of the parts. To gain the maximum benefits, however, we need to think about how to harness this potential synergy. This will mean devising new styles of system, rather than merely seeking to enhance the old models.In this paper we describe our model for coupling hypertext and a knowledge based (...) system, and then go on to describe two prototype systems which attempt to exploit this composite framework. The first application concerns animated hypertext which accords the text a central role whilst giving access to all the advantages of a knowledge based system. The second suggests how we can augment the hypertext by providing links which reflect the conceptual model of a knowledge based system in the domain, so as to provide a more structured traversal of the text. (shrink)

This paper presents an outline of a new theory of relevant deduction which arose from the purpose of solving paradoxes in various fields of analytic philosophy. In distinction to relevance logics, this approach does not replace classical logic by a new one, but distinguishes between relevance and validity. It is argued that irrelevant arguments are, although formally valid, nonsensical and even harmful in practical applications. The basic idea is this: a valid deduction is relevant iff no subformula of the conclusion (...) is replaceable on some of its occurrences by any other formula salva validitate of the deduction. The paper first motivates the approach by showing that four paradoxes seemingly very distant from each other have a common source. Then the exact definition of relevant deduction is given and its logical properties are investigated. An extension to relevance of premises is discussed. Finally the paper presents an overview of its applications in philosophy of science, ethics, cognitive psychology and artificial intelligence. (shrink)

In the 1920s, Paul Hertz (1881-1940) developed certain calculi based on structural rules only and established normal form results for proofs. It is shown that he anticipated important techniques and results of general proof theory as well as of resolution theory, if the latter is regarded as a part of structural proof theory. Furthermore, it is shown that Gentzen, in his first paper of 1933, which heavily draws on Hertz, proves a normal form result which corresponds to the completeness of (...) prepositional SLD-resolution in logic programming. (shrink)

. The term inversion principle goes back to Lorenzen who coined it in the early 1950s. It was later used by Prawitz and others to describe the symmetric relationship between introduction and elimination inferences in natural deduction, sometimes also called harmony. In dealing with the invertibility of rules of an arbitrary atomic production system, Lorenzen’s inversion principle has a much wider range than Prawitz’s adaptation to natural deduction. It is closely related to definitional reflection, which is a principle for reasoning (...) on the basis of rule-based atomic definitions, proposed by Hallnäs and Schroeder-Heister. After presenting definitional reflection and the inversion principle, it is shown that the inversion principle can be formally derived from definitional reflection, when the latter is viewed as a principle to establish admissibility. Furthermore, the relationship between definitional reflection and the inversion principle is investigated on the background of a universalization principle, called the ω- principle, which allows one to pass from the set of all defined substitution instances of a sequent to the sequent itself. (shrink)

The paper begins by providing a game-theoretic reconstruction of Gilbert’s (1989) philosophical critique of Lewis (1969) on the role of salience in selecting conventions. Gilbert’s insight is reformulated thus: Nash equilibrium is insufficiently powerful as a solution concept to rationalize conventions for unboundedly rational agents if conventions are solutions to the kinds of games Lewis supposes. Both refinements to NE and appeals to bounded rationality can plug this gap, but lack generality. As Binmore (this issue) argues, evolutive game theory readily (...) explains the origin of conventional behavior, but that is not Lewis’s project. Gilbert’s critique is generalized by reference to Bacharach’s (2006) work on team reasoning in games. The paper then argues that although Lewis’s account of the rationalization of conventions is shown by the reconstruction of Gilbert’s critique to be incomplete, Gilbert is wrong to conclude that classical (‘eductive’) game theory lacks the resources to explain conformity to conventions among people. A game-theoretic account of the dynamics of socialization, based on Ross’s (2005, 2006) idea of ‘game determination’, rationalizes choices of conventional strategies in overlapping generations contexts, provided agents are products of evolutionary selection and know that other players are also such products. (shrink)

We consider the theoryT IT of infinite terms. The axioms for the theoryT IT are analogous to the Mal'cev's axioms for the theoryT IT of finite terms whose models are the locally free algebras. Recently Maher [Ma] has proved that the theoryT IT in a finite non singular signature plus the Domain Closure Axiom is complete. We give a description of all the complete extension ofT IT from which an effective decision procedure forT IT is obtained. Our approach considers formulas (...) built up with syntactic terms containing pointers. Using such a technique, the analysis of the theoryT IT can be carried out in analogy with Mal'cev's analysis ofT FT. Our results follow from an effective quantifier elimination procedure for formulas with pointers. (shrink)

In this paper the notion of unifier is extended to the infinite set case. The proof of existence of the most general unifier of any infinite, unifiable set of types (terms) is presented. Learning procedure, based on infinite set unification, is described.

There has been little research into the weak kindsof negating hypotheses. Hypotheses may be unfalsifiable. In this case it is impossible tofind a contradiction in some area of the conceptualsystems in which they are incorporated.Notwithstanding this fact, it is sometimes necessaryto construct ways of rejecting the unfalsifiablehypothesis at hand by resorting to some external forms of negation, external because wewant to avoid any arbitrary and subjectiveelimination, which would be rationally orepistemologically unjustified. I will consider akind of ``weak'''' (unfalsifiable) hypotheses that (...) arehard to negate and the ways for making it easy. Inthese cases the subject can ``rationally'''' decide towithdraw his hypotheses even in contexts where it is``impossible'''' to find ``explicit'''' contradictions: theuse of negation as failure (an interestingtechnique for negating hypotheses and accessing newones suggested by artificial intelligence) isilluminating. I plan to explore whether this kind ofnegation can be employed to model hypothesiswithdrawal in Poincaré''s conventionalism of theprinciples of physics and in Freudian analyticreasoning. (shrink)

We describe a new way in which theories about the deontic status of actions can be represented in terms of the standard two-sorted first-order extensional predicate calculus. Some of the resulting formal theories are easy to implement in Prolog; one prototype implementation—R. M. Lee's deontic expert shell DX—is briefly described.

ABSTRACT This work presents efficient algorithms to update knowledge bases in the presence of integrity constraints. The algorithms ensure that the changes to the knowledge bases are minimal. We use the deductive database paradigm to represent knowledge. Minimality is defined as a natural partial order over possible models of the database and expresses a preference for data explicity stored in the database over the data deduced by default. This requirement seems rational for many applications and yet it is hard to (...) be expressed with a set of integrity constraints. We handle safe negation and local variables in the bodies of the rules. We tackle the issue of modifying the active domain (i.e. adding new constants or removing some of the constants which are present in the knowledge base), and we demonstrate how interaction with the user can be used to handle recursive definitions. (shrink)

This is an expository article about the solution to the frame problem proposed in 1980 by Raymond Reiter. For years, his “frame default” remained untested and suspect. But developments in some seemingly unrelated areas of computer science—logic programming and satisfiability solvers—eventually exonerated the frame default and turned it into a basis for important applications.

In this paper we investigate two purely syntactical notions ofcircularity, which we call ``self-application'''' and ``self-inclusion.'''' Alanguage containing self-application allows linguistic items to beapplied to themselves. In a language allowing for self-inclusion thereare expressions which include themselves as a proper part. We introduceaxiomatic systems of syntax which include identity criteria andexistence axioms for such expressions. The consistency of these axiomsystems will be shown by providing a variety of different models –these models being our circular languages. Finally we will show what (...) apossible semantics for these circular languages could look like. (shrink)

In this article, we compare the expressive powers of classes of normal logic programs that are obtained by constraining the number of positive subgoals in the bodies of rules. The comparison is based on the existence/nonexistence of polynomial, faithful, and modular translation functions between the classes. As a result, we obtain a strict ordering among the classes under consideration. Binary programs are shown to be as expressive as unconstrained programs but strictly more expressive than unary programs which, in turn, are (...) strictly more expressive than atomic programs. We also take propositional theories into consideration and prove them to be strictly less expressive than atomic programs. In spite of the gap in expressiveness, we develop a faithful but non-modular translation function from normal programs to propositional theories. We consider this as a breakthrough due to sub-quadratic time complexity |). Furthermore, we present a prototype implementation of the translation function and demonstrate its promising performance with SAT solvers using three benchmark problems. (shrink)

Let S be a set, P the class of all subsets of S and F the class of all fuzzy subsets of S. In this paper an “extension principle” for closure operators and, in particular, for deduction systems is proposed and examined. Namely we propose a way to extend any closure operator J defined in P into a fuzzy closure operator J* defined in F. This enables us to give the notion of canonical extension of a deduction system and to (...) give interesting examples of fuzzy logics. In particular, the canonical extension of the classical propositional calculus is defined and it is showed its connection with possibility and necessity measures. Also, the canonical extension of first order logic enables us to extend some basic notions of programming logic, namely to define the fuzzy Herbrand models of a fuzzy program. Finally, we show that the extension principle enables us to obtain fuzzy logics related to fuzzy subalgebra theory and graded consequence relation theory. (shrink)

In this paper I give conditions under which a matrix characterisation of validity is correct for first order logics where quantifications are restricted by statements from a theory. Unfortunately the usual definition of path closure in a matrix is unsuitable and a less pleasant definition must be used. I derive the matrix theorem from syntactic analysis of a suitable tableau system, but by choosing a tableau system for restricted quantification I generalise Wallen's earlier work on modal logics. The tableau system (...) is only correct if a new condition I call alphabetical monotonicity holds. I sketch how the result can be applied to a wide range of logics such as first order variants of many standard modal logics, including non-serial modal logics. (shrink)

Abduction is or subsumes a process of inference. It entertains possible hypotheses and it chooses hypotheses for further scrutiny. There is a large literature on various aspects of non-symbolic, subconscious abduction. There is also a very active research community working on the symbolic (logical) characterisation of abduction, which typically treats it as a form of hypothetico-deductive reasoning. In this paper we start to bridge the gap between the symbolic and sub-symbolic approaches to abduction. We are interested in benefiting from developments (...) made by each community. In particular, we are interested in the ability of non-symbolic systems (neural networks) to learn from experience using efficient algorithms and to perform massively parallel computations of alternative abductive explanations. At the same time, we would like to benefit from the rigour and semantic clarity of symbolic logic. We present two approaches to dealing with abduction in neural networks. One of them uses Connectionist Modal Logic and a translation of Horn clauses into modal clauses to come up with a neural network ensemble that computes abductive explanations in a top-down fashion. The other combines neural-symbolic systems and abductive logic programming and proposes a neural architecture which performs a more systematic, bottom-up computation of alternative abductive explanations. Both approaches employ standard neural network architectures which are already known to be highly effective in practical learning applications. Differently from previous work in the area, our aim is to promote the integration of reasoning and learning in a way that the neural network provides the machinery for cognitive computation, inductive learning and hypothetical reasoning, while logic provides the rigour and explanation capability to the systems, facilitating the interaction with the outside world. Although it is left as future work to determine whether the structure of one of the proposed approaches is more amenable to learning than the other, we hope to have contributed to the development of the area by approaching it from the perspective of symbolic and sub-symbolic integration. (shrink)

One of our purposes here is to expose something of the elementary logical structure of abductive reasoning, and to do so in a way that helps orient theorists to the various tasks that a logic of abduction should concern itself with. We are mindful of criticisms that have been levelled against the very idea of a logic of abduction; so we think it prudent to proceed with a certain diffidence. That our own account of abduction is itself abductive is methodological (...) expression of this diffidence. A second objective is to test our conception of abduction's logical structure against some of the more promising going accounts of abductive reasoning. We offer our various suggestions in a benignly advisory way. The primary targets of our advice is ourselves, meant as guides to work we have yet to complete or, in some instances, start. It is possible that our colleagues in the abduction research communities will find our counsel to be of some interest. But we repeat that our first concern is to try to get ourselves straight about what a logic of abduction should encompass. (shrink)

In this paper we present learning algorithms for classes of categorial grammars restricted by negative constraints. We modify learning functions of Kanazawa [10] and apply them to these classes of grammars. We also prove the learnability of intersection of the class of minimal grammars with the class of k-valued grammars.