Conditional composition

Generalizing the notion of function composition, we introduce the concept ofconditional function composition and present a theory of such compositions. We use the theory to describe the semantics of a programming language with exceptions, and to relate exceptions to theIF statement.Supported in part by Air Force Office of Scientific Research grant number 91-0070. Now at DEC Systems Research Center, Palo Alto, CA.     

On computing minimal models

This paper addresses the problem of computing the minimal models of a given CNF propositional theory. We present two groups of algorithms. Algorithms in the first group are efficient when the theory is almost Horn, that is, when there are few non-Horn clauses and/or when the set of all literals that appear positive in any non-Horn clause is small. Algorithms in the other group are efficient when the theory can be represented as an acyclic network of low-arity relations. Our algorithms suggest several characterizations of tractable subsets for the problem of finding minimal models.This work was partially supported by an IBM graduate fellowship to the first author, by NSF grants IRI-9157636 and IRI-9200918, by Air Force Office of Scientific Research grant AFOSR 900136, by a grant from Xerox Palo Alto research center, and by Toshiba of America. Part of this work was done while the first author was a graduate student at the Cognitive Systems Laboratory, Computer Science Department, University of California, Los Angeles, California, USA.     

Local enhancement of compressed images

We develop a simple focusing technique for wavelet decompositions. This allows us to single out interesting parts of an image and obtain variable compression rates over the image. We also study similar techniques for image enhancement.Partially supported by U.S. Air Force Office of Scientific Research grant 89-0455 and Defense Advanced Research Projects Agency grant AFOSR 89-0455.     

Characterizing crossover in genetic algorithms

We characterize crossover and schemata; crossover is a binary operator that preserves schemata and commutes with addition and projection. Moreover, for any setS of chromosomes and familyF of crossover operators, we fully characterize the reachable chromosomes.Research sponsored in part by the Air Force Office of Scientific Research and Office of Naval Research (F49620-90-C-0033), and by the National Science Foundation (IRI-8917545).     

Degradation reduction in optics imagery using Toeplitz structure

This paper is concerned with improvement in optical image quality by image restoration. Image restoration is an ill-posed inverse problem which involves the removal or minimization of degradations caused by noise and blur in an image, resulting from, in this case, imaging through a medium. Our work here concerns the use of the underlying Toeplitz structure of such problems, and associated techniques for accelerating the convergence of iterative image restoration computations. Denoising methods, including total variation minimization, followed by segmentation-based preconditioning methods for minimum residual conjugate gradient iterations, are investigated. Regularization is accomplished by segmenting the image into (smooth) segments and varying the preconditioners across the segments. By taking advantage of the Toeplitz structure, our algorithms can be implemented with computational complexity of onlyO (ln ² logn), wheren ² is the number of pixels in the image andl is the number of segments used. Also, parallelization is straightforward. Numerical tests are reported for atmospheric imaging problems, including the case of spatially varying blur. Research supported in part by a National Science Foundation Postdoctoral Research Fellowship. Research sponsored by the U.S. Air Force Office of Scientific Research under grant F49620-97-1-1039. Research sponsored by the U.S. Air Force Office of Scientific Research under grant F49620-97-1-0139, and by the National Science Foundation under grant CCR-96-23356. Research sponsored by the National Science Foundation under grant CCR-96-23356.     

Vandermonde and resultant matrices: An abstract approach

We propose an abstract approach to the problems of common divisors and common multiples of rational matrix functions which (in the case of matrix polynomials) have been studied before using Vandermonde and resultant matrices.Supported in part by the Office of Naval Research, Air Force Office of Scientific Research, and the National Science Foundation.The work of this author was partially supported by an NSF grant and was carried out while visiting the University of California, San Diego.     

Using counterfactuals in knowledge-based programming

This paper adds counterfactuals to the framework of knowledge-based programs of Fagin, Halpern, Moses, and Vardi [3,4]. The use of counterfactuals is illustrated by designing a protocol in which an agent stops sending messages once it knows that it is safe to do so. Such behavior is difficult to capture in the original framework because it involves reasoning about counterfactual executions, including ones that are not consistent with the protocol. Attempts to formalize these notions without counterfactuals are shown to lead to rather counterintuitive behavior.Received: 15 November 2001, Accepted: 15 April 2004, Published online: 13 July 2004Joseph Y. Halpern: Work supported in part by NSF under grant IRI-96-25901, IIS-0090145, and CTC-0208535, by the Air Force Office of Scientific Research under grant F49620-96-1-0323 and F48620-02-1-0101, and by ONR under grants N00014-00-1-03-41, N00014-01-1-0795, and by the DoD Multidisciplinary University Research Initiative (MURI) program administered by the ONR under grant N00014-01-1-0795.)A preliminary version of this paper appeared in the Proceedings of the Seventh Conference on Theoretical Aspects of Rationality and Knowledge (TARK), 1998.     

A trust-region framework for managing the use of approximation models in optimization

This paper presents an analytically robust, globally convergent approach to managing the use of approximation models of varying fidelity in optimization. By robust global behaviour we mean the mathematical assurance that the iterates produced by the optimization algorithm, started at an arbitrary initial iterate, will converge to a stationary point or local optimizer for the original problem. The approach presented is based on the trust region idea from nonlinear programming and is shown to be provably convergent to a solution of the original high-fidelity problem. The proposed method for managing approximations in engineering optimization suggests ways to decide when the fidelity, and thus the cost, of the approximations might be fruitfully increased or decreased in the course of the optimization iterations. The approach is quite general. We make no assumptions on the structure of the original problem, in particular, no assumptions of convexity and separability, and place only mild requirements on the approximations. The approximations used in the framework can be of any nature appropriate to an application; for instance, they can be represented by analyses, simulations, or simple algebraic models. This paper introduces the approach and outlines the convergence analysis.This research was supported by the Dept. of Energy grant DEFG03-95ER25257 and Air Force Office of Scientific Research grant F49620-95-1-0210This research was supported by the National Aeronautics and Space Administration under NASA Contract No. NAS1-19480 while the author was in residence at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, VA 23681, USAThis research was supported by the Air Force Office of Scientific Research grant F49620-95-1-0210 and by the National Aeronautics and Space Administration under NASA Contract No. NAS1-19480 while the author was in residence at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, VA 23681, USA     

Homomorphisms between stochastic sequential machines and related problems

The problem of finding a stochastic sequential machine with minimal number of states and homomorphic to a given machine is studied in various aspects. The methods used for investigating the above problem are based upon the properties of a certain convex polyhedron associated with the given machine.The research reported herein was supported by the Air Force Office of Scientific Research, Office of Aerospace Research, United States Air Force under AFOSR Grant AFAFOSR-639-67.On leave from Technion, Israel Institute of Technology, Haifa, Israel.     

Quantification without variables in connectionism

Connectionist attention to variables has been too restricted in two ways. First, it has not exploited certain ways of doing without variables in the symbolic arena. One variable-avoidance method, that of logical combinators, is particularly well established there. Secondly, the attention has been largely restricted to variables in long-term rules embodied in connection weight patterns. However, short-lived bodies of information, such as sentence interpretations or inference products, may involve quantification. Therefore short-lived activation patterns may need to achieve the effect of variables. The paper is mainly a theoretical analysis of some benefits and drawbacks of using logical combinators to avoid variables in short-lived connectionist encodings without loss of expressive power. The paper also includes a brief survey of some possible methods for avoiding variables other than by using combinators.This work was supported in part by grant AFOSR-88-0215 from the Air Force Office of Scientific Research, to Barnden, and grant NAGW-1592 under the Innovative Research Program of the NASA Office of Space Science and Applications, to Barnden and C.A. Fields.     

Ordered model trees: A normal form for disjunctive deductive databases

Model trees were conceived as a structure-sharing approach to represent information in disjunctive deductive databases. In this paper we introduce the concept ofordered minimal model trees as a normal form for disjunctive deductive databases. These are model trees in which an order is imposed on the elements of the Herbrand base. The properties of ordered minimal model trees are investigated as well as their possible utilization for efficient manipulation of disjunctive deductive databases. Algorithms are presented for constructing and performing operations on ordered model trees. The complexity of ordered model tree processing is addressed. Model forests are presented as an approach to reduce the complexity of ordered model tree construction and processing.This research was supported by the National Science Foundation, under the grant Nr. IRI-89-16059, the Air Force Office of Scientific Research, under the grant Nr. AFOSR-91-0350, and the Fulbright Scholar Program.This work was done while visiting at the University of Maryland Institute for Advanced Computer Studies.     

A note on undecidable properties of formal languages

A general set of conditions is given under which a property is undecidable for a family of languages. Examples are given of the application of this result to wellknown families of languages.Research sponsored in part by the Air Force cambridge Research Laboratories, Office of Aerospace Research, USAF, under Contract F1962867C0008, and by the Air Force Office of Scientific Research, Office of Aerospace Research, USAF under Grant No. AF-AFOSR-1203-67.     

On supremal languages of classes of sublanguages that arise in supervisor synthesis problems with partial observation

This paper characterizes the class of closed and (M, N)-recognizable languages in terms of certain structural aspects of relevant automata. This characterization leads to algorithms that effectively compute the supremal (M, N)-recognizable sublanguage of a given language. One of these algorithms is used, in an alternating manner with an algorithm which yields the supremal (∑_u, N)-invariant resulting algorithm is proved. An example illustrates the use of these algorithms. This research was supported in part by the Air Force Office of Scientific Research under Grant No. AFOSR-86-0029, in part by the National Science Foundation under Grant No. ECS-8412100, and in part by the DoD Joint Services Electronics Program through the Air Force Office of Scientific Research (AFSC) Contract No. F49620-86-C-0045     

Analysis of an identification algorithm arising in the adaptive estimation of Markov chains

We investigate an algorithm applied to the adaptive estimation of partially observed finite-state Markov chains. The algorithm utilizes the recursive equation characterizing the conditional distribution of the state of the Markov chain, given the past observations. We show that the process “driving” the algorithm has a unique invariant measure for each fixed value of the parameter, and following the ordinary differential equation method for stochastic approximations, establish almost sure convergence of the parameter estimates to the solutions of an associated differential equation. The performance of the adaptive estimation scheme is analyzed by examining the induced controlled Markov process with respect to a long-run average cost criterion. This research was supported in part by the Air Force Office of Scientific Research under Grant AFOSR-86-0029, in part by the National Science Foundation under Grant ECS-8617860 and in part by the DoD Joint Services Electronics Program through the Air Force Office of Scientific Research (AFSC) Contract F49620-86-C-0045.     

Decomposition of linear sequential machines

Linear sequential machines can sometimes be decomposed into parallel and series connections of smaller linear sequential machines. Necessary and sufficient conditions are given for such decompositions to exist for finite linear sequential machines.Research sponsored by the Air Force Office of Scientific Research, Grant AF-AFOSR 639-67, and by the National Science Foundation, Grant GP-6945     

Proof rules for the programming language Euclid

Summary In the spirit of the previous axiomatixation of the programming language Pascal, this paper describes Hoare-style proof rules for Euclid, a programming language intended for the expression of system programs which are to be verified. All constructs of Euclid are covered except for storage allocation and machine dependencies.Supported by the Defense Advanced Research Projects Agency under contract DAHC-15-72-C-0308Supported in part by the National Science Foundation under grant MCS-76-86089 and the Joint Services Electronics Program monitored by the Air Force Office of Scientific Research under contract F44620-76-C-0061Supported in part by a Research Leave Grant from the University of Toronto and a grant from the National Research Council of Canada.Supported in part by the Defense Advanced Research Projects Agency under contract DAHC 73-C-0368. The views expressed are those of the authors     

The algebraic specification of abstract data types

Summary There have been many recent proposals for embedding abstract data types in programming languages. In order to reason about programs using abstract data types, it is desirable to specify their properties at an abstract level, independent of any particular implementation. This paper presents an algebraic technique for such specifications, develops some of the formal properties of the technique, and shows that these provide useful guidelines for the construction of adequate specifications.Supported in part by the National Science Foundation under grant MCS-76-06089 and the Joint Services Electronics Program monitored by the Air Force Office of the Scientific Research under contract F44620-72C-0061Supported in part by the National Research Council of Canada.     

Finding the minimum weight IIS cover of an infeasible system of linear inequalities

Given an inconsistent set of inequalities Ax b, theirreducible inconsistent subsystems (IISs) designate subsets of the inequalities such that at least one member of each subset must be deleted in order to achieve a feasible system. By solving a set covering problem over the IISs, one can determine a minimum weight set of inequalities that must be deleted in order to achieve feasibility. Since the number of IISs is generally exponential in the size of the original subsystem, we generate the IISs only when they are violated by a trial solution. Computational results on the NETLIB infeasible LP library are given.This author was supported by Air Force Office of Scientific Research and Office of Naval Research Contract #F49620-92-J-0248-DEF.     

Images of AFL under certain families of homomorphisms

An AFL is a family of sets of words closed under six basic operations. It is shown that a certain family of homomorphic images of sets in an AFL is an AFL. Then two families of sets related to tape-bounded nondeterministic Turing acceptors are shown to coincide and be an AFL.Research sponsored in part by the Air Force Cambridge Research Laboratories, Office of Aerospace Research, USAF, under contract F1962867C0008, the Air Force Office of Scientific Research, Office of Aerospace Research, USAF, under AFOSR Grant No. AF-AFOSR-1203-67A, and by the National Science Foundation, Grant No. GJ454.Part of this work was also done at the System Development Corporation, Santa Monica, Calif.     

Some ideas on semantic memory in automatic learning of heuristics

This paper is concerned with the problem of computer semantic memory, i. e. with the problem of representing general knowledge about, a given world. The sematic memory issue is raised in the context of machiue learning of heuristics and the connection with the problem of machine representation of knowledge is emphasized. The guidelines for the implementation of a sematic memory are presented and attention is given to the design of the processes for storing and retrieving information. The problem of knowledge representation is tackled in its, general form, so that the proposed semantic memory may be of interest also in other fields, like Natural Lauguage Understanding, Question Answering, Theorem Proving. The research described in this paper was carried out wile the author was visiting, the Department of Computer Science, Carnegie Mellon University, Pittsburgh, Pa. U. S. A. The research has been supported by the Advanced Research Projects Agency of the Office of the U. S. Secretary of Defense (F 44620-70-C-0107), monitored by the Air Force Office of Scientific Reseach, and in part by the National Research Council Istituto di Elaborazione dell'informazione, Pisa Italy.