{"entities":{"Q1057263":{"pageid":1059111,"ns":120,"title":"Item:Q1057263","lastrevid":48800479,"modified":"2026-01-05T21:40:50Z","type":"item","id":"Q1057263","labels":{"en":{"language":"en","value":"An \\(O(| T| ^ 3)\\) algorithm for testing the Church-Rosser property of Thue systems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3896912"}},"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":"Q1057263$40CC287C-5BDF-47D2-A045-77644C163719","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dfa3abc5302264fe215dbd4d9363a7428d747814","datavalue":{"value":{"text":"An \\(O(| T| ^ 3)\\) algorithm for testing the Church-Rosser property of Thue systems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1057263$16563771-9028-45F0-88E0-0500E9194D32","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6c790af8139b23595dd4fc35b6f2c8488f76f1f6","datavalue":{"value":"0563.03018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057263$1E95472E-CE8F-4A45-B3A4-4AB775C02B1F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ca9c188d9a8676b9ff2b575d5443a5664d8e01fa","datavalue":{"value":"10.1016/0304-3975(85)90008-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057263$9355653C-8DDC-4C74-AEE4-1949963EAFB8","rank":"normal"}],"P16":[{"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":"Q1057263$F16B290F-68E9-4F7E-B622-BBB936D1CD00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7a60a38320311da18eda10821922742954865726","datavalue":{"value":{"entity-type":"item","numeric-id":394492,"id":"Q394492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057263$3EE81501-0F69-4497-8D9E-069D5BF1F838","rank":"normal"},{"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":"Q1057263$434A03EF-3384-4501-9F38-89596ED67185","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d16922eb7ed4824225f324fac9345cfe633d1fb3","datavalue":{"value":{"entity-type":"item","numeric-id":211674,"id":"Q211674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057263$EF86977E-3E9D-42CE-9898-739EBDAA18EA","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":"Q1057263$69F9937D-308E-48BC-B340-33C9631B1617","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":"Q1057263$BECB55A7-0A25-4FF1-8B45-DE0F14F1A69A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"db5ddca568342e1e6256acc3761f1ae77b4f1dec","datavalue":{"value":"\\textit{R. V. Book} and \\textit{C. P. O'Dunlaing} [Theor. Comput. Sci. 16, 223- 229 (1981; Zbl 0479.68035)] have given an algorithm of time complexity \\(O(| T|^ 6)\\) which decides whether a Thue system T is Church- Rosser or not. The present paper describes an algorithm of time complexity \\(O(| T|^ 3)\\) which answers this question, too.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1057263$1F93BE44-95B7-47E8-ADFB-92263740D983","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"21699a423435669f291d1bd1ba3da28fa1465b3f","datavalue":{"value":"03D03","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057263$AA86AA98-F0C8-4300-B5F5-2A4B5DBA4D8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057263$92EE3925-2024-49B3-BC0B-C4CA124D822D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e7aaaf0b37aa063d9f19abad35426e8e9b4a075e","datavalue":{"value":"3896912","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057263$F95C8E72-9B5C-42AF-9BF5-1DB464600C97","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e5adb2f5b9beef2201bef72e73c6f511c159db61","datavalue":{"value":{"entity-type":"item","numeric-id":493519,"id":"Q493519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057263$79AFA743-3465-4BC6-B74F-149411F235C9","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":"Q1057263$CE678DB0-43D5-4502-8B6D-8D7CE2886E0F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"350e053bf4f58ce9b3e2715e7344465f581e126b","datavalue":{"value":"https://doi.org/10.1016/0304-3975(85)90008-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1057263$744F7446-5D7D-4591-962D-9E66C51E1326","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c5d9386e7acd8aa8f5f21ac60aaa92772d96170f","datavalue":{"value":"W2080604675","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057263$96ACDA34-2175-4245-9222-CCB167C63E62","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e884892508373839ae801c95d241a499a8aaf0a5","datavalue":{"value":{"entity-type":"item","numeric-id":4055184,"id":"Q4055184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057263$CA04AE25-73F1-4B3A-A559-479075A42620","rank":"normal"},{"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":"Q1057263$C527C3CC-2491-4173-8363-7FB4A9A13D3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb713495b9ea7313f59f292ec295ea082246771a","datavalue":{"value":{"entity-type":"item","numeric-id":1162144,"id":"Q1162144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057263$9D93F1B7-467F-4F45-B755-CF45158D3A51","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":"Q1057263$FBC67384-F1C3-49BC-8F0E-D857562DF2A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d48410a7583156d1131964150b5eab11998283a","datavalue":{"value":{"entity-type":"item","numeric-id":4105657,"id":"Q4105657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057263$8DDDD694-2406-4B29-BCC4-7D14D1377A77","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a02fbca4bccb20200d05fefd3fb4db34e08fdf45","datavalue":{"value":{"entity-type":"item","numeric-id":1071759,"id":"Q1071759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7edac2f083da39af50bb5e14e6ead647ea631b33","datavalue":{"value":{"amount":"+0.9106969833374025","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":"Q1057263$1E9F43AA-5807-4A88-A3A1-473C394CDC1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d1454efb480b150a0afee282e59f9f878946610","datavalue":{"value":{"entity-type":"item","numeric-id":3778003,"id":"Q3778003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82e8b5b70d91a9ddde4a166c4a7eec6840c024a6","datavalue":{"value":{"amount":"+0.8316652774810791","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":"Q1057263$73FC1319-00B2-4C54-9451-ED03A2F6567C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d652fdf152aeddbb37949bf30540510352318d6","datavalue":{"value":{"entity-type":"item","numeric-id":1123619,"id":"Q1123619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28540217d5d34dc2751935fa144de206c1be1d44","datavalue":{"value":{"amount":"+0.8239223957061768","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":"Q1057263$905B6BA9-1398-4313-BD65-5E3DEBD29581","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f30758dc49df7f4b9e9d10b9ce54c0e60977278","datavalue":{"value":{"entity-type":"item","numeric-id":3722483,"id":"Q3722483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ef8bc1652410cd0a5b84038cf33d7a3ed3748fa","datavalue":{"value":{"amount":"+0.8063820600509644","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":"Q1057263$29B4BE64-65F9-44A3-8130-F20B1A42489A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98410aee71e8acee7749f84cd62a30d087d1d9f9","datavalue":{"value":{"entity-type":"item","numeric-id":3798271,"id":"Q3798271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d36a36cff4fed23f9b3ffa476d5ca2c2f9f5535","datavalue":{"value":{"amount":"+0.8054307699203491","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":"Q1057263$486751F9-4AFE-464C-998B-BB9FBF2754F3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1057263","badges":[]}}}}}