Davis-Putnam Style Rules for Deciding Property S

• Autorzy: Cowen R. , Kolany A.
• Języki publikacji: EN

Abstrakty

EN

Two set systems E, F on an underlying set V will be said to have Property S if there exists a subset [sigma] of V, such that [formula] (see [8], [9]). We give rules for deciding Property S, which generalizes the very successful Davis-Putnam rules for deciding satisfiability in propositional logic.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 79, nr 1-2
• Strony: 5--15
• Opis fizyczny: bibliogr. 12 poz.

Twórcy

autor

Cowen R.

autor

Kolany A.

• Theoretical Computer Science Department, Gronostajowa 3, 30-072 Kraków, Poland

Bibliografia

• [1] Cowen, R., Two hypergraph theorems equivalent to BPI, Notre Dame J. Formal Logic 31(1990), 232-240.
• [2] Cowen, R., Some connections between set theory and computer science, Lecture Notes in Computer Science 713(1993), 14-22.
• [3] Cowen, R., Hechler, S., G-free colorability and the Boolean prime ideal theorem, Scientiae Mathematicae Japonicae, 59(2004), no.2, 257-263
• [4] Cowen, R., Property S, Reports on Math. Logic, 35(2001), 61-74.
• [5] Davis, M., Logemann, G. and Loveland, D., A machine program for theorem proving, Communications of the ACM, 5(1962), 394-397.
• [6] Davis, M. and Putnam, H., A computing procedure for quantification theory, J. of the ACM 7(1960), 201-215.
• [7] Erdös, Peter., Some generalizations of Property B and the splitting property, Ann. of Combinatorics , 3(1999), 53-59.
• [8] Kolany, A., Satisfiability on hypergraphs, Studia Logica, 52(1993), 393-404.
• [9] Schrijver, A., The dependence of some some logical axioms on disjoint transversals and linked systems, Colloq. Math., 39(1978), 191-199.
• [10] Stein, S. K., B-sets and planar maps, Pacific J. Math. 37(1971), 217-224.
• [11] West, D., Introduction to Graph Theory, Prentice-Hall, Upper Saddle River, NJ, 1996.
• [12] Woodall, D. R., Property B and the four-colour problem, in Combinatorics, ed. Welsh, D.J. and Woodall, D.R., IMA, 1972.