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

DOI10.1007/978-3-642-54423-1_41zbMATH Open1351.68191OpenAlexW2150973624MaRDI QIDQ5405065FDOQ5405065

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

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

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)

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)