And/Or trees revisited Export

@inproceedings{citeulike:6008749, abstract = {We consider boolean functions over n variables. Any such function can be represented (and computed) by a complete binary tree with and or or in the internal nodes and a literal in the external nodes, and many different trees can represent the same function, so that a fundamental question is related to the so-called complexity of a boolean function: L(f) := minimal size of a tree computing f .}, author = {Chauvin, B. and Flajolet, P. and Gardy, D. and Gittenberger, B.}, booktitle = {in « Combinatorics, Probability and Computing », To appear}, citeulike-article-id = {6008749}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.7520}, keywords = {combinatorics}, posted-at = {2009-10-26 09:31:22}, priority = {2}, title = {And/Or trees revisited}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.7520}, volume = {27} }

TY - CONF ID - citeulike:6008749 L3 - citeulike-article-id:6008749 N2 - We consider boolean functions over n variables. Any such function can be represented (and computed) by a complete binary tree with and or or in the internal nodes and a literal in the external nodes, and many different trees can represent the same function, so that a fundamental question is related to the so-called complexity of a boolean function: L(f) := minimal size of a tree computing f . TI - And/Or trees revisited VL - 27 T2 - in « Combinatorics, Probability and Computing », To appear KW - combinatorics AU - Chauvin, B AU - Flajolet, P AU - Gardy, D AU - Gittenberger, B UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.7520 ER -