{"entities":{"Q734041":{"pageid":735890,"ns":120,"title":"Item:Q734041","lastrevid":63993651,"modified":"2026-04-11T16:56:07Z","type":"item","id":"Q734041","labels":{"en":{"language":"en","value":"Undecidable properties of flat term rewrite systems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5617928"}},"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":"Q734041$D1E9E863-F2F4-4DF4-9F3F-B8050C03E176","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d35e67cb45fc3d253d658f857736889c9fc3f044","datavalue":{"value":{"text":"Undecidable properties of flat term rewrite systems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q734041$AB5A0362-CD8F-4497-AB4D-2AF33B3C9BC1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e8a5f7ac4967c02e4bf68cf81625ce2960f46ce2","datavalue":{"value":"1187.68274","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q734041$C9196630-7F2C-45CF-86B7-54D29C71A15B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"957322e0e65309e69a1881e776e7b58b540ff033","datavalue":{"value":{"entity-type":"item","numeric-id":734040,"id":"Q734040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q734041$4086D1F4-CBB2-4C41-A109-CBBC69C78FCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"905ccb078108ec3e5ff534405172f896420ef05b","datavalue":{"value":{"entity-type":"item","numeric-id":356390,"id":"Q356390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q734041$D01B319B-8BD5-49EE-B99E-9663DCCD494C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e71b1a810c94176f33b214acd409208085d409e4","datavalue":{"value":{"entity-type":"item","numeric-id":162945,"id":"Q162945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q734041$C26FEDED-B48A-4541-A538-518C4EB81B4E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bd476ebbd61c1948a69e599e82439aa1b933a98f","datavalue":{"value":{"time":"+2009-10-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q734041$415771F8-785E-488A-B406-F8EED2640242","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1418dbac7bed0f9d2362d279678659a7626bf27f","datavalue":{"value":"Reachability, joinability, termination or strong normalization, confluence, weak normalization, and unique normalization are some fundamental properties of term rewrite systems (TRS) that are known to be undecidable in general. Their decidablity has been investigated for some particular classes. In this paper, the authors give new simple proofs for the undecidability of reachability, joinability, and confluence for flat TRS. They also give proofs for the undecidability of weak and unique normalizations for flat TRS.","type":"string"},"datatype":"string"},"type":"statement","id":"Q734041$0C3EBD78-C492-4517-9FEF-DAEA0193A055","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q734041$78F648A5-32E4-4764-9AD1-6BD07C2CB922","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7c0c9fe73ce0243d38e72a6c9c7519c1ab4bad05","datavalue":{"value":"5617928","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q734041$B23C3654-1858-414C-9038-84169D47C3B1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a664fc87eb2216b1fad976387dcf6ff589b12b5","datavalue":{"value":"term rewriting","type":"string"},"datatype":"string"},"type":"statement","id":"Q734041$D8348270-2F7B-4C22-BB0B-0026CAA995CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f619bfcb84c5eab168c7cd3a1b80d60faa60a04","datavalue":{"value":"syntactic restrictions","type":"string"},"datatype":"string"},"type":"statement","id":"Q734041$5E5F6544-F8B4-471C-85C1-6EF20D091AA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a813fd0e4aef1fda5e8e7d4b77b02104337d96e6","datavalue":{"value":"undecidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q734041$33E5AA73-00FF-4A6E-A00E-2F2B66CF2462","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3f9e311a53969bed982204d1446a9d77dda26ac9","datavalue":{"value":{"entity-type":"item","numeric-id":591667,"id":"Q591667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q734041$C197C6FF-A56A-4C82-A337-4511EA81A40E","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":"Q734041$5DDACF56-E2F3-4877-95D1-53BBF1E3FBA2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5dfe89f07317f42b84f8773c27a1de7fd57cb9f0","datavalue":{"value":"https://doi.org/10.1007/s00200-009-0097-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q734041$A5D9F7D4-E2E4-4D54-96A2-9AC635612A20","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"23034acabf7da20157d1fa757080bac353b1eb53","datavalue":{"value":"W2095909184","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q734041$F3B763B7-C777-4E6E-828E-19FD6580EFEE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"819a2535befb2a67f49ee5e43432525215be36de","datavalue":{"value":{"entity-type":"item","numeric-id":4702972,"id":"Q4702972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q734041$BCF42672-21C0-464A-835B-64E87A35E565","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d31d24a311564e96c97e95598f7a6ed5e21d59e3","datavalue":{"value":{"entity-type":"item","numeric-id":5432342,"id":"Q5432342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q734041$6DD67D3F-2CBA-408A-B678-FB66799781A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"842da22c1419bb2ac7a12aa45e86ebd6e6b1ba08","datavalue":{"value":{"entity-type":"item","numeric-id":3608777,"id":"Q3608777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q734041$C6D00C55-2DD2-4BC5-8A5D-E046DCBDCCFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b56fe7662535fc025568c711ed61fa5db68a7ac","datavalue":{"value":{"entity-type":"item","numeric-id":5307051,"id":"Q5307051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q734041$925F6BA4-D5DD-4B94-8FFA-E743E6472212","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"facb68a3f5c3aaa7972b89a35e2b0770a73aace7","datavalue":{"value":{"entity-type":"item","numeric-id":5394600,"id":"Q5394600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q734041$61988AF0-4289-48BD-9435-89CB637B312E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61ac4d5ab6018a1510010c37ae8dc3cec6c8ba78","datavalue":{"value":{"entity-type":"item","numeric-id":4418639,"id":"Q4418639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q734041$DA78B012-718C-4B9B-AB37-F165211A7FC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"926e1c124ce65acb98298900b42930980762fc43","datavalue":{"value":{"entity-type":"item","numeric-id":1014436,"id":"Q1014436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q734041$25D03321-957E-42FC-9E7E-C6543031D65E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f6ebe546bb22deea94d20817802960459c534e8","datavalue":{"value":{"entity-type":"item","numeric-id":5302902,"id":"Q5302902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q734041$353A2F2D-BF94-44A3-B184-8688DB71D4E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e49dd04201c59095126ace1b445dd17268a9523b","datavalue":{"value":{"entity-type":"item","numeric-id":1400714,"id":"Q1400714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q734041$4033F847-7740-4845-983D-BBF2A5683E28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea79bf0b8998e59df4aaa18289fafa2fe7f354f5","datavalue":{"value":{"entity-type":"item","numeric-id":3392275,"id":"Q3392275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q734041$FC8EF768-8632-4E55-AF20-24C8796DF680","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bde07cdcf9f119afdf8d81a4464725f1ef280c9d","datavalue":{"value":{"entity-type":"item","numeric-id":2723905,"id":"Q2723905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q734041$13CDFF80-1CAF-4760-B30E-F6BE944F7EA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a85429a98d5911d473b5c440c645ef66775e9d2","datavalue":{"value":{"entity-type":"item","numeric-id":3527306,"id":"Q3527306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q734041$B81CCF4D-0D21-474F-BCAD-C8DF0DB564F7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"692e49c18287ea1d0aec730be33cd69444b42116","datavalue":{"value":"10.1007/S00200-009-0097-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q734041$A7B71C36-0C49-4D1D-924F-DB7206DB4063","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc6b2c1645bd8130acddd4ec8cd643244e39f6b7","datavalue":{"value":{"entity-type":"item","numeric-id":1014436,"id":"Q1014436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"464088894fc339a3c674f70e4bc0a3b975b654c1","datavalue":{"value":{"amount":"+0.928441","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":"Q734041$76D7E12B-9F6D-4DEF-A391-E34F96566D18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"154a232b6e6da0785d372cafefb44b0468f34d27","datavalue":{"value":{"entity-type":"item","numeric-id":5166638,"id":"Q5166638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"825d219694554fca7b8a220c58ff7f9a38ae448d","datavalue":{"value":{"amount":"+0.9186991","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":"Q734041$C35BF6E1-E320-465F-961B-E14498AEE099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aec35960013665b110230748cbb897af20f4a1f5","datavalue":{"value":{"entity-type":"item","numeric-id":2873677,"id":"Q2873677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da9320a578492eae00e35ff142ecd67e1862d652","datavalue":{"value":{"amount":"+0.8944309","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":"Q734041$F216119E-3886-4B2F-87F9-5FDDB6586958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4f97b92586490fd2c6f65c10ae1ecca3d11b792","datavalue":{"value":{"entity-type":"item","numeric-id":4362915,"id":"Q4362915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef59892f0fcb778c949dfcf5ce3306a6f6940ce3","datavalue":{"value":{"amount":"+0.89400864","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":"Q734041$0D6D187A-29D8-4E52-9F05-42978B232772","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21827a3dc87c99c55f72e37691772912d775e438","datavalue":{"value":{"entity-type":"item","numeric-id":3644753,"id":"Q3644753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1270f341da63f8ccb814b2a17210c3f3ed78f13d","datavalue":{"value":{"amount":"+0.8823967","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":"Q734041$A6E212ED-4320-42CC-9EC0-8F412958D227","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bb035a7060f6feed65bc97b6622819fb2f93499","datavalue":{"value":{"entity-type":"item","numeric-id":1061484,"id":"Q1061484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cef47ff878a77b80a44095182c0f7dd1ca60e201","datavalue":{"value":{"amount":"+0.8787419","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":"Q734041$9DC20BF1-E7B1-4F8C-A0B2-A04D15061036","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b754178d023239cc098828c9a84fa899fd07362","datavalue":{"value":{"entity-type":"item","numeric-id":1854559,"id":"Q1854559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4cc11150c38990caceaeffb341fc7a9124c2c8f0","datavalue":{"value":{"amount":"+0.8704542","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":"Q734041$625E5A22-6D6B-48E5-81CB-3B5D45383F1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d335f8145d775bc612764758c98b47919c42e90e","datavalue":{"value":{"entity-type":"item","numeric-id":1911402,"id":"Q1911402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"156807f056d530d1abb7d17a4096d64539f23395","datavalue":{"value":{"amount":"+0.8682181","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":"Q734041$573869E3-225C-4C0E-86B7-97CBF9BDA6F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17fc89bf2f99789ced87ad22de525ca0ef816f9c","datavalue":{"value":{"entity-type":"item","numeric-id":4065053,"id":"Q4065053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0fef1bd28ef97b2092349afbfb3b966eda87c64","datavalue":{"value":{"amount":"+0.86029845","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":"Q734041$A0AC2FC2-8AE5-4392-AA0B-78F2C1053032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e796d03d85e164ac373cf0a8f6ff33b56a338662","datavalue":{"value":{"entity-type":"item","numeric-id":1341717,"id":"Q1341717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc70a428a5ba16bfae4236f9cbb7dfd075a0c2e6","datavalue":{"value":{"amount":"+0.8590523","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":"Q734041$051D80D1-31A7-4531-8441-B0150C8379BF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Undecidable properties of flat term rewrite systems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Undecidable_properties_of_flat_term_rewrite_systems"}}}}}