Constraint solving for interpolation

Interpolation is an important component of recent methods for program verification. It provides a natural and effective means for computing the separation between the sets of ‘good’ and ‘bad’ states. The existing algorithms for interpolant generation are proof-based: They require explicit construction of proofs, from which interpolants can be computed. Construction of such proofs is a difficult task. We propose an algorithm for the generation of interpolants for the combined theory of linear arithmetic and uninterpreted function symbols that does not require a priori constructed proofs to derive interpolants. It uses a reduction of the problem to constraint solving in linear arithmetic, which allows application of existing highly optimized Linear Programming solvers in a black-box fashion. We provide experimental evidence of the practical applicability of our algorithm.     

Analysis of adaptive step-size SA algorithms for parameter tracking

We present proofs and data for adaptive step-size algorithms for tracking time-varying parameters when recursive stochastic approximation type algorithms are used. A classical problem in adaptive control and communication theory concerns the tracking of the best fit of a given form when the statistics or the parameters change slowly. A major, and yet unresolved, problem has been the choice of the step sizes in the tracking algorithm. An algorithm for adapting the step size using the same system measurements which are used for the tracking was suggested by Benveniste and various examples worked out by Brossier. The numerical results were very encouraging. But proofs were lacking. These proofs are supplied here together with supporting numerical data. The proofs are based on recent results in stochastic approximation. The adaptive step-size technique works very well indeed. Much supporting analysis is presented, particularly concerning the interpretation of certain stationary processes as “stationary” pathwise derivatives. Finite difference forms are also treated. These are mathematically simpler and can be applied to a wide variety of systems, even when the system is not well modeled. The data shows that they work well     

Deducible and Equivalent Structural Knowledges in Distributed Algorithms

The correctness of distributed algorithms usually relies upon the use of some knowledge about the underlying network (a specific topology, some metrics, etc.). We define equivalent structural knowledges to be such knowledges that can be computed distributively, one knowing the other. We present a combinatorial characterization of this equivalence. Some applications are also given: zero knowledge, classical metrics (size, diameter, etc.). This characterization is defined in terms of graphs coverings and quasicoverings. The proofs are based upon an algorithm proposed by Mazurkiewicz, and on techniques of termination detection by Shy, Szymanski, and Prywes.     

Lower bounds for the polynomial calculus

We show that polynomial calculus proofs (sometimes also called Groebner proofs) of the pigeonhole principle must have degree at least over any field. This is the first non-trivial lower bound on the degree of polynomial calculus proofs obtained without using unproved complexity assumptions. We also show that for some modifications of , expressible by polynomials of at most logarithmic degree, our bound can be improved to linear in the number of variables. Finally, we show that for any Boolean function in n variables, every polynomial calculus proof of the statement “ cannot be computed by any circuit of size t,” must have degree . Loosely speaking, this means that low degree polynomial calculus proofs do not prove . Received: January 15, 1997.     

Deductive Synthesis of Numerical Simulation Programs from Networks of Algebraic and Ordinary Differential Equations

Scientists and engineers face recurring problems of constructing, testing and modifying numerical simulation programs. The process of coding and revising such simulators is extremely time-consuming, because they are almost always written in conventional programming languages. Scientists and engineers can therefore benefit from software that facilitates construction of programs for simulating physical systems. Our research adapts the methodology of deductive program synthesis to the problem of constructing numerical simulation codes. We have focused on simulators that can be represented as second order functional programs composed of numerical integration and root extraction routines. We have developed a system that uses first order Horn logic to synthesize numerical simulators built from these components. Our approach is based on two ideas: first, we axiomatize only the relationship between integration and differentiation. We neither attempt nor require a complete axiomatization of mathematical analysis. Second, our system uses a representation in which functions are reified as objects. Function objects are encoded as lambda expressions. Our knowledge base includes an axiomatization of term equality in the lambda calculus. It also includes axioms defining the semantics of numerical integration and root extraction routines. We use depth bounded SLD resolution to construct proofs and synthesize programs. Our system has successfully constructed numerical simulators for computational design of jet engine nozzles and sailing yachts, among others. Our results demonstrate that deductive synthesis techniques can be used to construct numerical simulation programs for realistic applications.     

Lifting lower bounds for tree-like proofs

It is known that constant-depth Frege proofs of some tautologies require exponential size. No such lower bound result is known for more general proof systems. We consider tree-like sequent calculus proofs in which formulas can contain modular connectives and only the cut formulas are restricted to be of constant depth. Under a plausible hardness assumption concerning small-depth Boolean circuits, we prove exponential lower bounds for such proofs. We prove these lower bounds directly from the computational hardness assumption. We start with a lower bound for cut-free proofs and “lift” it so it applies to proofs with constant-depth cuts. By using the same approach, we obtain the following additional results. We provide a much simpler proof of a known unconditional lower bound in the case where modular connectives are not used. We establish a conditional exponential separation between the power of constant-depth proofs that use different modular connectives. We show that these tree-like proofs with constant-depth cuts cannot polynomially simulate similar dag-like proofs, even when the dag-like proofs are cut-free. We present a new proof of the non-finite axiomatizability of the theory of bounded arithmetic I Δ₀(R). Finally, under a plausible hardness assumption concerning the polynomial-time hierarchy, we show that the hierarchy \({G_i^*}\) of quantified propositional proof systems does not collapse.     

Rotation Averaging

This paper is conceived as a tutorial on rotation averaging, summarizing the research that has been carried out in this area; it discusses methods for single-view and multiple-view rotation averaging, as well as providing proofs of convergence and convexity in many cases. However, at the same time it contains many new results, which were developed to fill gaps in knowledge, answering fundamental questions such as radius of convergence of the algorithms, and existence of local minima. These matters, or even proofs of correctness have in many cases not been considered in the Computer Vision literature. We consider three main problems: single rotation averaging, in which a single rotation is computed starting from several measurements; multiple-rotation averaging, in which absolute orientations are computed from several relative orientation measurements; and conjugate rotation averaging, which relates a pair of coordinate frames. This last is related to the hand-eye coordination problem and to multiple-camera calibration.     

Distant Decimals of $$\pi $$: Formal Proofs of Some Algorithms Computing Them and Guarantees of Exact Computation

We describe how to compute very far decimals of \(\pi \) and how to provide formal guarantees that the decimals we compute are correct. In particular, we report on an experiment where 1 million decimals of \(\pi \) and the billionth hexadecimal (without the preceding ones) have been computed in a formally verified way. Three methods have been studied, the first one relying on a spigot formula to obtain at a reasonable cost only one distant digit (more precisely a hexadecimal digit, because the numeration basis is 16) and the other two relying on arithmetic–geometric means. All proofs and computations can be made inside the Coq system. We detail the new formalized material that was necessary for this achievement and the techniques employed to guarantee the accuracy of the computed digits, in spite of the necessity to work with fixed precision numerical computation.     

Classifying and Formally Verifying Integer Constant Folding

Constant folding is a well-known optimization of compilers which evaluates constant expressions already at compile time. Constant folding is valid only if the results computed by the compiler are exactly the same as the results which would be computed at run-time by the target machine arithmetic. We classify different arithmetics by deriving a general condition under which a target-machine arithmetic can be replaced by a compiler arithmetic. Furthermore, we consider integer arithmetics as a special case. They can be described by residue class arithmetics. We show that these arithmetics form a lattice. Using the order relation in this lattice, we establish a necessary and sufficient criterion under which constant folding can be done in a residue class arithmetic that is different from the one of the target machine. Concerning formal verification, we have formalized our proofs in the Isabelle/HOL system. As examples, we discuss the Java and C integer arithmetics and show which compiler arithmetics are valid for constant folding. This discussion reveals also potential sources of incorrect behavior of C compilers.     

Autarkic Computations in Formal Proofs

Formal proofs in mathematics and computer science are being studied because these objects can be verified by a very simple computer program. An important open problem is whether these formal proofs can be generated with an effort not much greater than writing a mathematical paper in, say, LATEX. Modern systems for proof development make the formalization of reasoning relatively easy. However, formalizing computations in such a manner that the results can be used in formal proofs is not immediate. In this paper we show how to obtain formal proofs of statements such as Prime(61) in the context of Peano arithmetic or (x+1)(x+1)=x ²+2x+1 in the context of rings. We hope that the method will help bridge the gap between the efficient systems of computer algebra and the reliable systems of proof development.     

An augmented Lagrangian decomposition method for quasi-separable problems in MDO

Several decomposition methods have been proposed for the distributed optimal design of quasi-separable problems encountered in Multidisciplinary Design Optimization (MDO). Some of these methods are known to have numerical convergence difficulties that can be explained theoretically. We propose a new decomposition algorithm for quasi-separable MDO problems. In particular, we propose a decomposed problem formulation based on the augmented Lagrangian penalty function and the block coordinate descent algorithm. The proposed solution algorithm consists of inner and outer loops. In the outer loop, the augmented Lagrangian penalty parameters are updated. In the inner loop, our method alternates between solving an optimization master problem and solving disciplinary optimization subproblems. The coordinating master problem can be solved analytically; the disciplinary subproblems can be solved using commonly available gradient-based optimization algorithms. The augmented Lagrangian decomposition method is derived such that existing proofs can be used to show convergence of the decomposition algorithm to Karush–Kuhn–Tucker points of the original problem under mild assumptions. We investigate the numerical performance of the proposed method on two example problems.     

Numerical solution of the time-dependent Dirac equation in coordinate space without fermion-doubling

The validation and parallel implementation of a numerical method for the solution of the time-dependent Dirac equation is presented. This numerical method is based on a split operator scheme where the space–time dependence is computed in coordinate space using the method of characteristics. Thus, most of the steps in the splitting are calculated exactly, making for a very efficient and unconditionally stable method. We show that it is free from spurious solutions related to the fermion-doubling problem and that it can be parallelized very efficiently. We consider a few simple physical systems such as the time evolution of Gaussian wave packets and the Klein paradox. The numerical results obtained are compared to analytical formulas for the validation of the method.     

Constrained least absolute deviation neural networks.

It is well known that least absolute deviation (LAD) criterion or L(1)-norm used for estimation of parameters is characterized by robustness, i.e., the estimated parameters are totally resistant (insensitive) to large changes in the sampled data. This is an extremely useful feature, especially, when the sampled data are known to be contaminated by occasionally occurring outliers or by spiky noise. In our previous works, we have proposed the least absolute deviation neural network (LADNN) to solve unconstrained LAD problems. The theoretical proofs and numerical simulations have shown that the LADNN is Lyapunov-stable and it can globally converge to the exact solution to a given unconstrained LAD problem. We have also demonstrated its excellent application value in time-delay estimation. More generally, a practical LAD application problem may contain some linear constraints, such as a set of equalities and/or inequalities, which is called constrained LAD problem, whereas the unconstrained LAD can be considered as a special form of the constrained LAD. In this paper, we present a new neural network called constrained least absolute deviation neural network (CLADNN) to solve general constrained LAD problems. Theoretical proofs and numerical simulations demonstrate that the proposed CLADNN is Lyapunov stable and globally converges to the exact solution to a given constrained LAD problem, independent of initial values. The numerical simulations have also illustrated that the proposed CLADNN can be used to robustly estimate parameters for nonlinear curve fitting, which is extensively used in signal and image processing.     

PROPOSITIONAL DYNAMIC LOGIC FOR REASONING ABOUT FIRST‐CLASS AGENT INTERACTION PROTOCOLS

For agents to fulfill their potential of being intelligent and adaptive, it is useful to model their interaction protocols as executable entities that can be referenced, inspected, composed, shared, and invoked between agents, all at runtime. We use the term first‐class protocol to refer to such protocols. Rather than having hard‐coded decision‐making mechanisms for choosing their next move, agents can inspect the protocol specification at runtime to do so, increasing their flexibility. In this article, we show that propositional dynamic logic (PDL) can be used to represent and reason about the outcomes of first‐class protocols. We define a proof system for PDL that permits reasoning about recursively defined protocols. The proof system is divided into two parts: one for reasoning about terminating protocols, and one for reasoning about nonterminating protocols. We prove that proofs about terminating protocols can be automated, while proofs about nonterminating protocols are unable to be automated in some cases. We prove that, for a restricted class of nonterminating protocols, proofs about them can be transformed to proofs about terminating protocols, making them automatable.     

Connecting Logical Representations and Efficient Computations

When combining logic level theorem proving with computational methods it is important to identify both functions that can be efficiently computed and the objects they can be applied to. This is generally achieved by mappings of logic level terms and functions to their computational counterparts. However, these mappings are often quite ad hoc and fragile depending very much on the particular logic representations of terms. We present a method of annotating terms in logic proofs with their computational properties. This enables the compact representation of computational objects in deduction systems as well as their connection to functions that can be easily computed for them. This eases the identification of deduction problems that can be treated efficiently by computational methods and also abstracts from trivial properties that are artefacts of a particular representation. We ensure logical correctness of our concepts by providing the possibility to replace terms by their logical representation and by expanding computational procedures by tactic application that can be rigorously checked.     

Proof Transformation via Interpretation Functions: Results, Problems and Applications

Change is a constant factor in Software Engineering process. Redesign of a class structure requires transformation of the corresponding OCL constraints. In a previous paper we have shown how to use, what we call, interpretation functions for transformation of constraints. In this paper we discuss recently obtained results concerning proof transformations via such functions. In particular we detail the fact that they preserve proofs in equational logic, as well as proofs in other logical systems like propositional logic with modus ponens or proofs using resolution rule. Those results have direct applications to redesign of UML State Machines and Sequence Diagrams. If states in a State Machine are interpreted by State Invariants, then the topological relations between its states can be interpreted as logical relations between the corresponding formulas. Preservation of the consequence relation can bee seen as preservation of the topology of State Machines. We indicate also an unsolved problem and discuss the mining of its positive solution.     

Proofs, Programs, Processes

The objective of this paper is to provide a theoretical foundation for program extraction from inductive and coinductive proofs geared to practical applications. The novelties consist in the addition of inductive and coinductive definitions to a realizability interpretation for first-order proofs, a soundness proof for this system, and applications to the synthesis of non-trivial provably correct programs in the area of exact real number computation. We show that realizers, although per se untyped, can be assigned polymorphic recursive types and hence represent valid programs in a lazy functional programming language such as Haskell. Programs extracted from proofs using coinduction can be understood as perpetual processes producing infinite streams of data. Typical applications of such processes are computations in exact real arithmetic. As an example we show how to extract a program computing the average of two real numbers w.r.t. the binary signed digit representation.     

Justifying Equality

We consider the problem of finding irredundant bases for inconsistent sets of equalities and disequalities. These are subsets of inconsistent sets which do not contain any literals which do not contribute to the unsatisfiability in an essential way, and can therefore be discarded. The approach we are pursuing here is to decorate derivations with proofs and to extract irredundant sets of assumptions from these proofs. This requires specialized operators on proofs, but the basic inference systems are otherwise left unchanged. In particular, we include justifying inference systems for union-find structures and abstract congruence closure, but our constructions can also be applied to other inference systems such as Gaussian elimination.     

Stochastic approximation with dependent disturbances—I

A generalization of Robbins-Monro stochastic approximation is presented in the paper. It is shown that, if disturbances satisfy a sort of generalized law of large numbers then an appropriate stochastic approximation procedure converges almost surely or only in probability, depending on what kind of law of large numbers (strong or weak) is satisfied by disturbances. In that sense theorems presented in the paper generalize Robbins-Monro stochastic approximation schemes, because the law of large numbers can be satisfied, as is well-known, by sequences of dependent random variables.

On the other hand, as theorem of Gladishev (a generalized version of Robbins-Monro theorem) can be obtained from the results presented in the paper (see Theorem 10), one can consider this paper as the one providing new proofs for different versions of stochastic approximation. The proofs of the theorems of the paper are different than usual proofs of stochastic approximation procedure. In particular, they are not based on the Martingale convergence theorem. Roughly speaking the proofs exploit the analogy between the stochastic approximation procedures of Robbins-Monro versions and deterministic numerical iterative procedures seeking zeros of the system of nonliner equations.

As the results of the paper were thought to be applied to estimation of parameters of discrete stochastic processes (so called identification) special notation has been introduced. This notation is believed to be useful for the above purpose.     

Semidefinite programming duality and linear time-invariant systems

Several important problems in control theory can be reformulated as semidefinite programming problems, i.e., minimization of a linear objective subject to linear matrix inequality (LMI) constraints. From convex optimization duality theory, conditions for infeasibility of the LMIs, as well as dual optimization problems, can be formulated. These can in turn be reinterpreted in control or system theoretic terms, often yielding new results or new proofs for existing results from control theory. We explore such connections for a few problems associated with linear time-invariant systems.