The problem of reasoning by analogy

This article is the twenty-seventh of a series of articles discussing various open research problems in automated reasoning. The problem proposed for research asks one to find criteria that an automated reasoning program can apply to determine whether to attack a given question with reasoning by analogy. The imprecise term reasoning by analogy refers to a type of reasoning in which the type of proof being sought is sharply influenced by the style of proof that was successfully used to prove related theorems.This work was supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Constructing sets of functions which have a givenF-cardinality

The termF-cardinality of (=F-card()) is introduced whereF: ^{n n} is a partial function and is a set of partial functionsf: ^{n n} . TheF-cardinality yields a lower bound for the worst-case complexity of computingF if only functionsf can be evaluated by the underlying abstract automaton without conditional jumps. This complexity bound isindependent from the oracles available for the abstract machine. Thus it is shown that any automaton which can only apply the four basic arithmetic operations needs (n logn) worst-case time to sortn numbers; this result is even true if conditional jumps witharbitrary conditions are possible. The main result of this paper is the following: Given a total functionF: ^{n n} and a natural numberk, it is almost always possible to construct a set such that itsF-cardinality has the valuek; in addition, can be required to be closed under composition of functionsf,g . Moreover, ifF is continuous, then consists of continuous functions.     

Human-oriented and machine-oriented reasoning: Remarks on some problems in the history of Automated Theorem Proving

Examples in the history of Automated Theorem Proving are given, in order to show that even a seemingly mechanical activity, such as deductive inference drawing, involves special cultural features and tacit knowledge. Mechanisation of reasoning is thus regarded as a complex undertaking in cultural pruning of human-oriented reasoning. Sociological counterparts of this passage from human- to machine-oriented reasoning are discussed, by focusing on problems of man-machine interaction in the area of computer-assisted proof processing.     

A note to the definition of the ŁΠ-algebras

The -algebras are interesting algebraic structures. They were introduced by Esteva, Godo, and Montagna. These algebras are closely related to the well-known MV-algebras and -algebras. They have two sets of operations and reduct to one set is an MV-algebra and to the other one is a -algebra.Other important reducts of -algebras are so-called P-algebras (an MV-algebras enriched with product connective) and -algebras (-algebras with additional involutive negation).The definition of -algebras is based on its MV-algabraic reduct and the additional identities. In this paper we present how to base this definition on the other reducts we mention above. We present minimal sets of conditions which has to be added to the defining conditions of those reducts in order to obtain -algebras.     

Reduction and unification in lambda calculi with a general notion of subtype

Reduction, equality, and unification are studied for a family of simply typed -calculi with subtypes. The subtype relation is required to relate base types only to base types and to satisfy some order-theoretic conditions. Constants are required to have a least type, that is, no overloading. We define the usual and a subtype-dependent -reduction. These are related to a typed equality relation and shown to be confluent in a certain sense. We present a generic algorithm for preunification modulo -conversion and an arbitrary subtype relation. Furthermore it is shown that unification with respect to any subtype relation is universal.     

Modular Control and Coordination of Discrete-Event Systems

In the supervisory control of discrete-event systems based on controllable languages, a standard way to handle state explosion in large systems is by modular supervision: either horizontal (decentralized) or vertical (hierarchical). However, unless all the relevant languages are prefix-closed, a well-known potential hazard with modularity is that of conflict. In decentralized control, modular supervisors that are individually nonblocking for the plant may nevertheless produce blocking, or even deadlock, when operating on-line concurrently. Similarly, a high-level hierarchical supervisor that predicts nonblocking at its aggregated level of abstraction may inadvertently admit blocking in a low-level implementation. In two previous papers, the authors showed that nonblocking hierarchical control can be guaranteed provided high-level aggregation is sufficiently fine; the appropriate conditions were formalized in terms of control structures and observers. In this paper we apply the same technique to decentralized control, when specifications are imposed on local models of the global process; in this way we remove the restriction in some earlier work that the plant and specification (marked) languages be prefix-closed. We then solve a more general problem of coordination: namely how to determine a high level coordinator that forestalls conflict in a decentralized architecture when it potentially arises, but is otherwise minimally intrusive on low-level control action. Coordination thus combines both vertical and horizontal modularity. The example of a simple production process is provided as a practical illustration. We conclude with an appraisal of the computational effort involved.     

The expected additive weight of trees

Summary We consider a general additive weight of random trees which depends on the structure of the subtrees, on weight functions defined on the number of internal and external nodes and on the degrees of the nodes appearing in the tree and its subtrees. Choosing particular weight functions, the corresponding weight is an important parameter appearing in the analysis of sorting and searching algorithms. For a simply generated family of rooted planar trees , we shall derive a general approach to the computation of the average weight of a tree T with n nodes and m leaves for arbitrary weight functions. This general result implies exact and asymptotic expressions for many types of average weights of a tree T with n nodes if the weight functions are arbitrary polynomials in the number of nodes and leaves with coefficients depending on the node degrees.     

Distributivity in Łℵ0 and Other Sentential Logics

Certain distributivity results for ukasiewicz's infinite-valued logic ₀ are proved axiomatically (for the first time) with the help of the automated reasoning program OTTER. In addition, nondistributivity results are established for a wide variety of positive substructural logics by the use of logical matrices discovered with the automated model-finding programs MACE and MAGIC.     

Why does language matter to artificial intelligence?

Artificial intelligence, conceived either as an attempt to provide models of human cognition or as the development of programs able to perform intelligent tasks, is primarily interested in theuses of language. It should be concerned, therefore, withpragmatics. But its concern with pragmatics should not be restricted to the narrow, traditional conception of pragmatics as the theory of communication (or of the social uses of language). In addition to that, AI should take into account also the mental uses of language (in reasoning, for example) and the existential dimensions of language as a determiner of the world we (and our computers) live in. In this paper, the relevance of these three branches of pragmatics-sociopragmatics, psychopragmatics, and ontopragmatics-for AI are explored.     

From Conditional Events to Conditional Measures: A New Axiomatic Approach

Our starting point is a definition of conditional event EH which differs from many seemingly similar ones adopted in the relevant literature since 1935, starting with de Finetti. In fact, if we do not assign the same third value u (undetermined) to all conditional events, but make it depend on EH, it turns out that this function t(EH) can be taken as a general conditional uncertainty measure, and we get (through a suitable – in a sense, compulsory – choice of the relevant operations among conditional events) the natural axioms for many different (besides probability) conditional measures.     

Organisational development issues and the implementation of the Clean Technology paradigm in industry

Environmental protection activities in industry have rapidly increased in number over the last years. Additionally, surveys of environmental activities have identified a change in the kind or in the approaches used to environmental problem solving. A new paradigm Clean Technology has been developed which gradually seems to replace the Clean-up Technology paradigm and the older Dilute and Disperse paradigm. The new Clean Technology paradigm brings with it not only a new way of looking at environmental protection, but also a range of rules guiding the application of technology and the design of technological systems. This paper presents a few case studies highlighting and evaluating Clean Technology activities.     

A dialectical model of assessing conflicting arguments in legal reasoning

Inspired by legal reasoning, this paper presents a formal framework for assessing conflicting arguments. Its use is illustrated with applications to realistic legal examples, and the potential for implementation is discussed. The framework has the form of a logical system for defeasible argumentation. Its language, which is of a logic-programming-like nature, has both weak and explicit negation, and conflicts between arguments are decided with the help of priorities on the rules. An important feature of the system is that these priorities are not fixed, but are themselves defeasibly derived as conclusions within the system. Thus debates on the choice between conflicting arguments can also be modelled.The proof theory of the system is stated in dialectical style, where a proof takes the form of a dialogue between a proponent and an opponent of an argument. An argument is shown to be justified if the proponent can make the opponent run out of moves in whatever way the opponent attacks. Despite this dialectical form, the system reflects a declarative, or relational approach to modelling legal argument. A basic assumption of this paper is that this approach complements two other lines of research in AI and Law, investigations of precedent-based reasoning and the development of procedural, or dialectical models of legal argument.Supported by a research fellowship of the Royal Netherlands Academy of Arts and Sciences, and by Esprit WG 8319 Modelage.     

Theory of edge perception for computer vision feedback control

In this paper, the authors address the problem of edge-perception for its applications to vision-feedback control in robotic systems.In natural vision, the recognition of objects takes place through the process consisting of eye system, neural networks and cognition. The cognitive process, in turn yields a phenomenon known as perception. This is the phenomenon of perception of physical attributes, such as edges, color and texture, etc., which is responsible for the recognition of objects through the natural vision processes.In this paper, we make an attempt to postulate the theory of perception for gray-level images. The gray-level images, when going through the cognitive and perception processes, are contaminated by the uncertainty; here we call it cognitive uncertainty.The studies in this paper are confined to the phenomenon of edge-perception for two-dimensional gray-level images, however, these studies can be extended to other types of visual attributes both in two-dimensional and three-dimensional spaces. Indeed, the perception of these attributes, which attempts to emulate the human vision system, may help in the design of a truly robust computer vision-feedback control system for robotic applications.     

Single axioms for groups

We study equations of the form (=x) which are single axioms for group theory. Earlier examples of such were found by Neumann and McCune. We prove some lower bounds on the complexity of these , showing that McCune's examples are the shortest possible. We also show that no such can have only two distinct variables. We do produce an with only three distinct variables, refuting a conjecture of Neumann. Automated reasoning techniques are used both positively (searching for and verifying single axioms) and negatively (proving that various candidate (=x) hold in some nongroup and are, hence, not single axioms).     

Optimal component-insertion sequenceplanning methodology for the semiautomatic assembly of printed circuit boards

One of the primary concerns in the manufacturing of printed circuit boards (PCBs) is the definition of optimum component-insertion sequences for manual and automated operations. The problem is dynamic and multiple feasible solutions can be found. The research work described in this paper has developed a component-insertion sequencing methodology and a proof-of-concept expert system for printed circuit boards. This system solves the component-insertion sequencing problem for semi-automated work cells which utilize a light guiding system to identify for the operator where to assemble the next component. The innovation of the methodology is the application of Artificial Intelligence and Expert Systems techniques to represent the human reasoning involved in semi-automated PCB assembly planning. Based on established assembly criteria, sequencing decision rules and data available from a CAD system, the methodology leads to optimum component-insertion sequences.     

Separating complexity classes related to bounded alternating ω-branching programs

We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of -branching programs, : , a semiring homomorphism, that generalizes ordinary branching programs, -branching programs [M2] andMOD _p-branching programs [DKMW].Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating -branching programs we are able to separate the corresponding complexity classesN _ba ,co-N _{ba ba} , andMOD _p - _ba ,p prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past.     

Probabilistic analysis of the application of the cross ratio to model based vision: Misclassification

The cross ratio of four colinear points is of fundamental importance in model based vision, because it is the simplest numerical property of an object that is invariant under projection to an image. It provides a basis for algorithms to recognise objects from images without first estimating the position and orientation of the camera.A quantitative analysis of the effectiveness of the cross ratio in model based vision is made. A given imageI of four colinear points is classified by making comparisons between the measured cross ratio of the four image points and the cross ratios stored in the model database. The imageI is accepted as a projection of an objectO with cross ratio if |–|ntu, wheren is the standard deviation of the image noise,t is a threshold andu=. The performance of the cross ratio is described quantitatively by the probability of rejectionR, the probability of false alarmF and the probability of misclassificationp (), defined for two model cross ratios , . The trade off between these different probabilities is determined byt.It is assumed that in the absence of an object the image points have identical Gaussian distributions, and that in the presence of an object the image points have the appropriate conditional densities. The measurements of the image points are subject to small random Gaussian perturbations. Under these assumptions the trade offs betweenR,F andp () are given to a good approximation byR=2(1–(t)),F=r _F t, t|–|^–1, where is the relative noise level, is cumulative distribution function for the normal distribution,r _F is constant, ande is a function of only. The trade off betweenR andF is obtained in Maybank (1994). In this paper the trade off betweenR andp () is obtained.It is conjectured that the general form of the above trade offs betweenR,F andp () is the same for a range of invariants useful in model based vision. The conjecture prompts the following definition: an invariant which has trade offs betweenR,F,p () of the above form is said to benon-degenerate for model based vision.The consequences of the trade off betweenR andp () are examined. In particular, it is shown that for a fixed overall probability of misclassification there is a maximum possible model cross ratio _m , and there is a maximum possible numberN of models. Approximate expressions for _m andN are obtained. They indicate that in practice a model database containing only cross ratio values can have a size of order at most ten, for a physically plausible level of image noise, and for a probability of misclassification of the order 0.1.     

Job-shop scheduling using automated reasoning: A case study of the car-sequencing problem

The job-shop scheduling problem is known to be NP-complete. The version of interest in this paper concerns an assembly line designed to produce various cars, each of which requires a (possibly different) set of options. The combinatorics of the problem preclude seeking a maximal solution. Nevertheless, because of the underlying economic considerations, an approach that yields a good sequence of cars, given the specific required options for each, would be most valuable. In this paper, we focus on an environment for seeking, studying, and evaluating approaches for yielding good sequences. The environment we discuss relies on the automated reasoning program ITP. Automated reasoning programs of this type offer a wide variety of ways to reason, strategies for controlling the reasoning, and auxiliary procedures that contribute to the effective study of problems of this kind. We view the study presented in this paper as a prototype of what can be accomplished with the assistance of an automated reasoning program.