Dualization Problem over the Product of Chains: Asymptotic Estimates for the Number of Solutions

A key intractable problem in logical data analysis, namely, dualization over the product of partial orders, is considered. The important special case where each order is a chain is studied. If the cardinality of each chain is equal to two, then the considered problem is to construct a reduced disjunctive normal form of a monotone Boolean function defined by a conjunctive normal form, which is equivalent to the enumeration of irreducible coverings of a Boolean matrix. The asymptotics of the typical number of irreducible coverings is known in the case where the number of rows in the Boolean matrix has a lower order of growth than the number of columns. In this paper, a similar result is obtained for dualization over the product of chains when the cardinality of each chain is higher than two. Deriving such asymptotic estimates is a technically complicated task, and they are required, in particular, for proving the existence of asymptotically optimal algorithms for the problem of monotone dualization and its generalizations.     

Incremental polynomial time dualization of quadratic functions and a subclass of degree-<Emphasis Type="Italic">k</Emphasis> functions

We consider the problem of dualizing a Boolean function f represented by a DNF. In its most general form, this problem is commonly believed not to be solvable by a quasi-polynomial total time algorithm. We show that if the input DNF is quadratic or is a special degree-k DNF, then dualization turns out to be equivalent to hypergraph dualization in hypergraphs of bounded degree and hence it can be achieved in incremental polynomial time.     

On the complexity of the dualization problem

The computational complexity of discrete problems concerning the enumeration of solutions is addressed. The concept of an asymptotically efficient algorithm is introduced for the dualization problem, which is formulated as the problem of constructing irreducible coverings of a Boolean matrix. This concept imposes weaker constraints on the number of “redundant” algorithmic steps as compared with the previously introduced concept of an asymptotically optimal algorithm. When the number of rows in a Boolean matrix is no less than the number of columns (in which case asymptotically optimal algorithms for the problem fail to be constructed), algorithms based on the polynomialtime-delay enumeration of “compatible” sets of columns of the matrix is shown to be asymptotically efficient. A similar result is obtained for the problem of searching for maximal conjunctions of a monotone Boolean function defined by a conjunctive normal form.     

On a poset algebra which is hereditarily but not canonically well generated

LetB be a superatomic Boolean algebra.B is well generated, if it has a well founded sublatticeL such thatL generatesB. The free product of Boolean algebrasB andC is denoted byB *C. IfC is a chain thenB(C) denotes the interval algebra overC. Theorem 1: (a)Every Boolean subalgebra of B(ℵ₁) *B(ℵ₀)is well-generated. (b)B(ℵ₁) *B(ℵ₁)contains a non well-generated Boolean subalgebra. Canonical well-generatedness is defined in the introduction. Recall thatB(ℵ₁) *B(ℵ₀) is canonically well-generated, and thus well-generated. We prove the following result. Theorem 2:B(ℵ₁) *B(ℵ₀)contains a non canonically well generated Boolean subalgebra. In contrast with Theorem 1(b), we have the following result. Theorem 3:Let A ={ɑ:α<ℵ₁}⊆℘(w)be a strictly increasing sequence in the relation of almost containment. Let B be the subalgebra of ℘(w)generated by {{n}:n∈ℵ₀}∪A.Then B is superatomic, and B is not embeddable in a well-generated algebra.     

Numerical solution of eigenvalue problems for Hamiltonian systems

This paper discusses the numerical solution of eigenvalue problems for Hamiltonian systems of ordinary differential equations. Two new codes are presented which incorporate the algorithms described here; to the best of the author’s knowledge, these are the first codes capable of solving numerically such general eigenvalue problems. One of these implements a new new method of solving a differential equation whose solution is a unitary matrix. Both codes are fully documented and are written inPfort-verifiedFortran 77, and will be available in netlib/aicm/sl11f and netlib/aicm/sl12f.     

Projective Fraïssé limits and the pseudo-arc

The aim of the present work is to develop a dualization of the Fraïssé limit construction from model theory and to indicate its surprising connections with the pseudo-arc. As corollaries of general results on the dual Fraïssé limits, we obtain Mioduszewski's theorem on surjective universality of the pseudo-arc among chainable continua and a theorem on projective homogeneity of the pseudo-arc (which generalizes a result of Lewis and Smith on density of homeomorphisms of the pseudo-arc among surjective continuous maps from the pseudo-arc to itself). We also get a new characterization of the pseudo-arc via the projective homogeneity property.

     

Complexity of Boolean algebras and their Scott rank

We deal with problems associated with Scott ranks of Boolean algebras. The Scott rank can be treated as some measure of complexity of an algebraic system. Our aim is to propound and justify the procedure which, given any countable Boolean algebra, will allow us to construct a Boolean algebra of a small Scott rank that has the same natural algebraic complexity as has the initial algebra. In particular, we show that the Scott rank does not always serve as a good measure of complexity for the class of Boolean algebras. We also study into the question as to whether or not a Boolean algebra of a big Scott rank can be decomposed into direct summands with intermediate ranks. Examples are furnished in which Boolean algebras have an arbitrarily big Scott rank such that direct summands in them either have a same rank or a fixed small one, and summands of intermediate ranks are altogether missing. This series of examples indicates, in particular, that there may be no nontrivial mutual evaluations for the Scott and Frechet ranks on a class of countable Boolean algebras. Supported by RFFR grant No. 99-01-00485, by a grant for Young Scientists from SO RAN, 1997, and by the Federal Research Program (FRP) “Integration”. Translated fromAlgebra i Logika, Vol. 38, No. 6, pp. 643–666, November–December, 1999.     

Analysis of augmented three-field macro-hybrid mixed finite element schemes

On the basis of composition duality principles, augmented three-field macro- hybrid mixed variational problems and finite element schemes are analyzed. The compatibility condition adopted here, for compositional dualization, is the coupling operator surjectivity, property that expresses in a general operator sense the Ladyenskaja-Babuka-Brezzi inf-sup condition. Variational macro-hybridization is performed under the assumption of decomposable primal and dual spaces relative to nonoverlapping domain decomp...     

An analytical approach to global optimization

Global optimization problems with a few variables and constraints arise in numerous applications but are seldom solved exactly. Most often only a local optimum is found, or if a global optimum is detected no proof is provided that it is one. We study here the extent to which such global optimization problems can be solved exactly using analytical methods. To this effect, we propose a series of tests, similar to those of combinatorial optimization, organized in a branch-and-bound framework. The first complete solution of two difficult test problems illustrates the efficiency of the resulting algorithm. Computational experience with the programbagop, which uses the computer algebra systemmacsyma, is reported on. Many test problems from the compendiums of Hock and Schittkowski and others sources have been solved.The research of the first and the third authors has been supported by AFOSR grants #0271 and #0066 to Rutgers University. Research of the second author has been supported by NSERC grant #GP0036426 and FCAR grants #89EQ4144 and #90NC0305.     

Constructibility of Boolean algebras of elementary characteristic (1,0,1)

We deal with problems of finding a criterion of being strongly constructivizable for Boolean algebras. An example of a constructive but not strongly constructivizable Boolean algebra of characteristic (1, 0, 1) with a decidable set of atoms is constructed, and the construction is then generalized to the case of an arbitrary characteristic (k+1,0,1). Supported by the RFFR grant No. 96-01-01525. Translated fromAlgebra i Logika, Vol. 37, No. 5, pp. 499–521, September–October, 1998.     

Idempotent Boolean matrices and majorization

We obtain a new structural characterization of idempotent Boolean matrices. This characterization allows us to describe all Boolean matrices that are majorized by a given idempotent. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 1, pp. 11–29, 2007.     

Computational aspects of monotone dualization: A brief survey

Dualization of a monotone Boolean function represented by a conjunctive normal form (CNF) is a problem which, in different disguise, is ubiquitous in many areas including Computer Science, Artificial Intelligence, and Game Theory to mention some of them. It is also one of the few problems whose precise tractability status (in terms of polynomial-time solvability) is still unknown, and now open for more than 25 years. In this paper, we briefly survey computational results for this problem, where we focus on the famous paper by Fredman and Khachiyan [On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms 21 (1996) 618-628], which showed that the problem is solvable in quasi-polynomial time (and thus most likely not co-NP-hard), as well as on follow-up works. We consider computational aspects including limited nondeterminism, probabilistic computation, parallel and learning-based algorithms, and implementations and experimental results from the literature. The paper closes with open issues for further research.     

An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation

Given a finite set V, and a hypergraph H⊆2^V, the hypergraph transversal problem calls for enumerating all minimal hitting sets (transversals) for H. This problem plays an important role in practical applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan [On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms 21 (1996) 618-628] gave an incremental quasi-polynomial-time algorithm for solving the hypergraph transversal problem. In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same theoretical worst-case bound, practical experience with this implementation shows that it can be substantially faster. We also show that a slight modification of the original algorithm can be used to obtain a stronger bound on the running time.More generally, we consider a monotone property π over a bounded n-dimensional integral box. As an important application of the above hypergraph transversal problem, pioneered by Bioch and Ibaraki [Complexity of identification and dualization of positive Boolean functions, Inform. and Comput. 123 (1995) 50-63], we consider the problem of incrementally generating simultaneously all minimal subsets satisfying π and all maximal subsets not satisfying π, for properties given by a polynomial-time satisfiability oracle. Problems of this type arise in many practical applications. It is known that the above joint generation problem can be solved in incremental quasi-polynomial time via a polynomial-time reduction to a generalization of the hypergraph transversal problem on integer boxes. In this paper we present an efficient implementation of this procedure, and present experimental results to evaluate our implementation for a number of interesting monotone properties π.     

Vectorial Resilient PC（l） of Order k Boolean Functions from AG-Codes

Propagation criteria and resiliency of vectorial Boolean functions are important for cryptographic purpose (see [1–4, 7, 8, 10, 11, 16]). Kurosawa, Stoh [8] and Carlet [1] gave a construction of Boolean functions satisfying PC(l) of order k from binary linear or nonlinear codes. In this paper, the algebraic-geometric codes over GF(2m) are used to modify the Carlet and Kurosawa-Satoh’s construction for giving vectorial resilient Boolean functions satisfying PC(l) of order k criterion. This new construction is compared with previously known results.     

Order topology in vector lattices with closure by one step

An order topology in vector lattices and Boolean algebras is studied under the additional condition of “closure by one step” that generalizes the well-known “regularity” property of Boolean algebras and K-spaces. It is proved that in a vector lattice or a Boolean algebra possessing such a property there exists a basis of solid neighborhoods of zero with respect to an order topology. An example of a Boolean algebra without basis of solid neighborhoods of zero (an algebra of regular open subsets of the interval (0, 1)) is given. Bibliography: 3 titles. Translated fromProblemy Matematicheskogo Analiza, No. 15 1995, pp. 213–220.     

On the local convergence of adjoint Broyden methods

The numerical solution of nonlinear equation systems is often achieved by so-called quasi-Newton methods. They preserve the rapid local convergence of Newton’s method at a significantly reduced cost per step by successively approximating the system Jacobian though low-rank updates. We analyze two variants of the recently proposed adjoint Broyden update, which for the first time combines the classical least change property with heredity on affine systems. However, the new update does require, the evaluation of so-called adjoint vectors, namely products of the transposed Jacobian with certain dual direction vectors. The resulting quasi-Newton method is linear contravariant in the sense of Deuflhard (Newton methods for nonlinear equations. Springer, Heidelberg, 2006) and it is shown here to be locally and q-superlinearly convergent. Our numerical results on a range of test problems demonstrate that the new method usually outperforms Newton’s and Broyden’s method in terms of runtime and iterations count, respectively. Partially supported by the DFG Research Center Matheon “Mathematics for Key Technologies”, Berlin and the DFG grant WA 1607/2-1.     

Formal aspects of a theory for pairs of linear ordinary differential operators in the regular case

Summary The ordinary differential equation Su=λTu containing two operators and a parameter λ is considered on a compact interval. Boundary conditions, homogeneous and non-homogeneous problems, expansions in terms of associated eigenfunctions etc. are parallelled with the classical case when T=1. In homage to ProfessorBeniamino Segre Entrata in Redazione il 15 giugno 1973.     

Two-letter group codes that preserve aperiodicity of inverse finite automata

We construct group codes over two letters (i.e., bases of subgroups of a two-generated free group) with special properties. Such group codes can be used for reducing algorithmic problems over large alphabets to algorithmic problems over a two-letter alphabet. Our group codes preserve aperiodicity of inverse finite automata. As an application we show that the following problems are PSpace-complete for two-letter alphabets (this was previously known for large enough finite alphabets): The intersection-emptiness problem for inverse finite automata, the aperiodicity problem for inverse finite automata, and the closure-under-radical problem for finitely generated subgroups of a free group. The membership problem for 3-generated inverse monoids is PSpace-complete. Both authors were supported in part by NSF grant DMS-9970471. The first author was also supported in part by NSF grant CCR-0310793. The second author acknowledges the support of the Excellency Center, “Group Theoretic Methods for the Study of Algebraic Varieties” of the Israeli Science Foundation.     

Polyhedral annexaton,dualization and dimension reduction technique in global optimization

We demonstrate how the size of certain global optimization problems can substantially be reduced by using dualization and polyhedral annexation techniques. The results are applied to develop efficient algorithms for solving concave minimization problems with a low degree of nonlinearity. This class includes in particular nonconvex optimization problems involving products or quotients of affine functions in the objective function.This work was completed while the author was visiting the Department of Mathematics of Linköping University.