{"entities":{"Q685481":{"pageid":687330,"ns":120,"title":"Item:Q685481","lastrevid":42641200,"modified":"2025-07-07T14:52:52Z","type":"item","id":"Q685481","labels":{"en":{"language":"en","value":"Simple LPO constraint solving methods"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417395"}},"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":"Q685481$8CC8B0B3-456F-4134-AEE3-E5BAEEF37917","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0b22e51a4114b0df040b2fec7b451eff12dfb027","datavalue":{"value":{"text":"Simple LPO constraint solving methods","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685481$B028C8BA-7DCE-4E11-8FE3-5F0EF7BAF86F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"067ddd5f3002849c7a152f211b623530cc8da6ce","datavalue":{"value":"0781.68102","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685481$4AC5C350-C473-42B8-AEF3-6EB789EABB8C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fa5b378e88053253e913c3b4358b80bd8032d462","datavalue":{"value":"10.1016/0020-0190(93)90226-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685481$53F97D37-EA57-40FE-A769-0B26C8FF9A49","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1e6a58ff964b9ca97414f0c42659717fa8e6fc43","datavalue":{"value":{"entity-type":"item","numeric-id":475169,"id":"Q475169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685481$202E2D4E-FF73-4F1D-AF9D-51FF42A72632","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":"Q685481$0F48A1B5-671F-4C3E-BDAE-98CD553B80C6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ea9458ce3029a7f683c04e43e886fdc910ea299c","datavalue":{"value":{"time":"+1993-10-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685481$C9369DA8-DC13-4096-A519-D5AD053515F0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"95a279d22f7a5820cd68f21bd1b2dc9f80a3f148","datavalue":{"value":"Satisfiability of lexicographic path ordering constraints was shown to be decidable under the given signature by \\textit{H. Comon} [Int. J. Found. Comp. Sci. 1, No. 4, 387-411 (1990; Zbl 0722.03012)]; the author and \\textit{A. Rubio} [Theorem proving with ordering constrained clauses, Proc. 11th Int. Conf. on Automated Deduction, Saratoga Springs, NY, Springer, Berlin, 477-491 (1992)] obtained the like result for satisfiability under extended signatures. Both satisfiability problem are now proved to be NP- complete by reducing the constraints to disjunctions of ``simple systems'' (conjunctions of equalities and inequalities); it is argued that this technique should have practical relevance.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685481$C18FB505-E513-472A-95DF-5CCA2AC204C9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6e7c2e9d67f9590a26e18c734f34db53ce5ec87","datavalue":{"value":"68T15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685481$90A4FA61-E859-488C-A37F-1AB7AD1C7199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"10eaeaf8bbf8231bbfc812aab8956e260b5a9f12","datavalue":{"value":"03B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685481$C7372E15-CC5A-4AE2-A246-D84BFB5B5550","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685481$4A4EC4E5-7C00-42DE-B181-E72F83C0D762","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9911ea56c0a201a1ec2a6d067b0e510eeaa068d6","datavalue":{"value":"417395","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685481$91B7677D-BAB1-444D-988D-D1AB94525B49","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c04c463362cb0b9153ae29618073b289bb745f17","datavalue":{"value":"automatic theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q685481$E80A1910-5B25-4117-B110-A11788A4804B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e387b99154d26aa609b68058fc2c4480ac6963b9","datavalue":{"value":"proving","type":"string"},"datatype":"string"},"type":"statement","id":"Q685481$D27DB403-0A34-40BE-833A-10DBEA38C699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q685481$40F85386-6941-4451-8197-B46E9C009D8C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ce55c35a0130dff40a2e46fd6cbf84198a7e9797","datavalue":{"value":{"entity-type":"item","numeric-id":590016,"id":"Q590016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685481$69CFB0E2-9380-4C13-9245-4D86D22D388B","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":"Q685481$3333100D-49E0-49F1-8F2C-9D85745BCDEB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"eeaefa1501b49eb11345a7390fa93c7aaa33fb8a","datavalue":{"value":{"entity-type":"item","numeric-id":5753928,"id":"Q5753928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685481$DE64FCA3-4E01-47EC-AE78-B51D44B00F5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ea54b811ff390aea0ed0ec764fa22772489e900","datavalue":{"value":{"entity-type":"item","numeric-id":4036585,"id":"Q4036585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685481$D3507453-B1A9-42C4-BA0B-A81AB55315D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8c9c1aeb9cd97d0f637554f9533dd19252fdc52","datavalue":{"value":{"entity-type":"item","numeric-id":4264721,"id":"Q4264721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685481$8EE81FB2-D8A9-4A0C-80DC-CBCD4273DC20","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba00f0a729b4f4944deb9d9d9c6bfe7792bfcaab","datavalue":{"value":{"entity-type":"item","numeric-id":3131805,"id":"Q3131805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05dcf10c583504b6d3c3757364b793957503c461","datavalue":{"value":{"amount":"+0.87689626","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685481$2103C990-37BF-4856-95FF-E70EE6BE9E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fec5181653640d40c17597bbc5114109377a3ab3","datavalue":{"value":{"entity-type":"item","numeric-id":1278588,"id":"Q1278588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a8efc6aa76c3d7a56fa49054d6519047e70bdfb","datavalue":{"value":{"amount":"+0.87123686","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685481$D9D75FC6-854A-470C-957A-366BF6DACA94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"faf4d5fb5c49b456436c40fe32954b7d188030d4","datavalue":{"value":{"entity-type":"item","numeric-id":5449561,"id":"Q5449561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b57687a1fba5d23002c2251fab268e2ba491568b","datavalue":{"value":{"amount":"+0.86997867","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685481$E0483630-B64F-420B-8A1C-0198C69F609F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c3a0ffc71c3808155445eba803fefe71450bad4","datavalue":{"value":{"entity-type":"item","numeric-id":5450069,"id":"Q5450069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f591b959edb7c3a77bada214bbd2b64a5a06b4c","datavalue":{"value":{"amount":"+0.86531705","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685481$3C9824FB-3C6F-452F-96AF-72275F363B0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dddf28396e416804757cc431e034fe59cee06ffe","datavalue":{"value":{"entity-type":"item","numeric-id":3486364,"id":"Q3486364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfa67ebb648a1624588db9e7ce1b581316ca4fd3","datavalue":{"value":{"amount":"+0.86362505","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685481$D5136078-EC67-4818-85DE-18BF51A5B6D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c3a96ad1bebd3fd945f745640f85279fafdb359","datavalue":{"value":{"entity-type":"item","numeric-id":5287089,"id":"Q5287089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7047399a6cdab55adf13205b62d3e7f5e8a43f5","datavalue":{"value":{"amount":"+0.85781544","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685481$27B7DEF9-ED5E-4027-9737-C6893E3934BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41c540be178aebcbefe4a6c4e7e5b6dedd161785","datavalue":{"value":{"entity-type":"item","numeric-id":3367121,"id":"Q3367121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21193818791f6494eb87e83620ecc08c6b4034b7","datavalue":{"value":{"amount":"+0.85578966","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685481$62E5DEC8-E899-48D4-97F1-01E11E572FB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d221838057ba700065c387daa461cd7843f90ada","datavalue":{"value":{"entity-type":"item","numeric-id":3081837,"id":"Q3081837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"686a5ca6bb69857c596074953011b6c98150270e","datavalue":{"value":{"amount":"+0.85269","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685481$9E9AAE3D-ACDD-460E-9D2B-BBDFAFD80185","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd6222e034a410978f6163eb852a10f55f151249","datavalue":{"value":{"entity-type":"item","numeric-id":4889529,"id":"Q4889529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5c8b77c440e6e47f82edf60a6ee0aca7714b728","datavalue":{"value":{"amount":"+0.85223186","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685481$4FCE7085-071C-4226-B393-66EB046D84C0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:685481","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:685481"}}}}}