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 old.ad-astra.ro

Facebook

The Phase Transition in Random Horn satisfiability and its algorithmic implications

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

Autori: Gabriel Istrate

Editorial: Random Structures and Algorithms, vol. 20 no. 4, p.483-506, 2002.

Rezumat:

I determine the threshold behaviour of random Horn satisfiability via a probabilistic analysis of positive unit resolution, also determining as a byproduct the average-case complexity of this algorithm.

A preliminary version can be read from

http://xxx.lanl.gov/abs/cs.DS/9912001

Cuvinte cheie: satisfiability, positive unit resolution, threshold properties

URL: http://www3.interscience.wiley.com/cgi-bin/abstract/93516258/ABSTRACT