Minimal Samples of Positive Examples Identifying k-CNF Boolean Functions
| Autor: | Andrew T. Ogielski |
|---|---|
| Rok vydání: | 1994 |
| Předmět: |
Class (set theory)
Trace (linear algebra) Dimension (graph theory) Characterization (mathematics) Computer Science Applications Theoretical Computer Science Combinatorics Complexity index Computational Theory and Mathematics Encoding (memory) Boolean expression Boolean function Information Systems Mathematics |
| Zdroj: | Information and Computation. 113:220-229 |
| ISSN: | 0890-5401 |
| Popis: | A consistent learning algorithm can reconstruct any Boolean function belonging to a given class from a sufficiently large number of examples; therefore such samples may be interpreted as an encoding of functions. We investigate the complexity of encoding by examples for functions representable by k-CNF logic formulas. Lower and upper bounds for the sampling complexity of k-CNF functions are expressed in terms of the Vapnik-Chervonenkis dimension (trace number) and related combinatorial indices. Combinatorial characterization of k-CNF functions which cannot be identified from a sample smaller than the complete list of truth assignments is also investigated. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|