Equivalence classes of random Boolean trees and application to the Catalan satisfiability problem

DOI10.1007/978-3-642-54423-1_41MaRDI QIDQ5405065zbMATH OpenOpenAlexFDO

Authors Antoine Genitrini, Cécile Mailler

Publication date 31 March 2014

Published in LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-54423-1_41

zbMATH Keywords

Boolean functionprobability distributionsatisfiabilityanalytic combinatoricsBoolean formulasrandom Boolean expressions

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorics in computer science (68R05) Boolean functions (06E30)

Recommendations

• Generalised and quotient models for random and/or~trees and application to satisfiability
• And/or trees: A local limit point of view
• And/Or Trees Revisited
• No Shannon effect induced by and/or trees
• Some typical properties of large AND/OR Boolean formulas

Cited in

(2)

• Generalised and quotient models for random and/or~trees and application to satisfiability
• No Shannon effect induced by and/or trees

This page was built for publication: Equivalence classes of random Boolean trees and application to the Catalan satisfiability problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405065)