Journal of Integer Sequences, Vol. 10 (2007), Article 07.3.4

Mahler's Expansion and Boolean Functions


Jean-Francis Michon
LITIS - Université de Rouen
Avenue de l'Université - BP 8
76801 Saint-Étienne-du-Rouvray Cedex
France

Pierre Valarcher
LACL - Université Paris 12 Val de Marne
Faculté des Sciences
61, avenue du Général de Gaulle
94010 Créteil Cedex
France

Jean-Baptiste Yunès
LIAFA - Universitée Denis Diderot Paris 7
175, rue du chevaleret
75013 Paris
France

Abstract:

The substitution of X by X2 in binomial polynomials generates sequences of integers by Mahler's expansion. We give some properties of these integers and a combinatorial interpretation with covers by projection. We also give applications to the classification of boolean functions. This sequence arose from our previous research on classification and complexity of Binary Decision Diagrams (BDD) associated with boolean functions.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A100344.)

Received July 18 2005; revised version received March 28 2007. Published in Journal of Integer Sequences March 28 2007.

Return to Journal of Integer Sequences home page