{"entities":{"Q5941203":{"pageid":8118005,"ns":120,"title":"Item:Q5941203","lastrevid":47658577,"modified":"2026-01-02T08:54:01Z","type":"item","id":"Q5941203","labels":{"en":{"language":"en","value":"On interreduction of semi-complete term rewriting systems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1635368"}},"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":"Q5941203$1F9C60AD-1197-43FC-89AF-494B7BDCA398","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"34907ef959ec5bc7fcc52866c777ea6da58777a8","datavalue":{"value":{"text":"On interreduction of semi-complete term rewriting systems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5941203$F6200F56-A5CC-44E6-9E3D-5E727470D3DB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9353544d401b552cf6c88976deee368fac096528","datavalue":{"value":"0974.68079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941203$51436DCC-B787-4733-BF77-2AA81BC9DDAD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c1ef2d4cf90873461c4b0c7b6f2af09fbc90c249","datavalue":{"value":"10.1016/S0304-3975(00)00030-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941203$B30970CB-3EB5-4F0C-8309-9A3F5CED4178","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ebd62929982c5bab719524b29f6af40450c0159d","datavalue":{"value":{"entity-type":"item","numeric-id":671505,"id":"Q671505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941203$574979B1-A6B4-4F6B-8380-D98C824BD666","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":"Q5941203$DCC0079F-1050-4567-A332-D418885E11E8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0d780905acb67c2b1b938af03e08b68df411214b","datavalue":{"value":{"time":"+2001-08-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5941203$EF425CD3-56CE-4426-B197-64B029E68F1E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ae724e052be9afe969e465ac3173ce7cc5e88f22","datavalue":{"value":"For a complete, i.e., confluent and terminating Term Rewriting System (TRS) it is well-known that simplification (also called interreduction) into an equivalent canonical, i.e., complete and interreduced TRS is easily possible. This can be achieved by first normalizing all right-hand sides of the TRS and then deleting all rules with a reducible left-hand side. Here we investigate the logical and operational preservation properties of the same simplification operations for semi-complete, i.e., confluent and weakly terminating TRSs. Surprisingly, it turns out that for semi-complete TRSs these simplifications are neither operationally harmless nor logically correct: Semi-completeness may get lost and the induced equational theory need not be preserved. We also provide sufficient criteria for the preservation of semi-completeness and of the induced equational theory. In particular, we show that orthogonal TRSs enjoy all these preservation properties. In the general case, for a given semi-complete TRS an equivalent semi-canonical, i.e., semi-complete and interreduced system need not even exist.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941203$8C74FA4C-AA4D-4F63-B23A-C95E28C1AECE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941203$7D3B8423-3D70-4AAE-B55A-E0927E31AD87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941203$BF509B47-3A68-45B8-A0E3-679484F8FD50","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0696115584d1a569783eb3497bc23be8e6248476","datavalue":{"value":"1635368","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941203$4E9FF576-EFFC-456F-90F6-9E41F94A7880","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1a02b4e020864e91f8b46070c7c982fa2878da3","datavalue":{"value":"theory of computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941203$11AAAFE3-1E6C-4B4B-B76E-65F86F490B64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a664fc87eb2216b1fad976387dcf6ff589b12b5","datavalue":{"value":"term rewriting","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941203$30EE7148-0C71-4815-8192-88D5EF32B160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b38049d159af5d6c62de79db7ea882fef0c299bd","datavalue":{"value":"confluence","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941203$3E50B0A1-84EB-4C52-8FB3-1BC65D54AF8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4befa4ca20f2beabcfa09e8a92ae13c21cb4934a","datavalue":{"value":"termination","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941203$F1C63270-95DD-4909-B5AC-796A87996FBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"31e9cb40752744ec8367b55facfcbccaefab49a1","datavalue":{"value":"semi-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941203$E6BDF359-445E-4DC1-9FDD-8B764443CBCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d8d3f5ab92b720ed006e013a77a6d40dbbfe96b","datavalue":{"value":"right-normalization","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941203$69F59F4F-6BD5-4109-8BBD-B826171B0EFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"009cb170406be7ae20216323e714ed534e32b5f9","datavalue":{"value":"interreduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941203$85E493DC-2562-477A-A79C-190C14970BD2","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":"Q5941203$431FF811-C2BB-4AE6-8947-F9053453EC58","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f463d2fc68b751147d657b7d88f441cdf392409","datavalue":{"value":{"entity-type":"item","numeric-id":4000281,"id":"Q4000281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941203$C607A0AE-FEFA-4E54-9214-FE32AF48EC6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c525319ed7a0622a258a9434358c0414c7f08540","datavalue":{"value":{"entity-type":"item","numeric-id":4846257,"id":"Q4846257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941203$C10324BC-55DA-472F-BA24-D34D442527AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a01d4a91dcf05e247efe3d36d8b1cf5c4792f88","datavalue":{"value":{"entity-type":"item","numeric-id":4385532,"id":"Q4385532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941203$E92E910E-A680-43AD-9584-10E92357FFDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce85daf6ad363841c9c10c0d5c7403f58e8278c6","datavalue":{"value":{"entity-type":"item","numeric-id":5055812,"id":"Q5055812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941203$2A9231AE-1A1D-49E3-BB5D-5DB318AD6F70","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":"Q5941203$3517A4AD-9A03-4462-BA71-C13745438508","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7dd076536f3668f703f8f8e17b2cfee8106654e","datavalue":{"value":{"entity-type":"item","numeric-id":1154801,"id":"Q1154801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941203$B21368F0-9EF0-472A-A1D4-CB3954636AD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb04a3e1f7c2b128c194cbd9b09444095a7d8839","datavalue":{"value":{"entity-type":"item","numeric-id":4023825,"id":"Q4023825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941203$13D7065F-51E4-486B-B118-CC9F0C7C7049","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c955b55aa93e4322e27fdf7cf9c017b56661300b","datavalue":{"value":{"entity-type":"item","numeric-id":1117204,"id":"Q1117204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941203$5C6574F3-F05F-4EEE-8FBF-7A8B4CD1375B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1e0b4fc54e8c62a86959e50d4b1b27d9d9a092c","datavalue":{"value":{"entity-type":"item","numeric-id":5581665,"id":"Q5581665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941203$93808E45-3E84-4C77-B214-0F4411B52D06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f029f25ce66f1e8b3294e6cdf267f00f417ca7c2","datavalue":{"value":{"entity-type":"item","numeric-id":1836978,"id":"Q1836978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941203$145DF07A-8FCA-4C05-95A8-6BD1D2BB0C11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2202ea6b7a5f8b2bf37b129e53958a44d2d21d02","datavalue":{"value":{"entity-type":"item","numeric-id":1133323,"id":"Q1133323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941203$3974B80D-DAC3-4290-9B9C-C8B5E4930C46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54d5ead1bf938a8db255d60f48db40087ed47d98","datavalue":{"value":{"entity-type":"item","numeric-id":1294616,"id":"Q1294616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941203$8D7A55F8-1F8F-4A7D-BA7F-F3D114F66BD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"212a413d72385fbce7e63ede411ad18800925449","datavalue":{"value":{"entity-type":"item","numeric-id":4501166,"id":"Q4501166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941203$FCB7189D-9C35-460D-9FA6-6185CEBBAFFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8533cf00ebc930b9b782e1fc7f8971f87db31c20","datavalue":{"value":{"entity-type":"item","numeric-id":5684229,"id":"Q5684229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941203$63CB50F1-D587-4824-B997-328A12447DDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d25c898898b618a08f301331a46c4d1e466a4aef","datavalue":{"value":{"entity-type":"item","numeric-id":582270,"id":"Q582270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941203$D8181F40-9F16-42C3-A982-BF10716968BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fa703a3567d0034a8a5c9d58b556309ae4271aa","datavalue":{"value":{"entity-type":"item","numeric-id":689097,"id":"Q689097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941203$9ACA753B-0B57-4B41-8290-0CE700ECBBA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"776ab2ff945c52396f6e0d21fa9758c667df50b2","datavalue":{"value":{"entity-type":"item","numeric-id":5503212,"id":"Q5503212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941203$FCD49B3C-5EC8-41E9-B57A-B413280B275D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"130aa93c622f03ef50a7d5b09fe05904ae116d29","datavalue":{"value":{"entity-type":"item","numeric-id":4937190,"id":"Q4937190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941203$6F7BE539-DBD5-435F-AF0A-51F73C6764F8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83cc65cdf2044d1a4d927398a719f7ab76181f0a","datavalue":{"value":{"entity-type":"item","numeric-id":1077161,"id":"Q1077161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76bbd5603ee906fe119c11f7e5cb82dcbb1befa9","datavalue":{"value":{"amount":"+0.7808302044868469","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":"Q5941203$20942FC0-BA64-4F05-88D4-674895E86C66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11657cab5da6ccda3d74863e31abdc7ede599c07","datavalue":{"value":{"entity-type":"item","numeric-id":3820053,"id":"Q3820053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9273baecbfed3f970d6aab2c1265420ee6d81e36","datavalue":{"value":{"amount":"+0.779666006565094","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":"Q5941203$7EF5130F-398B-43E0-BD2C-6823F768D892","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50cef41e4034e4011ac63f848b7fcd73476e569e","datavalue":{"value":{"entity-type":"item","numeric-id":4369898,"id":"Q4369898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f32213cf4cf90cb0e42fd6e06878d08a9ccf6d25","datavalue":{"value":{"amount":"+0.7760957479476929","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":"Q5941203$95E7E303-1600-46CF-AEA2-07C9173A712B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef1c169f747b223fee7f66b2d56d4ee47544427d","datavalue":{"value":{"entity-type":"item","numeric-id":4037331,"id":"Q4037331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28508ead8fe5dbdacf56b312bb87b05b60c3dc8f","datavalue":{"value":{"amount":"+0.7754365801811218","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":"Q5941203$3F6B3D4C-670C-49A6-BB65-D818FE6EAFE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f9694f55ceb1d0c26ae12687b0e65341b5e766c","datavalue":{"value":{"entity-type":"item","numeric-id":5898157,"id":"Q5898157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b01137c5a7f21f4b84248fe3db4e938174821c3","datavalue":{"value":{"amount":"+0.7724055647850037","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":"Q5941203$A7ABD810-7D86-48C5-A687-7EAB4A129A2D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5941203","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5941203"}}}}}