When won't membership queries help?
From MaRDI portal
Publication:1892226
DOI10.1006/jcss.1995.1026zbMath0827.68039OpenAlexW4210406996MaRDI QIDQ1892226
Dana Angluin, Michael Kharitonov
Publication date: 13 December 1995
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1995.1026
Learning and adaptive systems in artificial intelligence (68T05) Data encryption (aspects in computer science) (68P25)
Related Items (42)
Learning elementary formal systems with queries. ⋮ Learning of Structurally Unambiguous Probabilistic Grammars ⋮ Prefix grammars: An alternative characterization of the regular languages ⋮ The query complexity of learning DFA ⋮ Learning union of integer hypercubes with queries (with applications to monadic decomposition) ⋮ On learning width two branching programs ⋮ A framework for polynomial-time query learnability ⋮ Structural analysis of polynomial-time query learnability ⋮ An efficient membership-query algorithm for learning DNF with respect to the uniform distribution ⋮ On the complexity of small description and related topics ⋮ Recent advances of grammatical inference ⋮ Learning orthogonal F-Horn formulas ⋮ Grammatical inference: An old and new paradigm ⋮ Construction and learnability of canonical Horn formulas ⋮ A Myhill-Nerode theorem for finite state matrix automata and finite matrix languages ⋮ Distributional Learning of Context-Free and Multiple Context-Free Grammars ⋮ Learning two-tape automata from queries and counterexamples ⋮ Active learning of nondeterministic finite state machines ⋮ Learnability of quantified formulas. ⋮ Classic learning ⋮ On the limits of proper learnability of subclasses of DNF formulas ⋮ Learning definite Horn formulas from closure queries ⋮ Learning orthogonal F-Horn formulas ⋮ Incremental learning of context free grammars based on bottom-up parsing and search ⋮ Learning expressions and programs over monoids ⋮ Optimally learning social networks with activations and suppressions ⋮ Query learning of bounded-width OBDDs ⋮ Exact learning of DNF formulas using DNF hypotheses ⋮ Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions ⋮ Weighted automata are compact and actively learnable ⋮ Learning large-alphabet and analog circuits with value injection queries ⋮ New cryptographic hardness for learning intersections of halfspaces over Boolean cubes with membership queries ⋮ Unnamed Item ⋮ Hardness of approximate two-level logic minimization and PAC learning with membership queries ⋮ Learning a circuit by injecting values ⋮ Canonical Horn Representations and Query Learning ⋮ Proper learning of \(k\)-term DNF formulas from satisfying assignments ⋮ Synthesizers and their application to the parallel construction of pseudo-random functions ⋮ Explaining AI decisions using efficient methods for learning sparse Boolean formulae ⋮ Even linear simple matrix languages: formal language properties and grammatical inference. ⋮ Theory revision with queries: Horn, read-once, and parity formulas ⋮ The complexity of learning concept classes with polynomial general dimension
This page was built for publication: When won't membership queries help?
