An algorithm to learn read-once threshold formulas,and transformations between learning models

We present a membership query (i.e. black box interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of Boolean threshold functions. We also present a catalogue of generic transformations that can be used to convert an algorithm in one learning model into an algorithm in a different model.     

Satisfiability of co-nested formulas

As a notion dual to Knuth's nested formulas [4], we call a boolean formula in conjunctive normal formco-nested if its clauses can be linearly ordered (sayC={c _i ;i=1,2, ...,n})so that the graphG ^cl =(XC, {xc _i ;xc _i or ¬xc _i } {c _i c _i+1;i=1, 2, ...,n}) allows a noncrossing drawing in the plane so that the circlec ₁,c ₂, ...,c _n bounds the outerface. Our main result is that maximum satisfiability of co-nested formulas can be decided in linear time.Both authors acknowledge a partial support of Ec Cooperative Action IC-1000 (project ALTEC:Algorithms for Future Technologies).     

Reducing signed propositional formulas

 New strategies of reduction for finite-valued propositional logics are introduced in the framework of the TAS¹ methodology developed by the authors [1]. A new data structure, the Δ^-sets, is introduced to store information about the formula being analysed, and its usefulness is shown by developing efficient strategies to decrease the size of signed propositional formulas, viz., new criteria to detect the validity or unsatisfiability of subformulas, and a strong generalisation of the pure literal rule.     

Short proofs for tricky formulas

Summary The object of this paper is to demonstrate how certain tricky mathematical arguments can be encoded as short formal proofs for the propositional tautologies representing the mathematical statements. Using resolution as a base proof system for the propositional calculus, we exhibit these short proofs under resolution augmented by one of two principles: the principle of extension, originally suggested by Tseitin, and the principle of symmetry, introduced in this paper. These short proofs illustrate the power of extension and symmetry in theorem proving.The principle of extension allows the introduction of auxiliary variables to represent intermediate formulas so that the length of a proof can be significantly reduced by manipulating these variables instead of the formulas that they stand for. Symmetry, on the other hand, allows one to recognize that a tautology remains invariant under certain permutations of variable names, and use that information to avoid repeated independent derivations of intermediate formulas that are merely permutational variants of one another.First we show that a number of inductive arguments can be encoded as short formal proofs using either extension or symmetry. We provide the details for the tautologies derived by encoding the statement, An acyclic digraph on n vertices must have a source. We then consider the familiar checkerboard puzzle which asserts that a checkerboard, two of whose diagonally opposite corner squares are removed, cannot be perfectly covered with dominoes. We demonstrate short proofs for the tautologies derived from the above assertion, using extension to mimic the tricky informal argument. Finally, we consider statements asserting the Ramsey property of numbers much larger than the critical Ramsey numbers. We show that the proof of Ramsey's theorem can be imitated using the principle of symmetry to yield short proofs for these tautologies.The main theme of the paper is that both extension and symmetry are very powerful augmentations to resolution. We leave open whether either extension or symmetry can polynomially simulate the other.This work was performed while the author was with the General Electric Research Center     

Generalizations of matched CNF formulas

A CNF formula is called matched if its associated bipartite graph (whose vertices are clauses and variables) has a matching that covers all clauses. Matched CNF formulas are satisfiable and can be recognized efficiently by matching algorithms. We generalize this concept and cover clauses by collections of bicliques (complete bipartite graphs). It turns out that such generalization indeed gives rise to larger classes of satisfiable CNF formulas which we term biclique satisfiable. We show, however, that the recognition of biclique satisfiable CNF formulas is NP-complete, and remains NP-hard if the size of bicliques is bounded. A satisfiable CNF formula is called var-satisfiable if it remains satisfiable under arbitrary replacement of literals by their complements. Var-satisfiable CNF formulas can be viewed as the best possible generalization of matched CNF formulas as every matched CNF formula and every biclique satisfiable CNF formula is var-satisfiable. We show that recognition of var-satisfiable CNF formulas is ₂ ^P-complete, answering a question posed by Kleine Büning and Zhao.     

Optimal weighted chebyshev-type quadrature formulas

A weighted quadrature formula is called of Chebyshev type if it has equal coefficients and real (but not necessarily distinct) nodes. Among such quadrature rules we construct an optimal one, i. e., one which has maximum algebraic degree of accuracy and minimum error when applied to the first power not exactly integrated. Optimal quadrature rules, typically, have multiple nodes. Their construction requires the complete solution of systems of algebraic equations involving generalized power sums. Numerical results are presented for the case of constant weight function on a finite interval, as well as for weight functions of the Hermite and Laguerre type on infinite intervals. The work of the second author was supported in part by the National Science Foundation under grant GP-36557     

New symmetric interpolatory quadrature formulas

We introduce two families of symmetric, interpolatory integration formulas on the interval [−1,1]. These formulas, related to the class of recursive monotone stable (RMS) formulas, allow the application of higher order or compound rules with an efficient reuse of computed function values. One family (SM) uses function values computed outside the integration interval, the other one (HR) uses derivative data. These formulas are evaluated using a practical test based on a tecnique for comparing automatic quadrature routine introduced by Lyness and Kaganove and improved by the authors. Work supported by CNR, Grant no. 93.00570, CT01     

Efficiently solving quantified bit-vector formulas

In recent years, bit-precise reasoning has gained importance in hardware and software verification. Of renewed interest is the use of symbolic reasoning for synthesising loop invariants, ranking functions, or whole program fragments and hardware circuits. Solvers for the quantifier-free fragment of bit-vector logic exist and often rely on SAT solvers for efficiency. However, many techniques require quantifiers in bit-vector formulas to avoid an exponential blow-up during construction. Solvers for quantified formulas usually flatten the input to obtain a quantified Boolean formula, losing much of the word-level information in the formula. We present a new approach based on a set of effective word-level simplifications that are traditionally employed in automated theorem proving, heuristic quantifier instantiation methods used in SMT solvers, and model finding techniques based on skeletons/templates. Experimental results on two different types of benchmarks indicate that our method outperforms the traditional flattening approach by multiple orders of magnitude of runtime.     

Algebraic proofs over noncommutative formulas

We study possible formulations of algebraic propositional proof systems operating with noncommutative formulas. We observe that a simple formulation gives rise to systems at least as strong as Frege, yielding a semantic way to define a Cook-Reckhow (i.e., polynomially verifiable) algebraic analog of Frege proofs, different from that given in Buss et al. (1997) and Grigoriev and Hirsch (2003). We then turn to an apparently weaker system, namely, polynomial calculus (PC) where polynomials are written as ordered formulas (PC over ordered formulas, for short). Given some fixed linear order on variables, an arithmetic formula is ordered if for each of its product gates the left subformula contains only variables that are less-than or equal, according to the linear order, than the variables in the right subformula of the gate. We show that PC over ordered formulas (when the base field is of zero characteristic) is strictly stronger than resolution, polynomial calculus and polynomial calculus with resolution (PCR), and admits polynomial-size refutations for the pigeonhole principle and Tseitin?s formulas. We conclude by proposing an approach for establishing lower bounds on PC over ordered formulas proofs, and related systems, based on properties of lower bounds on noncommutative formulas (Nisan, 1991).The motivation behind this work is developing techniques incorporating rank arguments (similar to those used in arithmetic circuit complexity) for establishing lower bounds on propositional proofs.     

Generalizations of matched CNF formulas

A CNF formula is called matched if its associated bipartite graph (whose vertices are clauses and variables) has a matching that covers all clauses. Matched CNF formulas are satisfiable and can be recognized efficiently by matching algorithms. We generalize this concept and cover clauses by collections of bicliques (complete bipartite graphs). It turns out that such generalization indeed gives rise to larger classes of satisfiable CNF formulas which we term biclique satisfiable. We show, however, that the recognition of biclique satisfiable CNF formulas is NP-complete, and remains NP-hard if the size of bicliques is bounded. A satisfiable CNF formula is called var-satisfiable if it remains satisfiable under arbitrary replacement of literals by their complements. Var-satisfiable CNF formulas can be viewed as the best possible generalization of matched CNF formulas as every matched CNF formula and every biclique satisfiable CNF formula is var-satisfiable. We show that recognition of var-satisfiable CNF formulas is _P ² P-complete, answering a question posed by Kleine Büning and Zhao.     

Generalized trapezoidal formulas for parabolic equations

We investigate the application of the one-parameter family of generalized trapezoidal formulas (GTFs) introduced in Chawla et al. [2] for the time-integration of parabolic equations. The resulting GTF finite-difference schemes (GTF-FDS) are, in general, second order in both time and space and unconditionally stable. Interestingly, there exists a method of the family which is third order in time. Unlike the popular Crank -Nicolson scheme, our present GTF-FDS can cope with discontinuities in the boundary conditions and the initial conditions. We consider extensions of the GTF-FDS for equations with derivative boundary conditions and to a nonlinear problem. Numerical experiments demonstrate the superiority of the present GTF-FDS, especially for the case of problems with discontinuities in the boundary and the initial conditions.     

On the depth complexity of formulas

The problem of minimizing the depth of formulas by equivalence preserving transformations is formalized in a general algebraic setting. For a particular algebraic system ∑₀ specific methods of a dynamic programming nature are developed for proving lower bounds on depth. Such lower bounds for ∑₀ automatically imply the same results for the systems of (i) arithmetic computations with addition and multiplication only, and (ii) computations over finite languages using union and concatenation. The specific lower bounds obtained are (i) depth 2n?o(n) for the permanent, (ii) depth (0.25+o(1))log² n for the symmetric polynomials and (iii) depth 1.16logn for a problem of formula sizen.     

h-space structure in matrix displacement formulas

A class of spaces of matrices, calledh-spaces, is considered, extending previous results in [R. Bevilacqua, P. Zellini,Closure, commutativity and minmal complexity of some space of matrices, Linear and Multilinear Algebra,25, (1989) 1–25]. These spaces include several known classes of matrix algebras, such as group matrix algebras and Hessenberg algebras and, in particular, certain symmetric closed 1-spaces, which are structurally related to Toeplitz plus Hankel-like matrices. Following the displacement rank technique, these spaces are involved in general displacement decomposition formulas of an arbitrary matrixA. These decompositions lead to a significant representation formula for the inverse of a centrosymmetric Toeplitz plus Hankel matrix.     

基于新阈值函数的小波阈值去噪算法

针对硬阈值函数不连续和软阈值函数中估计小波系数与分解小波系数之间存在着恒定偏差的缺点,构造了一种新的阈值函数.同时,为了增强去噪效果,采用了模糊控制算法对新阈值函数中的参数进行实时、动态地调节.仿真结果表明:新阈值函数去除噪声效果良好,信噪比和均方根误差等性能指标较传统阈值法均有显著提高.     

Converting untyped formulas to typed ones

We observe that every first-order logic formula over the untyped version of some many-sorted vocabulary is equivalent to a union of many-sorted formulas over that vocabulary. This result has as direct corollary a theorem by Hull and Su on the expressive power of active-domain quantification in the relational calculus. Received: 1 April 1998