{"entities":{"Q1107523":{"pageid":1118272,"ns":120,"title":"Item:Q1107523","lastrevid":69659367,"modified":"2026-04-13T08:31:32Z","type":"item","id":"Q1107523","labels":{"en":{"language":"en","value":"Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4064974"}},"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":"Q1107523$6B590CC4-8B68-4B38-BF0F-A7B6E2273AAF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"272489c283406eb80abffbcff13df12833847066","datavalue":{"value":{"text":"Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1107523$F1D46D53-C446-4897-B08C-CAA45D67650C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"202dce8f6c5e0c2705a7919d06286d095654e90d","datavalue":{"value":"0653.03026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107523$14529D1C-9ECA-437C-A7BE-BE0166C8C8CF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8ad8e95540e65eec12f4fc89fdbb511967746ff7","datavalue":{"value":"10.1016/0020-0190(88)90049-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107523$EEDCEDC8-D394-4F8E-989A-62EF2BF169B1","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":"Q1107523$D3D58812-F392-4373-8ED9-FC6956CBF52E","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":"Q1107523$19E53BA5-8B15-4A8F-B9EB-628DBA705F5E","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":"Q1107523$32D45A98-9991-4660-82C9-85A6E7D8671A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1107523$BC557A7E-932E-44A5-A47F-271861782832","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3ab37722f968027881d9349c04fed189280a9dda","datavalue":{"value":"As shown by \\textit{P. Narendran} and \\textit{R. McNaughton} [Theor. Comput. Sci. 31, 165-174 (1984; Zbl 0545.03022)] it is undecidable in general whether a finite Thue system is preperfect. Here it is shown that this problem remains undecidable even if the Thue systems under consideration contain only left-reducing rules plus a single length-preserving rule, which is a commutation rule of the form (ab,ba), where a and b are distinct letters. In particular, this implies that it is undecidable in general whether or not a finite Thue system containing only length- reducing rules is confluent modulo a partial commutativity relation.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107523$4710EDE2-281F-4930-921A-4B84ECB4B6F6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"21699a423435669f291d1bd1ba3da28fa1465b3f","datavalue":{"value":"03D03","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107523$8B2DD9AC-3100-4970-B965-DDF156AD3BA4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fd586f1a621a926ed18ba3ee6b019ff5d2fedf57","datavalue":{"value":"4064974","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107523$1C19390E-20A8-464D-A33F-20F5677388E5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48fe5da30f2000a910dd1a06f280ea2b3174328d","datavalue":{"value":"decidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107523$9C95DF6F-1AEC-43F8-ACF6-DED3B296225D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"121d3cd06600b0c796ffebf43959f5eb0036e791","datavalue":{"value":"Thue system","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107523$4D6EAA3D-6BA2-4764-92D9-8B4DFCCFDFE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13eac0175cd03485d63d9a94c70d6019077d34f9","datavalue":{"value":"preperfectness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107523$985A11A5-5543-4AF3-B9D5-6D65E6A86AB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"28cbe0277df63e29d825f0b09933d81365fde5c7","datavalue":{"value":"confluence modulo partial commutativity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107523$149DFD3A-B6BE-4946-AC9D-A2EB059ACD01","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cfcba2434c13a2d25584bf0bd97f2fba9d024dac","datavalue":{"value":{"entity-type":"item","numeric-id":815958,"id":"Q815958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107523$22ADEEB6-A75C-4603-9CB1-CBB5711B4038","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":"Q1107523$D3E6BAF0-46DA-4336-BE6B-A71859380E7F","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":"Q1107523$A1B93DE7-89AD-4C29-B08F-1A6C3EDF82D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98f33dfd04221b8d0cebf7c9cffc1e785b2297c4","datavalue":{"value":{"entity-type":"item","numeric-id":3939790,"id":"Q3939790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107523$CA295689-CA1F-446D-8062-F5B2F4D6A4D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e947664dc494a808b8d6cd2c56ed3d1b82c197fa","datavalue":{"value":{"entity-type":"item","numeric-id":1102124,"id":"Q1102124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107523$A88BFCC9-5EF5-42C8-BE12-F9AB40938C72","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":"Q1107523$46A764E5-1959-454D-BDBC-DDD4DC4F2B09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1765649f9cd7d78b6e2077ca88e55caaa496b93e","datavalue":{"value":{"entity-type":"item","numeric-id":3771597,"id":"Q3771597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107523$45377753-031E-4CB4-9D8D-2EBB5B71A9A5","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":"Q1107523$B62A89BD-1E16-4948-9944-BB8CE763C39E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"849241baa6b3c56591969b2586e51dae90f667cf","datavalue":{"value":{"entity-type":"item","numeric-id":3816048,"id":"Q3816048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107523$ECC4D16F-F91F-4C66-9055-023AD7524FF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4296a0f1102f265d68e6fe28f366c2c858446fd8","datavalue":{"value":{"entity-type":"item","numeric-id":1057263,"id":"Q1057263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107523$79769CFB-28AB-4504-8859-F78367663D89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e54b2bb0ead9149617d0c18f40eedd98f0e33c3","datavalue":{"value":{"entity-type":"item","numeric-id":797574,"id":"Q797574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107523$857E7F13-A566-4F5A-AC9A-2F73E31C14CA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e3a7667419516b06ff7249c68623bfb991ee4c1","datavalue":{"value":{"entity-type":"item","numeric-id":797574,"id":"Q797574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0bbf200ca20c70a9fed5cc55a7dc1055341a4fe5","datavalue":{"value":{"amount":"+0.8866398334503174","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":"Q1107523$AD455E05-A1A2-4B14-A24F-1780E3129314","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":"5d9cd6c5c7bd96e4bbadf2068785499923898e61","datavalue":{"value":{"amount":"+0.8100613951683044","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":"Q1107523$73A54E0F-4662-4C36-B40A-2CB64AD5CF3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d52969ea1e81fc7bc56326da841ac5dc3c3f2ad","datavalue":{"value":{"entity-type":"item","numeric-id":673625,"id":"Q673625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed8324c79b02c9a861f166cbd216dbb13cd66478","datavalue":{"value":{"amount":"+0.7855644226074219","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":"Q1107523$83F7B154-778D-4075-92E0-BF2098EDC565","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8de1216cf85068e80b9769616645c45e831dfcb6","datavalue":{"value":{"entity-type":"item","numeric-id":4310327,"id":"Q4310327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82660d411dfdd2e8b3ad014135535b494c98074a","datavalue":{"value":{"amount":"+0.7775388360023499","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":"Q1107523$C1A929F2-9FD7-49B4-A9F0-A64E9463B3DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"728a757175c1a9516f46cea78e27e9b6ec66ba75","datavalue":{"value":{"entity-type":"item","numeric-id":1087011,"id":"Q1087011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b1f27ce6898e10df7ea2994f06bbcd69c6bbbc4","datavalue":{"value":{"amount":"+0.7767977714538574","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":"Q1107523$9C38FCFE-D3DB-40D0-90B2-8188B5FDD7FC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Preperfectness_is_undecidable_for_Thue_systems_containing_only_length-_reducing_rules_and_a_single_commutation_rule"}}}}}