{"entities":{"Q685537":{"pageid":687386,"ns":120,"title":"Item:Q685537","lastrevid":78195782,"modified":"2026-05-06T11:01:00Z","type":"item","id":"Q685537","labels":{"en":{"language":"en","value":"On the complexity of recursive path orderings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417428"}},"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":"Q685537$ABC54E94-1B07-4D8C-ABBE-A48062F985E9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"40169335d3a095c6842c3edc996dc791b49bc554","datavalue":{"value":{"text":"On the complexity of recursive path orderings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685537$9A9007C8-318F-48D5-BDAF-797D92CBEB72","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c29c2347eaaa180127723ae42842940732746460","datavalue":{"value":"0778.68045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685537$4A257A09-D4DF-42C9-A09C-FB47C8ED829C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1b18e32947d1d4826e4563358a7c7255122af3f0","datavalue":{"value":"10.1016/0020-0190(93)90105-I","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685537$ABE52EA9-C0CE-4ED5-AFC1-7374AFB37B2F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"08806ac259b69338711fcb06260641ec2a055681","datavalue":{"value":{"entity-type":"item","numeric-id":685536,"id":"Q685536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685537$9BBECF87-6967-491F-9FA9-BE710FFD4289","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":"Q685537$341828F8-94A0-4CE6-92FD-2DE89F76287C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"729108c69527af72f2ca1b9041a9358219bdc1fc","datavalue":{"value":{"time":"+1994-01-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685537$A02DBC0C-F113-4DDF-86DF-F41A1F0B6C1A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"64bb02b90b676fb6416b7ca7c7c79371a7ac5fb1","datavalue":{"value":"We give a fast method for generating reduced sets of rewrite rules equivalent to a given set of ground equations. Since reduced sets of ground rewrite rules are in fact canonical, this is an efficient Knuth- Bendix procedure for the ground case. The dominant cost of the algorithm is for congruence closure, so the method runs in \\(O(n \\log n)\\) time and quadratic space, or in \\(O(n(\\log n)^ \\land 2)\\) time and linear space, where \\(n\\) is the number of occurrences of symbols in the original set of ground equations \\(E\\). We also show how our method provides a precise characterization of the (finite) collection of all reduced sets of rewrite rules equivalent to a given ground set of equations \\(E\\), and prove that our algorithm is complete in the sense that it can enumerate every member of this collection. Finally, we show that a modified version of this procedure can produce a reduced ground rewriting system contained in the lexicographic path ordering generated by a given total precedence ordering on the symbols of \\(E\\), still in a worst-case time of \\(O(n \\log n)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q685537$411F1B27-E67A-4DF2-A149-340121EC25A1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685537$69EB5BC0-DA59-487C-9DE9-40EFC00E608D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6e7c2e9d67f9590a26e18c734f34db53ce5ec87","datavalue":{"value":"68T15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685537$F8458E85-7F9C-4D2F-B939-24C90451532C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685537$86E564C4-0F20-4DD2-A26E-D3D621BEEA42","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0e29880723920fb7834910b97e923ecaebaee822","datavalue":{"value":"417428","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685537$4A5C4007-E212-4EBA-8B2E-5823D0132B7B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0f3e66d0c05c393bbc596d169abb55b93f3e0f1","datavalue":{"value":"Knuth-Bendix procedure","type":"string"},"datatype":"string"},"type":"statement","id":"Q685537$281E2359-4452-4AB9-BE1B-2E9CFB780836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29bf1e7f5f0084af3c8bb4d65234dcc9133aca3d","datavalue":{"value":"ground case","type":"string"},"datatype":"string"},"type":"statement","id":"Q685537$946BAA09-A21F-4E6A-991A-E3514879006D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de905e03d2f101d19466f3cb4759ec84e2b10ed3","datavalue":{"value":"path ordering","type":"string"},"datatype":"string"},"type":"statement","id":"Q685537$86E2D555-FE6A-4A80-825E-513F15FFD098","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":"Q685537$98C232F7-2E51-40F1-BBA1-709890BB1DE7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685537$1BB1C298-DED6-4FC2-A772-F4F00AA189CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e38c2f2e2ea48fd30061f5b3a3a8d0dacb950761","datavalue":{"value":{"entity-type":"item","numeric-id":4264723,"id":"Q4264723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685537$FCDB49D7-005F-49B6-B3CC-11D6A7D4ED25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6d3f5f0e6d39b0610560c479018fc71a2adcd20","datavalue":{"value":{"entity-type":"item","numeric-id":1098624,"id":"Q1098624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685537$34B3B0E9-9603-43E8-9B95-4BEF323C2768","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a01d4a91dcf05e247efe3d36d8b1cf5c4792f88","datavalue":{"value":{"entity-type":"item","numeric-id":4385532,"id":"Q4385532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685537$750FB10E-A319-4A58-B365-8516454C3E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bc614fe187bd0295ec729cf32cb3675e34b7b37","datavalue":{"value":{"entity-type":"item","numeric-id":4302847,"id":"Q4302847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685537$8C5A6986-19C0-43CB-8D2F-1F402709BEFC","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":"Q685537$82493CD6-4CB0-4933-ACB9-94A2D5116995","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4febb634b64d2f4bf70a6faf5990dbefd157552","datavalue":{"value":{"entity-type":"item","numeric-id":1082075,"id":"Q1082075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685537$7159C114-5A08-49E8-8DFE-E221653C746B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dec90514b3ee51c6aeaedd6a27b942e28206d994","datavalue":{"value":{"entity-type":"item","numeric-id":1099655,"id":"Q1099655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685537$5DBF7274-5FBE-4DFB-B9DB-9C830EBC8530","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7bc0556fcf14eb9842b401bc99d2ba45581b7a1e","datavalue":{"value":"https://doi.org/10.1016/0020-0190(93)90105-i","type":"string"},"datatype":"url"},"type":"statement","id":"Q685537$F35E9C67-7395-4921-A3EE-BE9B7D8D0218","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8ef6fdeb83b84d8a75678811604445bdd5bea9d3","datavalue":{"value":"W2041678518","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685537$8D640BC1-64DB-44C1-BCBF-4DAC0D7A6505","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f2b4152c95ffe583a7bb15981322f8abdb952d2","datavalue":{"value":{"entity-type":"item","numeric-id":5055736,"id":"Q5055736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3735a566ab089405860497891f54e8890576eea0","datavalue":{"value":{"amount":"+0.90147602558136","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":"Q685537$B36CEA68-222F-485A-87C1-AE3C1DD399AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"560b28a04f4c5bb1e763f023552eb3932641561d","datavalue":{"value":{"entity-type":"item","numeric-id":689111,"id":"Q689111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42a9217c300777d71460a0244defc757ffa68f6f","datavalue":{"value":{"amount":"+0.8440633416175842","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":"Q685537$74544B01-6CD1-4790-ADC2-55DEF8FA0186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a69148a98bb8be578ebffce87b8b01398d403a2","datavalue":{"value":{"entity-type":"item","numeric-id":4005178,"id":"Q4005178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30985eaf7395d321fe164ce5bd7789da13bddfb6","datavalue":{"value":{"amount":"+0.8358877301216125","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":"Q685537$757C4041-4B5B-4016-BB2B-2E60FEF25F64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26beb7d978a000922c3b45bfc5d117e96e06d354","datavalue":{"value":{"entity-type":"item","numeric-id":4033833,"id":"Q4033833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c05c017bca3bbceb173c586e43214d77143ec734","datavalue":{"value":{"amount":"+0.835324227809906","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":"Q685537$CF6250FA-A0DF-45B2-8F91-256541EF95FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4dfd60752e5a526f819ef0a629d7320e9888273","datavalue":{"value":{"entity-type":"item","numeric-id":5055737,"id":"Q5055737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"829396d3b5d5555ecf238889938596d832d5eddd","datavalue":{"value":{"amount":"+0.8270431756973267","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":"Q685537$3BDDD557-3295-4E14-BAAB-6FC440781B98","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of recursive path orderings","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_recursive_path_orderings"}}}}}