Abstrakt. En read-once formel är en Boolesk formel där varje variabel inträffar, som mest, en gång. Sådana formler kallas också p-formler eller booleska träd. Detta papper behandlar problemet med att exakt identifiera en okänd läs-en gång formel med hjälp av specifika typer av frågor. De viktigaste resultaten är en polynom-tid algoritm för exakt identifiering av monotone läs-ence formler med endast medlemskap frågor, och en polynom-tid algoritm för exakt identifiering av genenml läs-en gång formler med hjälp av likvärdighet och medlemskap frågor (ett protokoll baserat på begreppet en minimalt tillräcklig lärare [I]). Författarnas resultat förbättrar Valiants tidigare resultat för läs-och skrivformler [26]. Det visas också, att ingen polynom-tid algoritm med bara medlemskap frågor eller bara likvärdighet frågor kan exakt identifiera alla läs-en gång formler.
Både qhorn-1 och read-once Boolean formler REF tillåter variabler att uppstå som mest en gång.
Learning read-once formulas with queries
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}