Name
Title | ||
|---|---|---|
A continuous–discontinuous second-order transition in the satisfiability of random Horn-SAT formulas |
Abstract | ||
|---|---|---|
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, when the maximum clause length is three, this model displays a curve in its parameter space, along which the probability of satisfiability is discontinuous, ending in a second-order phase transition where it is continuous but its derivative diverges. This is the first case in which a phase transition of this type has been rigorously established for a random constraint satisfaction problem. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007 |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1002/rsa.v31:2 | APPROX-RANDOM |
Keywords | Field | DocType |
statistical physics,satisfiability,second order,phase transitions,differential equations | Discrete mathematics,Random element,Constraint satisfaction,Discontinuity (linguistics),Satisfiability,Constraint satisfaction problem,Finite-state machine,Parameter space,Tree automaton,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 2 | 1042-9832 |
Citations | PageRank | References |
2 | 0.42 | 21 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cristopher Moore | 1 | 1765 | 160.55 |
| Gabriel Istrate | 2 | 99 | 24.96 |
| Demetrios Demopoulos | 3 | 2 | 0.42 |
| Moshe Y. Vardi | 4 | 13413 | 2267.07 |