AFP Algorithm and a Canonical Normal Form for Horn Formulas

Preprint English OPEN
Majdoddin, Ruhollah (2014)
  • Subject: 68Q32, 68T27 | Computer Science - Learning
    acm: TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
    arxiv: Quantitative Biology::Quantitative Methods

AFP Algorithm is a learning algorithm for Horn formulas. We show that it does not improve the complexity of AFP Algorithm, if after each negative counterexample more that just one refinements are performed. Moreover, a canonical normal form for Horn formulas is presented, and it is proved that the output formula of AFP Algorithm is in this normal form.
  • References (3)

    Marta Arias and José L Balcázar. Construction and learnability of canonical horn formulas. Machine Learning, 85(3):273-297, 2011.

    [AFP92] Dana Angluin, Michael Frazier, and Leonard Pitt. Learning conjunctions of horn clauses. Machine Learning, 9(2-3):147-164, 1992.

    [Bal05] Jose L Balcázar. Query learning of horn formulas revisited. Giulia Battilotti, Paola Zizzi Logical Characterizations of PK and NPK over an Arbitrary Structure K. 30 Olivier Bournez, Felipe Cucker, Paulin Jacobé de Naurois, Jean-Yves Marion Fuzzy Interval-valued Processes Algebra............................. 44, page 1, 2005.

  • Metrics
    No metrics available
Share - Bookmark