There are very few reasoners which combine natural deduction and subsumption reasoning, and there are none which do so while supporting concurrency. Inference Graphs are a graph-based inference mechanism using an expressive first-order logic, capable of subsumption and natural deduction reasoning using concurrency. Evaluation of concurrency characteristics on a combination natural deduction and subsumption reasoning problem has shown linear speedup with the number of processors.

Hybrid reasoners combine multiple types of reasoning, usually subsumption and Prolog-style resolution. We outline a system which combines natural deduction and subsumption reasoning using Inference Graphs implementing a Logic of Arbitrary and Indefinite Objects.

Since their popularity began to rise in the mid-2000s there has been significant growth in the number of multi-core and multi-processor computers available. Knowledge representation systems using logical inference have been slow to embrace this new technology. We present the concept of inference graphs, a natural deduction inference system which scales well on multi-core and multi-processor machines. Inference graphs enhance propositional graphs by treating propositional nodes as tasks which can be scheduled to operate upon messages sent between nodes via the arcs that already exist as part of the propositional graph representation. The use of scheduling heuristics within a prioritized message passing architecture allows inference graphs to perform very well in forward, backward, bi-directional, and focused reasoning. Tests demonstrate the usefulness of our scheduling heuristics, and show significant speedup in both best case and worst case inference scenarios as the number of processors increases.

The SNePS inference engine is optimized for deductive efficiency, i.e. all beliefs acquired via inference are added to the agent's beliefs so that future queries may be answered by a retrieval rather than rederivation. An assumption-based truth maintenance system keeps track of the derivation histories of derived beliefs. We show how such an architecture simplifies the ontology of prepositional representations of plans; acts; preconditions, and effects of actions. In addition, the deductive efficiency of the basic system automatically extends itself to efficient search of plans, and hierarchical plan decompositions.

It is common in the knowledge representation literature for a belief space to be considered to be a set of sentences. Some implications of this stance are examined, and an alternative view, that belief spaces are sets of propositions is developed, and found to be an improvement. This latter view requires that propositions be accepted as entities in the domain of discourse of languages of thought, which, it is argued, accords with commonsense usage. In exchange, the semantics of nested belief expressions is simplified, and certain problems caused by the sentential view are avoided.

A method of deductive learning is proposed to control deductive inference. The goal is to improve problem solving time by experience, when that experience monotonically adds knowledge to the knowledge base. Accumulating and exploiting experience are done by the schemes of knowledge migration and knowledge shadowing. Knowledge migration generates specific (migrated) rules from general (migrating) rules and accumulates deduction experience represented by specificity relationships between migrating and migrated rules. Knowledge shadowing recognizes rule redundancies during a deduction and prunes deduction branches activated from redundant rules. Three principles for knowledge shadowing are suggested, depending on the details of deduction experience representation.>

A symmetric relation such as "... are adjacent" or "... are related" is characterized by not distinguishing among two or more of its arguments. Such a relation may efficiently be represented as a relation that takes a set as its argument, or as one of its arguments. The semantics of such a representation is, in part, determined by the instantiation (matching or unification) rule used by the reasoning system operating on the representation. Two such rules are discussed. One interprets the relation to be reflexive, the other does not. Since many of these relations are not reflexive, we prefer the latter rule, which forbids two distinct variables from matching the same term. It is argued that this apparently strange restriction is actually reasonable if the rules of the system are interpreted as fully intensional. Under that interpretation, an even stronger version of the instantiation rule emerges, which we name the Unique Variable Binding Rule (UVBR). Considering the behavior of the UVBR when reasoning about reflexive relations and about nonreflexive relations used reflexively casts light on the implications of a fully intensional knowledge representation scheme. These ideas are illustrated by the output of an intensional, rule-based knowledge representation system that has been modified to allow the choice of using the UVBR instead of standard unification.

We discuss how a deductive question-answering system can represent the beliefs or other cognitive states of users, of other (interacting) systems, and of itself. In particular, we examine the representation of first-person beliefs of others (e.g., the system's representation of a user's belief that he himself is rich). Such beliefs have as an essential component "quasi-indexical pronouns" (e.g., 'he himself'), and, hence, require for their analysis a method of representing these pronominal constructions and performing valid inferences with them. The theoretical justification for the approach to be discussed is the representation of nested "de dicto" beliefs (e.g., the system's belief that user-1 believes that system-2 believes that user-2 is rich). We discuss a computer implementation of these representations using the Semantic Network Processing System (SNePS) and an ATN parser-generator with a question-answering capability.

This paper describes the results of a preliminary study of a Knowledge Engineering approach to Natural Language Understanding. A computer system is being developed to handle the acquisition, representation, and use of linguistic knowledge. The computer system is rule-based and utilizes a semantic network for knowledge storage and representation. In order to facilitate the interaction between user and system, input of linguistic knowledge and computer responses are in natural language. Knowledge of various types can be entered and utilized: syntactic and semantic; assertions and rules. The inference tracing facility is also being developed as a part of the rule-based system with output in natural language. A detailed example is presented to illustrate the current capabilities and features of the system.

YNTRODUCTYONAugmented transition network (ATN) grammars have, since their development by Woods [ 7; ~, become the most used method of describing grammars for natural language understanding end question answering systems.The advantages of the ATN notation have been su,naarized as "I) perspicuity, 2) generative power, 3) efficiency of representation, 4) the ability to capture linguistic regularities and generalities, and 5) efficiency of operation., [ I ,p.191 ].The usual method of utilizing an ATN grammar in a natural language system is to provide an interpreter which can take any ATH graam~ar, a lexicon, and a sentence as data and produce either a parse of a sentence or a message that the sentence does not conform to the granunar.A compiler has been written [2;3 ] which takes an ATH grammar as input and produces a specialized parser for that grammar, but in this paper we will presume that an Interpreter is being used.

This paper discusses two programs that have been written to be aids to introductory programming students. They both embody the belief that Computer Assisted Instruction can be a worthwhile aid to students when properly used and that one of the best uses is to present visually to the student a process that he has some control over and which he would not otherwise be able to observe. Section 2 of this paper discusses HYCOMP1, an interactive visual computer simulator. Section 3 discusses IVF, the Interactive Visual FORTRAN interpreter. They were both written in SNOBOL41 and run under the KRONOS Time Sharing System on a CDC 6600 using an Applied Digital Data Systems, Inc. ADDS Consul 880 terminal, which is an ASCII terminal with a CRT display and an addressable cursor.