Inscriere cercetatori

Daca aveti cont Ad Astra si de Facebook, intrati pe pagina de profil pentru a da dreptul sa va logati pe site doar cu acest buton.

Site nou !

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

Facebook

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.

Rezumat:

Want create site? Find Free WordPress Themes and plugins.

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)

Did you find apk for android? You can find new Free Android Games and apps.

Cuvinte cheie: Horn satisfiability

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