Can I read A continuous–discontinuous second-order transition in the satisfiability of random Horn-SAT formulas on EtoBox?

A continuous–discontinuous second-order transition in the satisfiability of random Horn-SAT formulas by Cristopher Moore; Gabriel Istrate; Demetrios Demopoulos; Moshe Y. Vardi is a Mathematics article available to read on EtoBox.

What is A continuous–discontinuous second-order transition in the satisfiability of random Horn-SAT formulas about?

## 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

Who reads A continuous–discontinuous second-order transition in the satisfiability of random Horn-SAT formulas?

Author

Cristopher Moore; Gabriel Istrate; Demetrios Demopoulos; Moshe Y. Vardi

Publisher

John Wiley and Sons; Wiley (John Wiley & Sons); John Wiley & Sons Inc.; Wiley (ISSN 1042-9832)

Published

2007

Language

EN

Field

Mathematics (Physical Sciences)