4 citations · 5 across the 3 of their papers we have counts for
Showing 2005Show all
2 papers · 1 filter
math.PR2005
A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas
Cristopher Moore, Gabriel Istrate, Demetrios Demopoulos +1
We compute the probability of satisfiability of a class of random Horn-SAT formulae, motivated by a connection with the nonemptiness problem of finite tree automata. In particular,…
cs.DM2005★ 1 cited
Coarse and Sharp Thresholds of Boolean Constraint Satisfaction Problems
Gabriel Istrate
We study threshold properties of random constraint satisfaction problems under a probabilistic model due to Molloy. We give a sufficient condition for the existence of a sharp thre…