{"entities":{"Q1082075":{"pageid":1092827,"ns":120,"title":"Item:Q1082075","lastrevid":70576344,"modified":"2026-04-13T15:33:29Z","type":"item","id":"Q1082075","labels":{"en":{"language":"en","value":"On recursive path ordering"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3972182"}},"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":"Q1082075$87AB398A-4739-4AAE-93D1-E0144034BD5F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2db9584673a88682de3ac23363201e79955c34c7","datavalue":{"value":{"text":"On recursive path ordering","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1082075$079593B1-F80E-4E94-B9E5-8884D3C604C7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6efffc94f052180c8957278d8acab0820ac185d6","datavalue":{"value":"0602.68031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082075$B5140680-FEAF-46C6-92DF-37718A8214F1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2931d4939aa1693cc0e0bdc0aeca4f74a5e10121","datavalue":{"value":"10.1016/0304-3975(85)90175-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082075$D728299E-37BD-4CEA-AFA5-758259F0B64D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9c6edca5bf1daef00082b7b01041eecf3822e0fa","datavalue":{"value":{"entity-type":"item","numeric-id":1063003,"id":"Q1063003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082075$C03635EE-3E67-44E7-B97D-86B1791DE389","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6587fdd31c2d2b6b0dfb7e31f546481ef32f5a93","datavalue":{"value":{"entity-type":"item","numeric-id":171405,"id":"Q171405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082075$E32E6922-1EB5-4821-AF65-3B85BA4C8643","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":"Q1082075$A84FA807-DD4E-48A1-AF23-B672F3695120","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1082075$9D0C1578-63E1-4CA9-B5B2-943EDAAC35AC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"95e077b5b6838315461158d758dca2894075c232","datavalue":{"value":"The ''recursive path ordering'' (RPO) scheme of Dershowitz is a powerful way of extending a partial order on a set of function symbols to a well- founded partial order on their set of terms. We prove that, given a pair of terms, the problem of deciding whether they can be made RPO- comparable, by choosing a partial order on their function symbols, is NP- complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082075$647C5DCC-E5A3-4536-9391-AE6DC164E64A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"092d9a7dfbbaaa84ba458f8d83190fce94c9aa54","datavalue":{"value":"68Q65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082075$474B04D1-0AAB-4DA0-B737-4BF8486E74E2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a0fbe793751e833d118a5698ac06e140be26406d","datavalue":{"value":"3972182","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082075$92E1362B-268A-4E4D-B620-25A5A7AE6708","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58acf4952d5f9adc27bc95a2037859c88d48f9a6","datavalue":{"value":"term rewriting systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082075$C366E2D0-3E07-4243-9728-CACF290F155D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4befa4ca20f2beabcfa09e8a92ae13c21cb4934a","datavalue":{"value":"termination","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082075$8913EA95-A644-4F41-B38E-52A4A6E14A43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"37b320d45dc99ecd610b427c553166863319a84a","datavalue":{"value":"well-founded partial order","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082075$E91BA1AF-84D5-40E7-8E7C-1BCAED7DEC7E","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"cdc09159c3d9e35e53ef549059a47b095580c647","datavalue":{"value":{"entity-type":"item","numeric-id":40621,"id":"Q40621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082075$87F3CB2F-FE6D-4DC8-9EFA-71A7F80BFDC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"3f1ebf2accc5d6c6b3c7a81ee7493fd53a6bf250","datavalue":{"value":{"entity-type":"item","numeric-id":40618,"id":"Q40618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082075$D9974A31-1C70-42F4-ADC4-1307FF8DD507","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":"Q1082075$08FE20A5-B511-4AD3-92AF-EB10B3D94B51","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c40e6ac7fa05bbc855d532904d0df5ced59bb387","datavalue":{"value":"https://doi.org/10.1016/0304-3975(85)90175-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1082075$6DE11604-80FA-4D9E-A58B-C311BDC04D64","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"48f7d2f0f38cecd3d09e2f68eba8d560fa84bd94","datavalue":{"value":"W2055323844","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082075$BEA37549-E646-4AF0-AF16-68B94CDB7882","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"378088a63ec20245823db74d6a8845609e39ce21","datavalue":{"value":{"entity-type":"item","numeric-id":593789,"id":"Q593789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082075$DB7738B1-0FBA-456C-927B-CC63063AF81F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082075$35D73EE2-D8A4-4954-B2F7-7595036EC9FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d9d1a825019987eb50d4a73ab4b5db6ef28ea3c","datavalue":{"value":{"entity-type":"item","numeric-id":3040518,"id":"Q3040518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082075$AEC1BDA0-AEA9-436C-849C-0652B8F5AE39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"599c5dbf52817fbbe5f2f15e33a96dc6ac97514e","datavalue":{"value":{"entity-type":"item","numeric-id":3908463,"id":"Q3908463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082075$558638B5-16A4-4828-96FD-5520DE93429B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89e6b612eb3cb0e65ff83e8cd8762940dc520785","datavalue":{"value":{"entity-type":"item","numeric-id":3659124,"id":"Q3659124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082075$F4306A7E-FB66-4091-BF34-1BAE72FD1412","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"108976005e438ca70f7496d07e6faca25fa804e7","datavalue":{"value":{"entity-type":"item","numeric-id":3683533,"id":"Q3683533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082075$F0EB7177-24ED-46F1-9680-7A4F3461AC0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1e0b4fc54e8c62a86959e50d4b1b27d9d9a092c","datavalue":{"value":{"entity-type":"item","numeric-id":5581665,"id":"Q5581665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082075$EDA05243-3FA9-4A0A-B631-D429F5CA2864","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90876a4dccaf3458c2fc1c0199e90fd643a98046","datavalue":{"value":{"entity-type":"item","numeric-id":2956685,"id":"Q2956685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9132c9809984e34ee299465a22465058a1ceaaca","datavalue":{"value":{"amount":"+0.811794638633728","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":"Q1082075$93C6B44F-D0E1-4162-BE6D-ED0FECC3BF6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16b90152383a36e8bc6576cf3eacb06fc6bff521","datavalue":{"value":{"entity-type":"item","numeric-id":1400710,"id":"Q1400710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81ed053634806e726bd76f8f37f02014ccb1bc16","datavalue":{"value":{"amount":"+0.804688572883606","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":"Q1082075$7A7BD6AD-F323-4E6B-8D4F-673651FEF7E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4cd1a497e9d5bd1ff971781bbed7782a9278c0b","datavalue":{"value":{"entity-type":"item","numeric-id":3683533,"id":"Q3683533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"803559bcbdf60048653a723143d88d45cbbdd8e3","datavalue":{"value":{"amount":"+0.7977514266967773","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":"Q1082075$A0AB8DBC-6076-44FF-B1EC-ACAAFB1D0062","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a59c7ea6c5854084cd587246962e42d311985555","datavalue":{"value":{"entity-type":"item","numeric-id":3696501,"id":"Q3696501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6573cb5a644fba8544dc3884a86f551b3dc4ded7","datavalue":{"value":{"amount":"+0.7971507906913757","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":"Q1082075$472AEB76-9A5A-4120-B671-0F365DC5D65B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6abf472cc06f041e411014a2c7ec21d00c56471","datavalue":{"value":{"entity-type":"item","numeric-id":4914419,"id":"Q4914419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c94942c63699104d854fc48a40c6d7002c3c52f9","datavalue":{"value":{"amount":"+0.7911059260368347","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":"Q1082075$3FFB2445-7548-4E22-9489-AE5520C6D695","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On recursive path ordering","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_recursive_path_ordering"}}}}}