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

Simple item page
dc.creatorMoore, Cristopher
dc.creatorIstrate, Gabriel
dc.creatorDemopoulos, Demetrios
dc.creatorVardi, Moshe Y.
dc.date2005-05-02
dc.date.accessioned2026-07-07T05:19:35Z
dc.date.available2026-07-07T05:19:35Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/math/0505032
dc.identifierhttp://arxiv.org/abs/math/0505032
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/75069
dc.subjectProbability
dc.subjectDisordered Systems and Neural Networks
dc.subjectCombinatorics
dc.titleA Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas
dc.typetext

Files

Collections

arXiv