{"entities":{"Q4366603":{"pageid":6396202,"ns":120,"title":"Item:Q4366603","lastrevid":108301073,"modified":"2026-11-05T20:11:17Z","type":"item","id":"Q4366603","labels":{"en":{"language":"en","value":"Renaming a set of non-Horn clauses"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1090102"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4366603$0A59C7DF-AE24-4A3C-AA11-BFBDCB43D869","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c123955c0f8f2be504c831d8162f599405fadff9","datavalue":{"value":"0896.03025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4366603$A0205D05-6FB7-4C8F-9739-C50C6ECAA91E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0b6721df2a0037b15fd86f65472c88ec7ecc0ce5","datavalue":{"value":{"entity-type":"item","numeric-id":582115,"id":"Q582115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4366603$31D384E6-97D0-46C1-8533-27D823FDA984","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"927a23c11c9d89dc7ff2e86628c528209743bfde","datavalue":{"value":{"entity-type":"item","numeric-id":7348193,"id":"Q7348193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4366603$CB4D2F23-1393-43BA-9E95-CF7A4091DDA8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"999f03c13835e1923a8e900c7129f49e6e75be1c","datavalue":{"value":{"time":"+1998-09-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4366603$EE00C973-69E1-4021-9CB8-60F889F869EF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d53cd5ab715340bbfc507bf5b4aac1b907f4465d","datavalue":{"value":"03B70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4366603$21077F43-8C26-4415-9277-2E81470CE0D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b492f281b8f52c724f2bc547e7e570cccf4bd5e0","datavalue":{"value":"68N17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4366603$CFA8234C-816B-4676-95C5-192C372F9ED3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"10eaeaf8bbf8231bbfc812aab8956e260b5a9f12","datavalue":{"value":"03B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4366603$D98A7286-6718-4BAA-8FEF-D1DD6350CBBB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ab9140b4263804e7361a9583dfe19a8cf1dd7b11","datavalue":{"value":"1090102","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4366603$33BCB8AC-A6B9-4020-9EBF-E4884CC85A1C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e431190495251d75e7d7f973ca704f4139885eb","datavalue":{"value":"Horn clauses","type":"string"},"datatype":"string"},"type":"statement","id":"Q4366603$CA8883DC-E26F-41A4-B3B8-A1C6529E63D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88ac52ba5fbfea503a5169a1bf75445d6498e920","datavalue":{"value":"renaming","type":"string"},"datatype":"string"},"type":"statement","id":"Q4366603$F7D3E480-A774-4FF8-8EB6-BD5AB6E64909","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b5f5d758b6815d51bba8673e44010b22c717da2","datavalue":{"value":"measure for being non-Horn","type":"string"},"datatype":"string"},"type":"statement","id":"Q4366603$9650330B-F606-41A9-8F1B-32F33E69E8C2","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4366603$0CABD720-4287-4F26-912A-88D435333D77","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"202e5576435046a341bee1b62c53361a3c9b896d","datavalue":{"value":{"entity-type":"item","numeric-id":1587332,"id":"Q1587332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5c65739d1c38929d7a4558523c632ea467ede6a","datavalue":{"value":{"amount":"+0.885822057723999","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4366603$BC62E241-BE98-4E5F-A3FC-CC43D219838B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c334dc054d23aefcd23e9dddd5243131b09071a4","datavalue":{"value":{"entity-type":"item","numeric-id":5184426,"id":"Q5184426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cb844b6b06bd77fa2c3635d711fd5c35839f94b","datavalue":{"value":{"amount":"+0.8780532479286194","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4366603$6224A3A9-67A2-44B9-B96C-ACB8D5081788","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e401010a16cae18ee5b263f9625fbd07cf6ee2f","datavalue":{"value":{"entity-type":"item","numeric-id":1120278,"id":"Q1120278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50165bb0685138f002936639725f4e37ddb163b8","datavalue":{"value":{"amount":"+0.8318371772766113","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4366603$8764BE7B-DEC3-4E29-9A55-62B61719A384","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8dde5986a2ae1981a2a4b1372c473e49c41eb9ae","datavalue":{"value":{"entity-type":"item","numeric-id":1318709,"id":"Q1318709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36d4c2538cd26b28e1c25daaa998609946ce06df","datavalue":{"value":{"amount":"+0.7981866598129272","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4366603$8B0788BE-3492-4E09-B0CF-9F35BD410AC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5b277717c8a2c42e9b033effc04c094004c0e77","datavalue":{"value":{"entity-type":"item","numeric-id":6488560,"id":"Q6488560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e1cf06c86c36daf19e4a32a749c082f7f7b8b17","datavalue":{"value":{"amount":"+0.7882370948791504","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4366603$C27A0403-CB06-4F44-A1A1-C354EA56F564","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cc9ea75e2501763186fb1b733a91efb36c268ee6","datavalue":{"value":{"text":"Renaming a set of non-Horn clauses","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4366603$D2C84D67-C36F-4583-BB2B-87A6C117DD0F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b4b31a53fe797d16f4c06fc78d7732fd9d732504","datavalue":{"value":"10.1007/3-540-63614-5_58","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4366603$16EDD0FF-F2DF-42C4-92CD-0A7995D3C8E3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"313e7aa5ec1014e45436b08bac9c8444511932e1","datavalue":{"value":"A clause is a formula \\(H_1\\vee \\cdots \\vee H_k\\vee \\neg L_1\\vee \\neg L_2\\cdots \\neg L_n.\\) A clause is a Horn clause if \\(k\\leq 1\\). The case \\(k=1\\) is called a {program clause}: \\(H\\leftarrow L_1\\wedge \\cdots \\wedge L_n\\); \\(n=0\\) is the same as \\(H\\leftarrow true\\) and it is called a {fact}; \\(k=0 \\) is the same as \\(false\\leftarrow L_1\\wedge \\cdots \\wedge L_n \\) and it is called a {goal}. Here the \\(L_i\\) and \\(H_j\\) stand for atomic formulas. A standard {Horn clause} program \\(\\pi\\) is a finite set consisting of program clauses and of facts. Given a program \\(\\pi\\) and a goal \\(\\gamma\\), the objective is to refute \\(\\gamma\\), i.e., to find the instances where \\(L_1\\wedge\\cdots\\wedge L_n\\) is true. The resolution method is the most popular proof system for Horn clause logic and its computer implementation in form of Prolog has found practical applications as a high level programming language for database management problems. To express a certain situation within the framework of Horn clause logic may require some judicious choice of the basic predicates. But certainly not for the classical school example: All humans are mortal and Socrates is human; thus Socrates is mortal. On the other hand, with the predicate \\(divine(X)\\) for not being human, the Horn clause \\(mortal(X)\\vee \\neg human(X) \\) becomes \\(mortal(X)\\vee divine(X) \\) and the fact \\(human(socrates)\\) is now the negated predicate \\(\\neg divine(socrates)\\). While the semantics is still the same, resolution for Horn clause logic no longer applies. We have a set \\(\\{ m(X)\\vee d(X),\\neg d(s)\\} \\;\\) of two clauses. A formal change from the predicate \\(d\\) to its opposite then yields \\(\\{ m(X)\\vee \\neg d(X),d(s)\\}\\) which is now a set of two Horn clauses. Given a set of clauses, the formal process of replacing a selected set of predicates by their complements is called {renaming}. For mechanical deductions it is not necessary to actually rename the predicates. It is known (Lewis (1978); Mannila, Mehlhorn (1985)) that if there is a renaming to a set of Horn clauses, then it can be done in polynomial time. For a clause, the authors define a measure for being non-Horn by the number of the positive literals minus one. Given a finite set of clauses, one might be interested in finding a renaming for which the measure of being non-Horn is minimal. The authors show that this problem is NP-complete. The authors provide some experimental evidence that a higher measure for being non-Horn increases the number of steps for proof procedures that are based on resolution. For the entire collection see [Zbl 0951.00051].","type":"string"},"datatype":"string"},"type":"statement","id":"Q4366603$8982B408-9700-4D6D-9C91-D8BA6271789B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4366603$D1141865-5147-45E5-AB7D-DCCDDA4F8D94","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Renaming a set of non-Horn clauses (scientific article; zbMATH DE number 1090102)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Renaming_a_set_of_non-Horn_clauses_(scientific_article;_zbMATH_DE_number_1090102)"}}}}}