Learning Read-Once Formulas over Fields and Extended Bases
Abstract
A formula is read-once if each variable in it occurs at most once. Angluin, Hellerstein, and Karpinski [AHK89] have shown that read-once formulas over the basis (AND, OR, NOT) are identifiable in polynomial time with membership and equivalence queries. We extend this result for boolean formulas to a larger basis including arbitrary threshold functions (generalizing AND and OR), NOT, parity, and functions computing congruence to a residue in some modulus up to a constant k. Note these functions are all symmetric, but are not all unate. We further examine arithmetic read-once formulas over multiplication and addition on an arbitrary field. We show these are identifiable in time polynomial in the number of variables using equivalence queries and the natural extension of membership queries to a non-boolean domain.
Cite
Text
Hancock and Hellerstein. "Learning Read-Once Formulas over Fields and Extended Bases." Annual Conference on Computational Learning Theory, 1991. doi:10.1016/B978-1-55860-213-7.50033-XMarkdown
[Hancock and Hellerstein. "Learning Read-Once Formulas over Fields and Extended Bases." Annual Conference on Computational Learning Theory, 1991.](https://mlanthology.org/colt/1991/hancock1991colt-learning-a/) doi:10.1016/B978-1-55860-213-7.50033-XBibTeX
@inproceedings{hancock1991colt-learning-a,
title = {{Learning Read-Once Formulas over Fields and Extended Bases}},
author = {Hancock, Thomas R. and Hellerstein, Lisa},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1991},
pages = {326-336},
doi = {10.1016/B978-1-55860-213-7.50033-X},
url = {https://mlanthology.org/colt/1991/hancock1991colt-learning-a/}
}