Property S

• Autorzy: Cowen R.
• Języki publikacji: EN

Abstrakty

EN

A set-theoretic property called Property S is introduced as a generalization of the well-known Property B. Property S is named for Schrijver who first used it in a paper [13] in connection with the Boolean prime ideal theorem. It was independently introduced by Kolany [10] to give a uniform treatment for a variety of satisfiability problems using an abstract resolution method to determine satisfiability. We further investigate Property S and resolution.

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Reports on Mathematical Logic
• Rocznik: 2001
• Tom: No. 35
• Strony: 61--74

Twórcy

autor

Cowen R.

• Mathematics Department Queens College, CUNY Flushing, NY 11367, USA

Bibliografia

• [1] R. Cowen, Hypergraph satisfiability, Reports on Math. Logic, 24 (1991), 113–118.
• [2] R. Cowen, Some connections between set theory and computer science, in Lecture Notes in Computer Science no. 713, ed. G. Gottlob, A. Leitsch, D. Mundici, SpringerVerlag, Berlin, 1993.
• [3] R. Cowen, Combinatorial analytic tableaux, Reports on Math. Logic, 27 (1993), 29–39.
• [4] M. Davis and H. Putnam, A computing procedure for quantification theory, Journal of the ACM, 7 (1996): 201–215.
• [5] P. Erdös, On a combinatorial problem, Nord. Mat. Tid., 11 (1963), 5–10.
• [6] P. Erdös, On a combinatorial problem II, Acta Math. Acad. Sci. Hungar., 15 (1964), 445–447.
• [7] P. Erdös, On a combinatorial problem III, Canad. Math. Bull., 12 (1969), 413–416.
• [8] P. Erdös and A. Hajnal, On a property of families of sets, Acta Math. Acad. Sci. Hungar., 12 (1961), 87–123.
• [9] M. Garey and D. Johnson, Computers and Intractibility, Freeman, San Fransisco, 1979.
• [10] A. Kolany, Satisfiability on hypergraphs, Studia Logica, 52 (1993), 393–404.
• [11] E.W. Miller, On a property of families of sets, Comptes Rendus Varsovic, 30 (1937), 31–38.
• [12] D. Pretolani, Efficiency and stability of hypergraph SAT algorithms, in Cliques, Coloring, and Satisfiability, ed. D.S. Johnson and M.A. Trick, American Mathematical Society, 1996.
• [13] A. Schrijver, The dependence of some some logical axioms on disjoint transversals and linked systems, Colloq. Math., 39 (1978), 191–199.
• [14] R. Smullyan, First-Order Logic, Springer-Verlag, New York, 1968.
• [15] S.K. Stein, B-sets and planar maps, Pacific J. Math. 37 (1971), 217–224.
• [16] D.B. West, Introduction to Graph Theory, Prentice-Hall, Upper Saddle River, NJ, 1996.
• [17] D.R. Woodall, Property B and the four-colour problem, in Combinatorics, ed. D.J. Welsh and D.R. Woodall, IMA, 1972.