{"entities":{"Q7361063":{"pageid":31518728,"ns":120,"title":"Item:Q7361063","lastrevid":105362552,"modified":"2026-10-07T13:34:22Z","type":"item","id":"Q7361063","labels":{"en":{"language":"en","value":"Undecidability Results on Orienting Single Rewrite Rules"}},"descriptions":{"en":{"language":"en","value":"AFP entry Orient_Rewrite_Rule_Undecidable"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f77770dc25dd0aaf46137f6d27636bf854c91fcc","datavalue":{"value":"https://isa-afp.org/entries/Orient_Rewrite_Rule_Undecidable.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361063$5E825346-F51B-4557-B2BB-988C1AE10763","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"61877e84ba989d20dbe6baf29fb8934f5cbbd9f7","datavalue":{"value":{"time":"+2024-04-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7361063$1D8CA1A6-9CFA-4955-8487-7825DCF554A5","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"3e961f1f2b2e533bd88ffdbcd178bd2ef2813f73","datavalue":{"value":"Ren\u00e9 Thiemann","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361063$448C7EBD-02A4-4A5F-99C1-91D12458E30A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"2b7b69607d193b1d42312494a69ef7dd79c036d4","datavalue":{"value":"Fabian Mitterwallner","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361063$BEE2D63A-95A9-4B91-AE60-8569B7380859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"5700dfb4f0b161bb746d6eb3f115c010f073ef4c","datavalue":{"value":"Aart Middeldorp","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361063$D3282558-142D-431F-8D92-BBC6F0905401","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"471ad634df4d3f1224df0297e02ed0a3647c8602","datavalue":{"value":{"text":"Undecidability Results on Orienting Single Rewrite Rules","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361063$6C570201-CA3F-4D48-8FD5-6006731F24F7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1ad6f4234fba4afac4e913ba00f07d0c09855c10","datavalue":{"value":"We formalize several undecidability results on termination for one-rule term rewrite systems by means of simple reductions from Hilbert's 10th problem. To be more precise, for a class \\(C\\) of reduction orders, we consider the question for a given rewrite rule \\(\\ell \\to r\\), whether there is some reduction order \\({\\succ} \\in C\\) such that \\(\\ell \\succ r\\). We include undecidability results for each of the following classes \\(C\\): the class of linear polynomial interpretations over the natural numbers, the class of linear polynomial interpretations over the natural numbers in the weakly monotone setting, the class of Knuth\u2013Bendix orders with subterm coefficients , the class of non-linear polynomial interpretations over the natural numbers, and the class of non-linear polynomial interpretations over the rational and real numbers.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361063$5A36802C-ED5D-4581-B99A-E8DF52E9A0CE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c059d1355bcb0df592c7e924663d48f24f3b387e","datavalue":{"value":{"entity-type":"item","numeric-id":5613949,"id":"Q5613949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361063$E7FA15DD-23D0-46BE-8BBB-E62380DF6F5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b5c6a4af60557a1aad77de19fe05d07f4151219","datavalue":{"value":{"entity-type":"item","numeric-id":6970215,"id":"Q6970215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361063$F22EA778-1262-4043-9693-0A3D91293D5D","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361063$92EA01C2-A2EF-4D14-9EA1-EFCCB52EE8E1","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"cae84e801e061aec7176e0448420881931a4580c","datavalue":{"value":{"entity-type":"item","numeric-id":7361482,"id":"Q7361482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361063$08D20240-9F2F-4490-85E5-83EAAEC8EBCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"6d228da4bce2fba997fec5a975b2ba853633b29e","datavalue":{"value":{"entity-type":"item","numeric-id":7361840,"id":"Q7361840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361063$25C6D310-9CBB-41DC-AB3C-36A6DF372DC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"5d2b901a95ee4a9674d7709b6eab726a2a838e0f","datavalue":{"value":{"entity-type":"item","numeric-id":7361077,"id":"Q7361077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361063$FAFABA44-8858-4320-96D4-F7262A1A2DED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"3083b28cc1bd9860f5bb551df5db6c97e7a4c0c4","datavalue":{"value":{"entity-type":"item","numeric-id":7361593,"id":"Q7361593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361063$DFC81AD9-5379-4777-B56F-7E758B203E22","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"edf8a8949edec3767dd80b6d3acecc92e5d25f1c","datavalue":{"value":{"entity-type":"item","numeric-id":7360818,"id":"Q7360818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361063$4F394A75-E473-46FF-90D4-01C8B5BD26B3","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361063$9540E17A-3BBC-4F42-81AA-B726F9E6CFF5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Undecidability Results on Orienting Single Rewrite Rules","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Undecidability_Results_on_Orienting_Single_Rewrite_Rules"}}}}}