Inscriere cercetatori

Site nou !

Daca nu va puteti recupera parola (sau aveti alte probleme), scrieti-ne la pagina de contact. Situl vechi se gaseste la adresa


A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas

Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în revistã ştiinţificã

Autori: Cristopher Moore, Gabriel Istrate, Demetrios Demopoulos and Moshe Y. Vardi

Editorial: Random Structures and Algorithms, 31(2), p.173-185, 2007.


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 3, 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 becomes continuous. This is the first case in which a phase transition of this type has been rigorously established for a random constraint satisfaction problem.

A preliminary version can be read from
and has appeared in the Proceedings of the Eight International Workshop on Randomization and Computation (RANDOM’05)

Cuvinte cheie: Horn satisfiability