{"entities":{"Q797574":{"pageid":799422,"ns":120,"title":"Item:Q797574","lastrevid":42698380,"modified":"2025-07-08T14:32:43Z","type":"item","id":"Q797574","labels":{"en":{"language":"en","value":"The undecidability of the preperfectness of Thue systems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3867308"}},"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":"Q797574$A974856A-7618-4278-B230-D5BFA3C3287D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2581c3014c3a27c98bb39f0f5e466ed4b73603a8","datavalue":{"value":{"text":"The undecidability of the preperfectness of Thue systems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q797574$0392DB32-5330-4A5F-BAAF-5B3B8786C4FE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"465b56cba2159060e12cc6b8ce776deb706837ac","datavalue":{"value":"0545.03022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797574$E6E50663-5144-4D96-9209-6B3E26C7FC84","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ca153a48fd74d7677aae770e14522f847a4f5bbd","datavalue":{"value":"10.1016/0304-3975(84)90133-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797574$65CAF7E8-1EDB-47E7-84EF-BB828B922920","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":"Q797574$3F375B08-43F3-49B9-8C44-68D4FE1FAF51","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":"Q797574$93F8987C-4F97-4D6D-AEA4-0D1E25EA441D","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":"Q797574$3E66ED14-843E-4EAD-9FE5-13C830C25DBF","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":"Q797574$99A15DAE-6D2E-42C0-8BD5-38BE67BEF9F1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7d9f85aeeec3e4097129e15484fa872fae936350","datavalue":{"value":"Thue systems are string replacement systems that present monoids. Since the word problem for them was proved to be undecidable by Post and Markov in the 1940's, there has been some interest in developing conditions under which the word problem is decidable. A hierarchy of three has been defined: Church-Rosser systems are properly included in almost-confluent systems, which are properly included in preperfect systems. At present it is possible to decide whether a finite Thue system is almost-confluent or Church-Rosser, but testing for preperfectness has been an open problem for years. Here we prove that it is undecidable, by reducing it to the emptiness problem for deterministic linear-bounded automata (DLBA's).","type":"string"},"datatype":"string"},"type":"statement","id":"Q797574$CA6D9E16-952C-4964-B8A3-8340BA40AF89","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"21699a423435669f291d1bd1ba3da28fa1465b3f","datavalue":{"value":"03D03","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797574$01B27821-F8A4-4109-93A2-49E8CE65D399","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a27f9f06d965be24ec50f61065e06d2029a566a7","datavalue":{"value":"03D35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797574$87BE58AD-7D5A-4D21-96A7-D9D4A1AC7183","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c270fb88a62fde738bd530246c5ba57a005a4efd","datavalue":{"value":"03D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797574$47580793-7564-40BA-85E9-24447E89D5A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79c9a014785e41c94f76c463174af5cf2a59ec70","datavalue":{"value":"03D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797574$459BE57F-6215-4025-9D17-CF084401DE04","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b538ef04e3e91afc30fd1c80dc8d5f9f1236835b","datavalue":{"value":"3867308","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797574$DE50FAFD-A748-48DD-AFEE-60808C7C5914","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"872431b5dc755bcd5b7213492e1cb5e11885541c","datavalue":{"value":"Thue systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q797574$3C2F9FE6-8A75-45E6-947E-F83FB34B944D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"14a7ab210e71eff2ee2c83126e9378df29c9cad5","datavalue":{"value":"string replacement systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q797574$7ED63C27-D8CD-43B1-92C0-6E288DF51D90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c0206b3ce899f46214672b76de6b4000dbeb8f6f","datavalue":{"value":"monoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q797574$893B3FF0-FA86-45F2-8967-EF7E6C754450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6dbf42bc269958acea2d313f6db5c034566a53b","datavalue":{"value":"Church-Rosser systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q797574$2C1624F9-0399-4AFD-BE9D-A0B7D52475AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdabddeaaf221cdccc702a6afed808613b275882","datavalue":{"value":"almost-confluent systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q797574$AB6D737E-D2A0-460B-A967-B9A5932889A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"57220ad534f5818ce9114c76f8c1e77463c7d4d7","datavalue":{"value":"preperfect systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q797574$BD26ED88-5130-4E11-896D-7B621EADDA73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5289ddc45b66d6ec56e839b9cfc1cd14d1c4c748","datavalue":{"value":"emptiness problem for deterministic linear-bounded automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q797574$4E75BB0E-07FB-4D2F-9DBC-AFA362688260","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":"Q797574$9B7E8CC3-0E51-4BE1-80D0-EDF3E5B78A8E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e5e0d5a6c85501429f0e38644f5fb8f6b75ce80d","datavalue":{"value":"https://doi.org/10.1016/0304-3975(84)90133-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q797574$87FD0B30-15F0-4DEC-ACE7-0229753B125D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e2edacacf7edb422f9a55cafd35aa44da76bc281","datavalue":{"value":"W2027868924","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797574$56DBB2BE-EDDA-41D0-A168-7FC23F8CFE62","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":"Q797574$D839B636-3B99-43AA-810B-D9D1C76463B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e93f3c3eb08a198e5f96969567b686a9be61b15d","datavalue":{"value":{"entity-type":"item","numeric-id":798317,"id":"Q798317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q797574$B3D443EB-9CCD-48E6-81F4-6789E2ED1489","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":"Q797574$89BD58E7-98BB-4E38-85F4-F38CBBE01088","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f3bce65c153f53b67aafc08e73839b95059249d","datavalue":{"value":{"entity-type":"item","numeric-id":2545845,"id":"Q2545845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q797574$F16FF6D9-2A67-4F45-80E9-23E2E9F1C3B5","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":"Q797574$BEFE498A-0D7E-4D27-969C-C03A6ABBA5D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3c6d07dd80de4de8f6f1d51aa5d78e790a6fd51","datavalue":{"value":{"entity-type":"item","numeric-id":5812175,"id":"Q5812175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q797574$4A26614C-61B1-422C-8B7C-9C10437C37F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e146e1a73572c015ee99d18dfefc4f34fddc2d1c","datavalue":{"value":{"entity-type":"item","numeric-id":1839248,"id":"Q1839248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q797574$889AFD24-44D5-4ABF-98C7-F8B8A89F5AE3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b8bd24495c20392962007a1cc71102b097a2c9e","datavalue":{"value":{"entity-type":"item","numeric-id":1107523,"id":"Q1107523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06b29e017727afd2e0ade350d66ef9c178924b5a","datavalue":{"value":{"amount":"+0.91554064","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q797574$EA328006-6F91-4C51-93CF-5F2167CCAE5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed1ec2dff25dac97acd5fe3d2a3f4ee951e71222","datavalue":{"value":{"entity-type":"item","numeric-id":1092041,"id":"Q1092041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7aecb6d80e741f6f04407848df5c6b2175a7e8d6","datavalue":{"value":{"amount":"+0.9025523","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q797574$9011216D-39C1-42C8-81F5-BA0D204E7E8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc807f417615fd0288d8269779e7194b77263fcb","datavalue":{"value":{"entity-type":"item","numeric-id":1057264,"id":"Q1057264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21b8f13d00a558c3e2696a013270fe8a49a3c87d","datavalue":{"value":{"amount":"+0.8863608","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q797574$66228D35-7CE3-464A-B042-5A32E870BA0F","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":"86020f2f2f0adf3a6bae2f7bfef39d38080d740a","datavalue":{"value":{"amount":"+0.88072586","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q797574$72245770-2387-4128-A7F7-104EA0559083","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f92ccbc49632ca8cad828d551599de73d0d4e93","datavalue":{"value":{"entity-type":"item","numeric-id":1938620,"id":"Q1938620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1768f11cfc9affe16371d0b57b31e47b2b4b534b","datavalue":{"value":{"amount":"+0.86674505","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q797574$670F3BA9-0942-45EE-B991-F0F4E0DDF172","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc80a4ae50bef582575d18896abb0ad7b5457771","datavalue":{"value":{"entity-type":"item","numeric-id":3138021,"id":"Q3138021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1581ab58667d39dc15238c5011e05763eeeef1a9","datavalue":{"value":{"amount":"+0.86186254","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q797574$E1324C91-E78F-4A0D-98A8-7BB7D87938BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8bb001512014a8546eb723f44ac77c4be954100a","datavalue":{"value":{"entity-type":"item","numeric-id":1176199,"id":"Q1176199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06fbd4c7d3f449967474b19374dff30f0ac57099","datavalue":{"value":{"amount":"+0.85643715","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q797574$AD9B7F47-A0DF-4B98-8091-3A082496CE87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db44f78501a5f07622fad5ae086e37e833a17280","datavalue":{"value":{"entity-type":"item","numeric-id":5752558,"id":"Q5752558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0126f05fe097d9842a80f68bad1fb56061aae1dd","datavalue":{"value":{"amount":"+0.8558996","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q797574$CFB79F2A-9C4A-4174-8336-7ABC763ED256","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8ac95a9e12fb5e027b8c97f8b76dc58a263adfd","datavalue":{"value":{"entity-type":"item","numeric-id":1073016,"id":"Q1073016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdaa72061b76f885f1b6a920c6f8caeb7c328d66","datavalue":{"value":{"amount":"+0.8558551","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q797574$D59A4816-CE4C-4D6E-BB66-2788D7100D89","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:797574","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:797574"}}}}}