Malicious Omissions and Errors in Answers to Membership Queries

We consider two issues in polynomial-time exact learning of concepts using membership and equivalence queries: (1) errors or omissions in answers to membership queries, and (2) learning finite variants of concepts drawn from a learnable class.To study (1), we introduce two new kinds of membership queries: limited membership queries and malicious membership queries. Each is allowed to give incorrect responses on a maliciously chosen set of strings in the domain. Instead of answering correctly about a string, a limited membership query may give a special I don't know answer, while a malicious membership query may give the wrong answer. A new parameter Lis used to bound the length of an encoding of the set of strings that receive such incorrect answers. Equivalence queries are answered correctly, and learning algorithms are allowed time polynomial in the usual parameters and L. Any class of concepts learnable in polynomial time using equivalence and malicious membership queries is learnable in polynomial time using equivalence and limited membership queries; the converse is an open problem. For the classes of monotone monomials and monotone k-term DNF formulas, we present polynomial-time learning algorithms using limited membership queries alone. We present polynomial-time learning algorithms for the class of monotone DNF formulas using equivalence and limited membership queries, and using equivalence and malicious membership queries.To study (2), we consider classes of concepts that are polynomially closed under finite exceptions and a natural operation to add exception tables to a class of concepts. Applying this operation, we obtain the class of monotone DNF formulas with finite exceptions. We give a polynomial-time algorithm to learn the class of monotone DNF formulas with finite exceptions using equivalence and membership queries. We also give a general transformation showing that any class of concepts that is polynomially closed under finite exceptions and is learnable in polynomial time using standard membership and equivalence queries is also polynomial-time learnable using malicious membership and equivalence queries. Corollaries include the polynomial-time learnability of the following classes using malicious membership and equivalence queries: deterministic finite acceptors, boolean decision trees, and monotone DNF formulas with finite exceptions.     

On the power of small-depth threshold circuits

We investigate the power of threshold circuits of small depth. In particular, we give functions that require exponential size unweighted threshold circuits of depth 3 when we restrict the bottom fanin. We also prove that there are monotone functionsf _k that can be computed in depthk and linear size , -circuits but require exponential size to compute by a depthk–1 monotone weighted threshold circuit.     

On Bounding Solutions of Underdetermined Systems

Sufficient conditions for the existence and uniqueness of a solution x* D (R ⁿ ) of Y(x) = 0 where : R ⁿ R ^m (m n) with C ²(D) where D R ⁿ is an open convex set and Y = (x)⁺ are given, and are compared with similar results due to Zhang, Li and Shen (Reliable Computing 5(1) (1999)). An algorithm for bounding zeros of f (·) is described, and numerical results for several examples are given.     

Synchronous and Asynchronous Interval Newton-Schwarz Methods for a Class of Large Systems of Nonlinear Equations

We introduce a class of parallel interval arithmetic iteration methods for nonlinear systems of equations, especially of the type Ax+(x) = f, diagonal, in R ^N . These methods combine enclosure and global convergence properties of Newton-like interval methods with the computational efficiency of parallel block iteration methods: algebraic forms of Schwarz-type methods which generalize both the well-known additive algebraic Schwarz Alternating Procedure and multisplitting methods. We discuss both synchronous and asynchronous variants. Besides enclosure and convergence properties, we present numerical results from a CRAY T3E.     

Context-free preserving functions

A functionf on the non-negative integers is a context-free preserving function (cfpf) if and only if for every context-free languageL, {x|(y) (xy L, and |y| =f(|x|))} is a context-free language. In this note we give an algebraic characterization of the class of cfpf's.This research was supported by the National Bureau of Standards under Contract 3-35999.     

Maximality and totality of stable functions in the category of stable bifinite domains

This paper studies maximality and totality of stable functions in the category of stable bifinite domains. We present three main results as follows,o

1. (1)every maximum-preserving function is a maximal element in the stable function spaces;
2. (2)a maximal stable function f : D → E is maximum-preserving if D is maximum-separable and E is completely separable; and
3. (3)a stable bifinite domain D is maximum-separable if and only if for any locally distributive stable bifinite domain E, each maximal stable function f : D → E is maximum-preserving.

     

Randomized function evaluation on a ring

LetR be a unidirectional asynchronous ring ofn identical processors each with a single input bit. Letf be any cyclic nonconstant function ofn boolean variables. Moran and Warmuth (1986) prove that anydeterministic algorithm that evaluatesf onR has communication complexity (n logn) bits. They also construct a family of cyclic nonconstant boolean functions that can be evaluated inO(n logn) bits by a deterministic algorithm.This contrasts with the following new results:

New Sequences with Zero Autocorrelation

New families of unimodular sequences of length p = 3f + 1 with zero autocorrelation are described, p being a prime. The construction is based on employing Gauss periods. It is shown that in this case elements of the sequences are algebraic numbers defined by irreducible polynomials over of degree 12 (for the first family) and 6 (for the second family). In turn, these polynomials are factorized in some extension of the field into polynomials of degree, respectively, 4 and 2, which are written explicitly. For p = 13, using the exhaustive search method, full classification of unimodular sequences with zero autocorrelation is given.     

Monotone data flow analysis frameworks

Summary We consider a generalization of Kildall's lattice theoretic approach to data flow analysis, which we call monotone data flow analysis frameworks. Many flow analysis problems which appear in practice meet the monotonicity condition but not Kildall's condition called distributivity. We show that the maximal fixed point solution exists for every instance of every monotone framework, and that it can be obtained by Kildall's algorithm. However, whenever the framework is monotone but not distributive, there are instances in which the desired solution—the meet over all paths solution — differs from the maximal fixed point. Finally, we show the nonexistence of an algorithm to compute the meet over all paths solution for monotone frameworks.Work supported by NSF grant GJ-1052.     

Conjunctions of Unate DNF Formulas: Learning and Structure

A central topic in query learning is to determine which classes of Boolean formulas are efficiently learnable with membership and equivalence queries. We consider the class ^kconsisting of conjunctions ofkunate DNF formulas. This class generalizes the class ofk-clause CNF formulas and the class of unate DNF formulas, both of which are known to be learnable in polynomial time with membership and equivalence queries. We prove that ²can be properly learned with a polynomial number of polynomial-size membership and equivalence queries, but can be properly learned in polynomial time with such queries if and only if P=NP. Thus the barrier to properly learning ²with membership and equivalence queries is computational rather than informational. Few results of this type are known. In our proofs, we use recent results of Hellersteinet al.(1997,J. Assoc. Comput. Mach.43(5), 840–862), characterizing the classes that are polynomial-query learnable, together with work of Bshouty on the monotone dimension of Boolean functions. We extend some of our results to ^kand pose open questions on learning DNF formulas of small monotone dimension. We also prove structural results for ^k. We construct, for any fixedk2, a class of functionsfthat cannot be represented by any formula in ^k, but which cannot be “easily” shown to have this property. More precisely, for any functionfonnvariables in the class, the value offon any polynomial-size set of points in its domain is not a witness thatfcannot be represented by a formula in ^k. Our construction is based on BCH codes.     

Concepts and realization of a high-performance data type architecture

Fifth generation computers are expected to capitalize on the dramatic progress of VLSI technology, in order to offer an improved performance/cost figure. An even more important requirement, however, is that they will support by architectural means the generation, execution, and maintenance of quality software, as a way out of the software crisis. One approach towards the design and implementation of quality software is programming with abstract data types, in connection with elaborate type consistency checking. The objection raised against the abstract data type based programming style is poor run time efficiency when such programs are executed on a conventional machine. In this paper adata type architecture is described that offers efficient and convenient mechanism for constructing arbitrary data structures and encapsulating them into abstract data types, thus avoiding the inefficiency penalty mentioned above. Through a process of hierarchical decomposition, user-defined abstract data types are mapped on representations given in terms of a basicstructured machine data type. This approach combines high performance with generality and completeness. The hardware structure of the data type architecture can be classified as a strongly coupled, asymmetric multicomputer system with hierarchical function distribution among the computers. The system includes a pipeline for numerical and nonnumerical operations, performed on the vector-structured basic machine data type in the SIMD mode of operation. Software reliability and data security is enhanced through elaborate run time consistency checking. The computer, which was designed and built at the Technical University of Berlin, has recently become operational. This paper outlines the operational principle, the mechanisms, and the hardware and software structure of this innovative, fifth generation computer architecture.This work was sponsored by the German Science Foundation under grant no. Gi 42/13.     

Recursivite et cones rationnels fermes par intersection

Resume Nous définissons les grammaires quasi-commutatives en modifiant légérement la definition des grammaires commutatives introduites par Crespi-Reghizzi et Mandrioli [5]. Nous obtenons, ainsi, une caractérisation grammaticale de , le plus petit c?ne rationnel clos par intersection et contenantD ₁′^*, le langage de semi-Dyck sur une lettre. Nous en déduisons que tout langage de (D ₁′*)est récursif. A l'aide d'une généralisation des ?Vector Addition Systems?, nous démontrons, ensuite, le même résultat pour les langages de , le plus petit c?ne rationnel clos par étoile et intersection, contenant le langage formé de tous les préfixes des mots deD ₁′.     

On the usefulness of bifaithful rational cones

Roughly, a faithful (resp. bifaithful) rational transduction is a non deterministic finite state mapping that does not decrease (resp. alter) the length of words by very much. We introduce the notion of stronglyf-saturated language:L is stronglyf-saturated if and only if for any languageL, from which we can obtainL by faithful rational transduction, for any languageL, image ofL by a faithful rational transduction, there exists a bifaithful rational transduction such thatL is the image ofL . We prove that no quasirational language and no language in the substitution closed rational cone generated by bounded languages is stronglyf-saturated. Conversely, we establish that a language such as , very low in the hierarchy of algebraic languages, is stronglyf-saturated thus is not a quasirational language. We also establish that any commutative quasi rational language over two letters is rational.     

MV-pairs and states

An MV-pair is a BG-pair (B; G) (where B is a Boolean algebra and G is a subgroup of the automorphism group of B) satisfying certain conditions. Recently, it was proved by Jenca that, given an MV-pair (B; G), the quotient where is an equivalence relation naturally associated with G, is an MV-algebra, and conversely, to every MV-algebra there corresponds an MV-pair. In this paper, we introduce a new definition of so called MV*-pair, and we show that is an effect algebra iff the first of the defining properties of the MV*-pair is satisfied, while the second property guarantees the MV-algebra structure of . We also study some relations between states on MV-algebras and the corresponding R-generated Boolean algebras. This work was supported by Science and Technology Assistance Agency under the contract no. LPP-0199-07 and no. APVV-0071-06, grant VEGA 2/6088/26 and Center of excellence SAS CEPI–Physics of Information–I/2/2005.     

PI k mass production and an optimal circuit for the Nečiporuk slice

Letf: {0,1} ⁿ {0,1} ^m be anm-output Boolean function inn variables.f is called ak-slice iff(x) equals the all-zero vector for allx with Hamming weight less thank andf(x) equals the all-one vector for allx with Hamming weight more thank. Wegener showed that PI _k -set circuits (set circuits over prime implicants of lengthk) are at the heart of any optimum Boolean circuit for ak-slicef. We prove that, in PI _k -set circuits, savings are possible for the mass production of anyFX, i.e., any collectionF ofm output-sets given any collectionX ofn input-sets, if their PI _k -set complexity satisfiesSC _m (FX)3n+2m. This PI _k mass production, which can be used in monotone circuits for slice functions, is then exploited in different ways to obtain a monotone circuit of complexity 3n+o(n) for the Neiporuk slice, thus disproving a conjecture by Wegener that this slice has monotone complexity (n ^3/2). Finally, the new circuit for the Neiporuk slice is proven to be asymptotically optimal, not only with respect to monotone complexity, but also with respect to combinational complexity.     

Doubler and linearizer: an approach toward a unified theory for molecular computing based on DNA complementarity

Two specific mappings called doubler f _d and linearizer are introduced to bridge between two kinds of languages. Specifically, f _d maps string languages into (double-stranded) molecular languages, while performs the opposite mapping. Using these mappings, we obtain new characterizations for the families of sticker languages and of Watson-Crick languages, which lead to not only a unified view of the two families of languages but also provide a helpful view on the computational capability of DNA complementarity. Furthermore, we introduce a special type of a projection f _pr which is composed of f _d and a projection in the usual sense. We show that any recursively enumerable language L can be expressed as f _pr (L _m ) for a minimal linear language L _m . This result can be strengthened to L = f _pr (L _s ), for a specific form of minimal linear language L _s , which provides a simple morphic characterization for the family of recursively enumerable languages. A preliminary version of this article appeared in Onodera and Yokomori (2006).     

The complexity of monotone boolean functions

We study the realization of monotone Boolean functions by networks. Our main result is a precise version of the following statement: the complexity of realizing a monotone Boolean function ofn arguments is less by the factor (2/n)^1/2, where is the circular ratio, than the complexity of realizing an arbitrary Boolean function ofn arguments. The proof combines known results concerning monotone Boolean functions with new methods relating the computing abilities of networks and machines.     

All‐in‐one implementation framework for binary heaps

Even a rough literature review reveals that there are many alternative ways of implementing a binary heap, the fundamental priority‐queue structure loved by us all. Which one of these alternatives is the best in practice? The opinions of crowd‐pullers and textbook authors are aligned: use an array. Of course, the correct answer is ‘it depends’. To get from opinions to facts, a framework—a set of class templates—was written that provides a variety of customization options so it could be used to realize a large part of the proposed variants. Also, some of the derived implementations were performance benchmarked. From this work, three conclusions can be drawn: (i) It is difficult to achieve space efficiency and speed at the same time. If n denotes the current number of values in the data structure, ? is a small positive real, ?  < 1, and denotes the size of the values of type in bytes, space efficiency means bytes of space, and speed means O (lgn ) worst‐case time per push and pop . (ii) If an array‐based solution is sufficient, Williams' original program from 1964 is still to this day hard to beat. (iii) Sometimes a linked structure and clever programming is a viable option. If the binary‐heap variant you need is not available at the software library you are using, reading this essay might save you some headaches. Copyright © 2016 John Wiley & Sons, Ltd.     

Knowledge Representation

Abstract

In this semi-expository note, we first recall that every boolean function f of n variables is determined uniquely by a certain subset S of the nodes of the hypercube Q". We then propose the subgraph of Q_n induced by S as a realization of f, and call it the graph of a boolean function. We observe that boolean functions of the same type always have the same graph, but the converse does not hold. We conclude with the open question which suggests itself from a confrontation of the disjunctive and conjunctive normal forms of a boolean function.