Learning read-once formulas with queries
From MaRDI portal
Publication:4033838
DOI10.1145/138027.138061zbMath0764.68139OpenAlexW2071210909MaRDI QIDQ4033838
Dana Angluin, Marek Karpinski, Lisa Hellerstein
Publication date: 16 May 1993
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/138027.138061
interpolationinductionconcept learningmembership queriesequivalence queriesread-once formulaspolynomial-time learningexact identification\(\mu\)-formulas
Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)
Related Items
Learning with queries inside the class of unate \(k\)-quasi-Horn formulas, An algorithm to learn read-once threshold formulas, and transformations between learning models, More efficient PAC-learning of DNF with membership queries under the uniform distribution, Diagnosis of three types of constant faults in read-once contact networks over finite bases, Efficient parallel recognition algorithms of cographs and distance hereditary graphs, Exact learning from an honest teacher that answers membership queries, Simple learning algorithms using divide and conquer, Learning fallible deterministic finite automata, The forbidden projections of unate functions, Exact learning of linear combinations of monotone terms from function value queries, On the Readability of Monotone Boolean Formulae, Using relevance queries for identification of read-once functions, Conjunctions of unate DNF formulas: Learning and structure, Selection of relevant features and examples in machine learning, Independence and port oracles for matroids, with an application to computational learning theory, Isomorphism testing of read-once functions and polynomials, Learning counting functions with queries, Learning from examples with unspecified attribute values., Unnamed Item, Exact learning of subclasses of CDNF formulas with membership queries, Minimum self-dual decompositions of positive dual-minor Boolean functions, On the readability of monotone Boolean formulae, Read-once polynomial identity testing, An improvement on the complexity of factoring read-once Boolean functions, Learning attribute-efficiently with corrupt oracles, Learning Read-Constant Polynomials of Constant Degree Modulo Composites, On the limits of proper learnability of subclasses of DNF formulas, Randomized vs. deterministic decision tree complexity for read-once Boolean functions, Learning read-constant polynomials of constant degree modulo composites, Learning read once functions using subcube parity queries, Learning languages from positive data and a finite number of queries, Monotone term decision lists, Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees, Computer science and decision theory, Query learning of bounded-width OBDDs, The complexity of exact learning of acyclic conditional preference networks from swap examples, Critical properties and complexity measures of read-once Boolean functions, Learning large-alphabet and analog circuits with value injection queries, The learnability of unions of two rectangles in the two-dimensional discretized space, Locating Errors in Faulty Formulas, Learning a circuit by injecting values, A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications, Attribute-efficient learning in query and mistake-bound models, Characterizing Arithmetic Read-Once Formulae, Structural results about exact learning with unspecified attribute values, Optimal ordered binary decision diagrams for read-once formulas, DERANDOMIZED LEARNING OF BOOLEAN FUNCTIONS OVER FINITE ABELIAN GROUPS, Diagnosis of constant faults in read-once contact networks over finite bases, The query complexity of finding local minima in the lattice, Read-Once Functions Revisited and the Readability Number of a Boolean Function, Theory revision with queries: Horn, read-once, and parity formulas, The complexity of learning concept classes with polynomial general dimension
