{"entities":{"Q650893":{"pageid":652742,"ns":120,"title":"Item:Q650893","lastrevid":63320001,"modified":"2026-04-11T12:04:46Z","type":"item","id":"Q650893","labels":{"en":{"language":"en","value":"First-order satisfiability in G\u00f6del logics: an NP-complete fragment"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5986991"}},"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":"Q650893$C4ADADF1-151B-44C1-91B1-F9B34D1F0071","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2c02de8478192722eb6ae575f9f026e6b64cc21e","datavalue":{"value":{"text":"First-order satisfiability in G\u00f6del logics: an NP-complete fragment","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q650893$7A26F785-3A1E-49FC-867E-9D433EC27080","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"24f3d04b2646a4b130131b47bf046423f7312737","datavalue":{"value":"1244.03090","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650893$7B4C295C-3685-4B99-AB10-2135D80BED61","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec91c84374e1970ffeb850b5b07163b4a998968b","datavalue":{"value":{"entity-type":"item","numeric-id":167059,"id":"Q167059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$8CCAFCBB-8106-40BF-BE93-FB0F5E779F81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"eb4465c1e4c8de201e147387c933ac41a7d412d9","datavalue":{"value":{"entity-type":"item","numeric-id":385018,"id":"Q385018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$22172668-0DD3-4405-81D2-618D9678D8D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"694d2e8c67abb491571f4dddc9bef501d0565c56","datavalue":{"value":{"entity-type":"item","numeric-id":650892,"id":"Q650892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$AF1CBA11-B8F8-448F-B930-F1C823EBEC24","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$478CE9F7-C493-49B4-8B65-7196DD8A4748","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e38c6f1e03c0365fe5e243370e140f97607764e2","datavalue":{"value":{"time":"+2011-12-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q650893$5936FD9F-03F5-49C0-B6C9-0E8CA85F47CE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fa4ed08c8334c19bc3f45796e333c92faccd282d","datavalue":{"value":"The topic of the paper is a fragment of first-order G\u00f6del logic with \\(\\Delta\\) whose satisfiability problem is shown to be NP-complete. In particular, the considered fragment is the set \\(\\mathrm{FO}^1_{\\mathrm{mon}}(V)\\), a subset of both the monadic fragment and the one-variable fragment of first-order G\u00f6del logic, of formulas in the language of G\u00f6del logic plus \\(\\Delta\\) having the form   \\[  \\bigvee_{i=1}^n \\left( \\exists x A^i_1(x) \\wedge \\cdots \\wedge \\exists x A^i_{n_1}(x) \\wedge \\forall x B^i_1(x) \\wedge \\cdots \\wedge \\forall x B^i_{m_1}(x)\\right),  \\]  where each \\(A_k^i\\), \\(B_k^i\\) is a monadic and quantifier-free formula containing no function and constant symbol. \\(V\\) is the set of truth values (a subset of \\([0,1]\\)) in which the predicates are interpreted.  Note that in general satisfiability in monadic G\u00f6del logic with \\(\\Delta\\) is undecidable if the set of truth values is infinite.  The interest in this fragment also relies on the fact that formulas of \\(\\mathrm{FO}^1_{\\mathrm{mon}}(V)\\) are used to formalize the expert system CADIAG-2 for making differential diagnoses in internal medicine.  If \\(V\\) has \\(1\\) as isolated point, it is not difficult to prove that the SAT problem of \\(\\mathrm{FO}^1_{\\mathrm{mon}}(V)\\) is decidable (this is for example the case when \\(V\\) is finite). If in \\(V\\) the point \\(1\\) is not isolated, then the proof of decidability needs a semantic investigation of the topological properties if \\(V\\).  The complexity issues follow from a reduction to the satifiability problem of a suitable propositional finite-valued G\u00f6del logic.","type":"string"},"datatype":"string"},"type":"statement","id":"Q650893$9141F74F-E848-4163-81A6-80F22E7F2DE6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a2a70f0f285d20f2fec0c316c192a882e68b3933","datavalue":{"value":{"entity-type":"item","numeric-id":591007,"id":"Q591007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$43D6044D-0C53-41B5-9B39-358AB27ABD1B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0ad6448c9e3f2394361827e5c2d117e48dc71794","datavalue":{"value":"03B52","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650893$9E1EE0DB-214B-46DC-9BA3-3947EB583A78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650893$DDC45F13-0FDB-4389-8A78-CC1878E0EDAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"73dccdfb072fb026a86af92d74fe625efeb2b023","datavalue":{"value":"68T35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650893$49A9D03F-17B0-493B-8A98-C24F0A3C7CB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e27beffea4779e8a96e7c5961e8cc7879483d808","datavalue":{"value":"92C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650893$0F10D90E-B2DB-44A5-A54A-6F3DBFECAF21","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dce967f99860c2fd32f8986f1336615b3d90dfd3","datavalue":{"value":"5986991","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650893$75724AA7-0927-459C-898C-F4FB82F6C79F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da9ee2efa056a2d50f77db1d0c8f6a52f653a5d8","datavalue":{"value":"first-order G\u00f6del logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q650893$D6E96CB8-6E57-4BC9-B229-0EF39B98B481","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"252f9f9ed9fe8ca406cc19fba38a46c0414791ee","datavalue":{"value":"satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q650893$1EB1F573-EB29-442C-AC6C-6A317324B682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ef580dc6ba1451aeadb852ac0dd131e497dec33","datavalue":{"value":"monadic logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q650893$C6D14CBA-A762-4E12-8F06-84D807AA38E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25ecbf9cbbbe2ba5a272217776d675fb42cbc74b","datavalue":{"value":"one-variable fragment","type":"string"},"datatype":"string"},"type":"statement","id":"Q650893$1FBC79B0-AB42-424D-B93F-1C805E26B5ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6f411cd977b2103bee33f272cfba7c094c0f1345","datavalue":{"value":"expert system CADIAG-2 for medical diagnosis","type":"string"},"datatype":"string"},"type":"statement","id":"Q650893$D160AC9A-8D54-4882-B959-907E74971C4A","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":"Q650893$6603EBF7-8D4F-4663-B5B7-E983914AF129","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2784dcc41e473d9d066ea48971c30f5fec5293f2","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2011.07.015","type":"string"},"datatype":"url"},"type":"statement","id":"Q650893$F6973DD5-EAA9-4A91-911A-3281F6FC269D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"93b28339d212d2145074e2a46d1744229af0bb3a","datavalue":{"value":"W2096504793","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650893$6DDB42CE-AC52-4C09-80E2-1A7A53B989F8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7bc15f249726e286830d3ad1d34138fb5e2e3d4","datavalue":{"value":{"entity-type":"item","numeric-id":4893133,"id":"Q4893133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$72CE139F-3091-4B81-88BE-42016ADBE1C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c518c18f44c81af14e64f37602ee04f933d21cfc","datavalue":{"value":{"entity-type":"item","numeric-id":3498458,"id":"Q3498458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$A4808103-F59A-414F-9769-6D1F2CB507E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f897f786c8e1886c25b0e6db3a231e333dc409f","datavalue":{"value":{"entity-type":"item","numeric-id":3638278,"id":"Q3638278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$9C7A9BBF-6CEF-4E57-BB7F-41E2CC73FED7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e54c09b2b8cc66915ea23e1c66200f99fb03980","datavalue":{"value":{"entity-type":"item","numeric-id":1580660,"id":"Q1580660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$88CF3D7C-B718-43A7-A776-FC796E6B73B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8a8e7aa3826057e8a68a04faafb879ca50e3653","datavalue":{"value":{"entity-type":"item","numeric-id":2370370,"id":"Q2370370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$E9591E3A-8528-4711-A0A1-F4B642F72908","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b542c3daf2ebc6c2cfa771ac36c3ecb1e039b00","datavalue":{"value":{"entity-type":"item","numeric-id":1013988,"id":"Q1013988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$7200BF41-F092-41B9-874C-4AC828C39F17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd1edcb888e96f446a1331c09f2a0c09105dbc83","datavalue":{"value":{"entity-type":"item","numeric-id":3426561,"id":"Q3426561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$FC3D7B7D-31A2-44BE-976F-5E6AF69BAFE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e027f5650296472fc746ced3fc44df7db916881","datavalue":{"value":{"entity-type":"item","numeric-id":5665173,"id":"Q5665173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$3EC1655C-86E2-4681-BC49-1A31B0057926","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2dec21687bede7beca570d09d16d3ea6c14f888","datavalue":{"value":{"entity-type":"item","numeric-id":1976881,"id":"Q1976881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$C95B4289-D9A7-46CF-A375-554E1FC8489C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8107640f4efa5131b779c96c74a819a031e2d191","datavalue":{"value":{"entity-type":"item","numeric-id":869112,"id":"Q869112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$8BC89155-36DE-4790-B9F1-B0405BE6E43B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ff1803fde0abca892b67ad3b3b6752abf5aba40","datavalue":{"value":{"entity-type":"item","numeric-id":4450446,"id":"Q4450446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$A3AFD7AC-F58A-4F9F-8488-6387FC680957","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f421884f879ae4e0048a14b487c578b45714b0b","datavalue":{"value":{"entity-type":"item","numeric-id":1307301,"id":"Q1307301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$FDF4A99A-6814-4490-B0B3-DC00BB9E93C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8be0f7c81004227114f5bee606cc547dbf0099bc","datavalue":{"value":{"entity-type":"item","numeric-id":3410679,"id":"Q3410679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$D3B39631-7000-4831-9D1E-D8F373784B02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9f773300cd053ea51f6b2e01c0bd0b060f02131","datavalue":{"value":{"entity-type":"item","numeric-id":4323294,"id":"Q4323294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$4432B897-AC42-40D0-A68D-E5AB3DACA2FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0eda07e74c455b9508c4802bce8fdc74d6e13f24","datavalue":{"value":{"entity-type":"item","numeric-id":5738917,"id":"Q5738917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$27491236-B31F-42C8-AE8E-C98A0DCCAE15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60bab06c6efc101c2c178c21ed15568782da3276","datavalue":{"value":{"entity-type":"item","numeric-id":3693510,"id":"Q3693510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$E2115229-7559-4DE5-ACD2-096E46577BBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6bdde33d7655e7b51f89c495e13b554090e3744","datavalue":{"value":{"entity-type":"item","numeric-id":4740561,"id":"Q4740561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650893$40CF185D-7812-49FA-A384-2BD77A820800","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"512162542da091a9ab1c236de4d9cb85e5daac97","datavalue":{"value":"10.1016/J.TCS.2011.07.015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650893$ECBBDE57-F430-4615-8A2A-0910AD7E5D0A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"567a53036494fe5f611d3a1443ce42a5d092542d","datavalue":{"value":{"entity-type":"item","numeric-id":3638278,"id":"Q3638278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"786f4a943b6f604615af2f401ebd10b549f9965c","datavalue":{"value":{"amount":"+0.8550581336021423","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":"Q650893$4C96D649-BE66-404E-B544-3CFFF2CEDD3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3b5564a2136dab1167c218b225ffcec94caa35e","datavalue":{"value":{"entity-type":"item","numeric-id":4645749,"id":"Q4645749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d3e731a24c827854183b908cf5b6180d6548640","datavalue":{"value":{"amount":"+0.7904866933822632","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":"Q650893$D8D1894F-D5F4-4080-ACF8-D82108B5A8AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b3a74f366c5bf1ca13f2a718d636fa2eb20035e","datavalue":{"value":{"entity-type":"item","numeric-id":3498458,"id":"Q3498458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a87deab3ee289aecf32edb49ffd1940d351cbf4d","datavalue":{"value":{"amount":"+0.7884849309921265","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":"Q650893$17751BA4-13B0-473F-A514-1A7916FDA6A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c638b4c1f2bbf7de0d024f9c8a2b72fdbbe9911","datavalue":{"value":{"entity-type":"item","numeric-id":2370370,"id":"Q2370370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc99d556ba68f4a572138be69cc9d856fa473f96","datavalue":{"value":{"amount":"+0.7819607257843018","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":"Q650893$53398210-B9D3-4163-84E5-FB3E1B5CBCA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"412f3b6cddef730dc4ebc4d23d96b8bda753925b","datavalue":{"value":{"entity-type":"item","numeric-id":1616771,"id":"Q1616771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ed93004bd165674f4550335e5ac8bf6697b7c3c","datavalue":{"value":{"amount":"+0.772923469543457","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":"Q650893$F71193E8-FB2D-4896-97A8-E184FB259373","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"First-order satisfiability in G\u00f6del logics: an NP-complete fragment","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/First-order_satisfiability_in_G%C3%B6del_logics:_an_NP-complete_fragment"}}}}}