Probabilities of Boolean Functions Given by Random Implicational Formulas

被引：0

作者：

Genitrini, Antoine ^{[1
,6
]}

Gittenberger, Bernhard ^{[2
]}

Kraus, Veronika ^{[3
]}

Mailler, Cecile ^{[4
,5
]}

机构：

[1] CNRS UMR 7606, Lab Informat Paris 6, F-75252 Paris 05, France

[2] Vienna Univ Technol, Inst Discrete Math & Geometry, A-1040 Vienna, Austria

[3] Eduard Wallnoefer Zentrum 1, Inst Bioinformat & Translat Res, UMIT, A-6060 Hall In Tirol, Austria

[4] Univ Versailles St Quentin, F-78035 Versailles, France

[5] CNRS UMR 8100, Lab Math Versailles, F-78035 Versailles, France

[6] Univ Paris 06, F-75252 Paris 05, France

来源：

ELECTRONIC JOURNAL OF COMBINATORICS | 2012年 / 19卷 / 02期

关键词：

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We study the asymptotic relation between the probability and the complexity of Boolean functions in the implicational fragment which are generated by large random Boolean expressions involving variables and implication, as the number of variables tends to infinity. In contrast to models studied in the literature so far, we consider two expressions to be equal if they differ only in the order of the premises. A precise asymptotic formula is derived for functions of low complexity. Furthermore, we show that this model does not exhibit the Shannon effect.

引用

页数：20

共 20 条

[1]

[Anonymous], ASS COMMUTATIV UNPUB

[2]

[Anonymous], 2009, RANDOM TREES

[3] And/or trees revisited [J].

Chauvin, B ;

Flajolet, P ;

Gardy, D ;

Gittenberger, B .

COMBINATORICS PROBABILITY & COMPUTING, 2004, 13 (4-5) :475-497

[4] LINEAR-TIME ALGORITHMS FOR TESTING THE SATISFIABILITY OF PROPOSITIONAL HORN FORMULAE. [J].

Dowling, William F. ;

Gallier, Jean H. .

Journal of Logic Programming, 1984, 1 (03) :267-284

[5] SINGULARITY ANALYSIS OF GENERATING-FUNCTIONS [J].

FLAJOLET, P ;

ODLYZKO, A .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1990, 3 (02) :216-240

[6]

Flajolet P., 2009, ANAL COMBINATORICS

[7]

Fournier H, 2007, LECT NOTES COMPUT SC, V4646, P177

[8] The fraction of large random trees representing a given Boolean function in implicational logic [J].

Fournier, Herve ;

Gardy, Daniele ;

Genitrini, Antoine ;

Gittenberger, Bernhard .

RANDOM STRUCTURES & ALGORITHMS, 2012, 40 (03) :317-349

[9]

Gardy D., 2006, C COMP LOG APPL DMTC, P1

[10]

Genitrini A., 2012, NEW NOTION IN PRESS

← 1 2 →