{"entities":{"Q791314":{"pageid":793162,"ns":120,"title":"Item:Q791314","lastrevid":64368450,"modified":"2026-04-11T19:23:43Z","type":"item","id":"Q791314","labels":{"en":{"language":"en","value":"Finite complete rewriting systems and the complexity of word problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3850471"}},"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":"Q791314$F3F6FE8E-D916-402B-A475-24A31138C131","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ce8dcd89bb187ee4bbb86b07ed95e6fa66760b9d","datavalue":{"value":{"text":"Finite complete rewriting systems and the complexity of word problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q791314$BC01F5D7-5CE5-4A9B-8D79-50D992CE4D47","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c0789f62be0c9f7a7ff43918182a940aa1ad9ef5","datavalue":{"value":"0535.68019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791314$041C8F08-70D8-4B26-B0DF-30151379DD87","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"57f4f92fcf0401aee5f1479ee844cd64877c2f98","datavalue":{"value":"10.1007/BF00271645","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791314$F4EA77D5-4000-45E0-ADC9-BA7E5646F1E0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$4D94FD8B-130C-4EDB-A1DF-15AA6CA99CAB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q791314$7D9BDA5A-5696-490F-8ED3-F4976B3AC9BB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2f83b86e5284a623055e4611119f0b06bdb08e8e","datavalue":{"value":"It is well known that the word problem for a finite complete rewriting system is decidable. Here it is shown that in general this result cannot be improved. This is done by proving that each sufficiently rich complexity class can be realized by the word problem for a finite complete rewriting system. Further, there is a gap between the complexity of the word problem for a finite complete rewriting system and the complexity of the least upper bound for the lengths of the chains generated by this rewriting system, and this gap can get arbitrarily large. Thus, the lengths of these chains do not give any information about the complexity of the word problem. Finally, it is shown that the property of allowing a finite complete rewriting system is not an invariant of finite monoid presentations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q791314$407F669F-4BBD-4BB6-8D5D-9D73D510968B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791314$D9CDD7B5-BF1A-4F95-8D5A-1566DF0E6A8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"21699a423435669f291d1bd1ba3da28fa1465b3f","datavalue":{"value":"03D03","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791314$3D72B20B-22F6-4D17-A5C1-62B8EB5C159D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79c9a014785e41c94f76c463174af5cf2a59ec70","datavalue":{"value":"03D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791314$EC1D7DF9-2873-4AA4-8629-B16FB5B830A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791314$902CAA87-ABA6-44D8-A0FA-108D5A4AFECA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"aada7b5ac7ee25a634806a2ad3d322811329ab75","datavalue":{"value":"3850471","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791314$E87BF4AE-692F-4A36-AA7E-7A29AC37B118","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"541e14ca1a9bb27a1cfe827610ca5ddb594a16de","datavalue":{"value":"word problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q791314$6B920CD0-F5EE-4C8C-8C83-4CA9E942B703","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6432ae523837d7dcee6e53851a1bc0c8e3d7aa1","datavalue":{"value":"finite complete rewriting system","type":"string"},"datatype":"string"},"type":"statement","id":"Q791314$C9EE1C8F-7652-483A-88A9-27F8691A3B2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f1f87b0e1df54e6065b1d5b89e7a078354c22bd","datavalue":{"value":"finite monoid presentations","type":"string"},"datatype":"string"},"type":"statement","id":"Q791314$17BD980D-47CD-4EB9-98A3-5E626FB32132","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"48ddbfe7c1fbede2e5486efb3d24ec9aaf902835","datavalue":{"value":{"entity-type":"item","numeric-id":2269717,"id":"Q2269717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$4B5A6BCA-C61B-4BB4-B1C0-0D36E3929494","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f46c7c00558d7121734d489049799fa24953dd04","datavalue":{"value":{"entity-type":"item","numeric-id":287428,"id":"Q287428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$004BD4CE-A123-4C2E-B60E-3712D04E6F74","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":"Q791314$67C6BC76-FA6A-47B6-A78C-19999F96E20F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"39f8caa4d24218ecf63bb6d39ed1b79a4c2266ea","datavalue":{"value":{"entity-type":"item","numeric-id":3936184,"id":"Q3936184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$8C1422A6-BC81-4609-A2FA-DF95B23F8AED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d0d60285ae04471993c98b6fd4f9789d850bb6c","datavalue":{"value":{"entity-type":"item","numeric-id":2902935,"id":"Q2902935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$8A845B16-C63F-400A-AA59-D23CE83C299A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"954424d38b0084062ecb04ce2fedd4da29a556c1","datavalue":{"value":{"entity-type":"item","numeric-id":3957939,"id":"Q3957939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$151DC1CD-AEC2-46B6-A77D-EB9F345DCE1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6db44461333ef5e5aae7abb248658a05e60ef41","datavalue":{"value":{"entity-type":"item","numeric-id":3247126,"id":"Q3247126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$B510CFC6-7776-48FC-8942-0CCD493A5FD9","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":"Q791314$A151A1E9-B964-4C08-A869-75B9F9946F90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cee115f650dd9b2c9350f8cdefbe2dab8f0e067","datavalue":{"value":{"entity-type":"item","numeric-id":5824357,"id":"Q5824357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$AD656814-1508-4346-BE04-2C881E43CCF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a488dfc1f4b2227eec634f19254790ea77c725d","datavalue":{"value":{"entity-type":"item","numeric-id":5622171,"id":"Q5622171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$39521B28-FA32-4E01-A04F-5F9EC59CE92B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$191D5961-BB33-4EAC-B34A-E13CCE9A3BDE","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":"Q791314$16001C70-7BCB-4855-BBCA-A3728D3C8780","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bb7e17689f7a32c0ad80890bf5d055b34c49978","datavalue":{"value":{"entity-type":"item","numeric-id":1073016,"id":"Q1073016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$F3DA795C-1A3E-4C23-BD04-20F5D60C7331","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":"Q791314$82BE67E6-1774-46F8-8642-1DF0E07AEA3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8941439de739c4cd65cdb44fb63c71009c2cabaa","datavalue":{"value":{"entity-type":"item","numeric-id":1229713,"id":"Q1229713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$A25BB4FB-0013-4B08-B7F9-F2F35B612B8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"590501c171be3baf72dfd4a760c5a38fc1164b28","datavalue":{"value":{"entity-type":"item","numeric-id":3934601,"id":"Q3934601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$653D4454-80C7-4930-80A8-851D224FBC11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f33f843778dfabfeef453cdfa627d4b42c24908","datavalue":{"value":{"entity-type":"item","numeric-id":4131648,"id":"Q4131648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$E6163F9E-DB51-4D74-BC78-35763D63A1C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"224fe5205d72f8b7bf3d1117c14acd86046e588d","datavalue":{"value":{"entity-type":"item","numeric-id":2652528,"id":"Q2652528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$5B770C97-735E-4F1C-9BE3-B2FB11ABAA91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc3903ed6b3b73f38caeb2f53f2e93e11217ca6a","datavalue":{"value":{"entity-type":"item","numeric-id":1839249,"id":"Q1839249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$A771935B-94F8-4D99-95D6-80A6FCB69B5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76b7c00d3d50c3cdcc2a83c1b07ea5bd3540fb34","datavalue":{"value":{"entity-type":"item","numeric-id":760506,"id":"Q760506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$595E15D6-342A-447C-9645-0D70A6E32CBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c7d001f0e412525c64f8e6185d8238753e67724","datavalue":{"value":{"entity-type":"item","numeric-id":5545521,"id":"Q5545521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$B53E32ED-3664-4578-8D31-0CC5FAF40393","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1f20790f96cd3e6513a786024cbef064a659e97","datavalue":{"value":{"entity-type":"item","numeric-id":4044553,"id":"Q4044553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791314$5929F2A7-7F48-4A98-9DD0-63F7698E4A17","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14b9ea1c41797f2c66e1109b6d2a4cd35a982504","datavalue":{"value":{"entity-type":"item","numeric-id":3026992,"id":"Q3026992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3361f08083f2a0d096e1f034711ae4fb8878ec65","datavalue":{"value":{"amount":"+0.83243727684021","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":"Q791314$8C88F0F0-0EB3-4D5E-BC4D-BA2A56F9FD12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"885b63461f656b92cd372231f1a1a4b3c2770757","datavalue":{"value":{"entity-type":"item","numeric-id":4469472,"id":"Q4469472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"677003c7f814e6270e60f86a4bd5a47e858d01d9","datavalue":{"value":{"amount":"+0.8246747255325317","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":"Q791314$F3087C44-5EC0-40E0-BC0F-21D916469E29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2219f99d490e36ee6e961a7eaef9ba54a453af34","datavalue":{"value":{"entity-type":"item","numeric-id":1084855,"id":"Q1084855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5aefe6799594fc1e41744d8d7a1617a3ce37bb77","datavalue":{"value":{"amount":"+0.8226837515830994","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":"Q791314$8B8797CB-AEA2-4BB6-8A5D-3D37FB3CB59B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba6ae5adfff606f4c874fd6335a3ef181c6fc4bd","datavalue":{"value":{"entity-type":"item","numeric-id":910850,"id":"Q910850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbd9e276ddaa1bd2a11c9ce82a2b9c483c8e4a12","datavalue":{"value":{"amount":"+0.8187147378921509","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":"Q791314$F7125501-BDB9-432A-865F-0496AA35B7F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbae16996234fe772f459f71d7a60330184ccf0e","datavalue":{"value":{"entity-type":"item","numeric-id":1357103,"id":"Q1357103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2f3f648c24cff99376b0a7ea38923e22d27afcd","datavalue":{"value":{"amount":"+0.8161081671714783","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":"Q791314$58FC163B-80E9-4312-80C0-B7C3E33A67A3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Finite complete rewriting systems and the complexity of word problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Finite_complete_rewriting_systems_and_the_complexity_of_word_problem"}}}}}