Characterizing Arithmetic Read-Once Formulae

An arithmetic read-once formula (ROF for short) is a formula (i.e. a tree of computation) in which the operations are $+$ and $x$ such that every input variable labels at most one leaf. Those formulae correspond to the smallest possible functions that depend on all of their variables. In this work we give a simple characterization of the read-once formulae. Other than being interesting in its own right, our characterization gives rise to a property testing algorithm for such formulae. To the best of our knowledge, prior to our work no characterization and/or property testing algorithm was known for this kind of formulae. We also show that no such characterization is possible for the ROF's Boolean counterpart.