{"entities":{"Q1097717":{"pageid":1108469,"ns":120,"title":"Item:Q1097717","lastrevid":49133464,"modified":"2026-01-06T15:48:31Z","type":"item","id":"Q1097717","labels":{"en":{"language":"en","value":"An \\(O(n^ 2)\\) algorithm for the satisfiability problem of a subset of propositional sentences in CNF that includes all Horn sentences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4035207"}},"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":"Q1097717$D704ABF7-A79E-4C7A-92AD-C096B2E68536","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2d0d44b7077e7fd3e235ec9057000d5a97c5bf89","datavalue":{"value":{"text":"An \\(O(n^ 2)\\) algorithm for the satisfiability problem of a subset of propositional sentences in CNF that includes all Horn sentences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1097717$EC430716-9095-4B6E-BB13-58C9B2CDF2A6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f770ac612a8b0e5827794b186fbafc52bbab7322","datavalue":{"value":"0635.68108","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097717$56EA2E87-6E6C-4A4D-92CF-97B8B7E71B0D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"36194e82a4737c6a939a3bf9ae83a66040a9d1e0","datavalue":{"value":"10.1016/0020-0190(87)90200-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097717$4ABD7B84-D0FF-4D16-9CB5-22F1EBBB37EC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"83acb26c132edffe3503227fdedd09777c685939","datavalue":{"value":{"entity-type":"item","numeric-id":1060191,"id":"Q1060191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097717$F3FE5472-554D-46A5-8EB9-0CB74A15ECEB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097717$69B4DAC3-D32B-4AA7-9FD7-A9F1F1E94BDE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1097717$F284DAB4-6639-4B38-A1B9-861672AA0CFC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"88f826d8519494bc7027e780ffd658a406f390f2","datavalue":{"value":"Based on the results of \u00cctai and Makowsky that recognize satisfiable Horn sentences in O(n) time, the authors present in this paper an algorithm that improves the performance of the algorithm of Yamasaki and Doshita of solving the satisfiability problem for a class \\(S_ 0\\) of propositional sentences that properly contains all Horn sentences. The algorithm, its correctness and complexity, and the structure of \\(S_ 0\\) are presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097717$E4C5EAFC-62A1-4B25-BB8A-40452D82FDD9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6e7c2e9d67f9590a26e18c734f34db53ce5ec87","datavalue":{"value":"68T15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097717$E74FE305-106F-4BA5-840C-E67496CFF7F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097717$EBCE90C4-C7CA-459B-8F76-F33128337F30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"10eaeaf8bbf8231bbfc812aab8956e260b5a9f12","datavalue":{"value":"03B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097717$BD538738-245F-42F2-B84F-B926CA889B1C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b3000de8c4d77bfd8b320deacce482f73fdf09f1","datavalue":{"value":"4035207","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097717$F48278D9-B45A-4D83-BFD7-1A1EC161DA32","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cbb1eab08408710abe553062777e22e027ce4880","datavalue":{"value":"Horn sentences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097717$00D47C83-8310-4895-B2C1-40A98427925E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f0b4d6e6089943a261128dec792d30fd4cdc9763","datavalue":{"value":"satisfiability problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097717$451C45C8-2F34-4DD4-97D5-2BE8EEB7B96B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7965187f51ff4168cd435c9b72248b0606765a09","datavalue":{"value":"propositional sentences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097717$37FB7E12-490C-42EF-8407-EB591F3C7B49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097717$27D65F15-AB79-4601-A5AB-29A21A1E7109","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":"Q1097717$084F082A-E632-4641-9E51-3FF8736AD829","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fa1fe0cfe9903d9f212492dfae09d1533c4ae526","datavalue":{"value":"https://doi.org/10.1016/0020-0190(87)90200-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1097717$1954B9F1-A0FF-4122-8E63-F8EDD5C4E604","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7e28cec9ac8a59c1f3426ebb05b53d048370a2a7","datavalue":{"value":"W1996333228","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097717$DA3D90C6-A325-43FB-B981-4E5471EDE9D3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4aff056159aaf1cff504830007d8fb1af49169b","datavalue":{"value":{"entity-type":"item","numeric-id":3782840,"id":"Q3782840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097717$9C88D9D3-D7C4-4202-BBAE-231D0AE24278","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b353bc1298597265c71a16d3c350d4e62f0e57f","datavalue":{"value":{"entity-type":"item","numeric-id":3677734,"id":"Q3677734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097717$986CB615-E8AA-4804-ABA0-DAA2CD4A0100","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a27e17451f20c33485f58a57d2667b7321d08684","datavalue":{"value":{"entity-type":"item","numeric-id":3677734,"id":"Q3677734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b01b7c7a0d2accc230581e54e6fedcc7fcce83d","datavalue":{"value":{"amount":"+0.8443446755409241","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":"Q1097717$D071BE3F-1782-4B85-8D23-8E73F9B02F2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2105f0c71536059d0b6d9a52909981c1a5ac2ee","datavalue":{"value":{"entity-type":"item","numeric-id":3723723,"id":"Q3723723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af0967c39637e3cb5fcfb05435292d05b8cdcfdb","datavalue":{"value":{"amount":"+0.8431435823440552","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":"Q1097717$1F552DED-32A9-44AA-95C4-5A589BC7760F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd01bc225923ba0424c86610ffc3038c50c8740f","datavalue":{"value":{"entity-type":"item","numeric-id":3826123,"id":"Q3826123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c91e8cfe4a5eae19713d66dcea7fc3856d92635","datavalue":{"value":{"amount":"+0.8254958391189575","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":"Q1097717$0F411BA6-BEDC-4FAB-964E-60EEC5595CA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c48f56e941190cd2911d5ff958db66c22ca9b5c","datavalue":{"value":{"entity-type":"item","numeric-id":1114394,"id":"Q1114394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0f1f76fd9e6f0b5f287aec5500d4ccc97eccfad","datavalue":{"value":{"amount":"+0.8221397399902344","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":"Q1097717$D51652C3-704A-483B-A4F5-CB6205F1E7D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d1fa86bb5f67d0f806395b601846298917bf334","datavalue":{"value":{"entity-type":"item","numeric-id":1082830,"id":"Q1082830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2649310af030afaa0786cb2c075a51396a6f085","datavalue":{"value":{"amount":"+0.8128398060798645","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":"Q1097717$1C8CB555-9405-46AA-8E36-EEB3DDF147E9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1097717","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1097717"}}}}}