Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Publications
Theses and dissertations
Ad Astra association
 
Press releases
News
Events
Funding opportunities
 
Login
Registration
 
>> Românã
 
   
 

Cristopher Moore, Gabriel Istrate, Demetrios Demopoulos and Moshe Y. Vardi. A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas. Random Structures and Algorithms, 31(2), pp. 173-185, 2007.

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 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
http://xxx.lanl.gov/abs/math.PR/0505032
and has appeared in the Proceedings of the Eight International Workshop on Randomization and Computation (RANDOM'05)

Keywords: Horn satisfiability

URL: http://dx.doi.org/10.1002/rsa.20176

Posted by Gabriel Istrate

Back

   
© Ad Astra 2001-2013