{"entities":{"Q1819932":{"pageid":1830674,"ns":120,"title":"Item:Q1819932","lastrevid":69402324,"modified":"2026-04-13T06:45:51Z","type":"item","id":"Q1819932","labels":{"en":{"language":"en","value":"On the descriptive power of term rewriting systems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3995050"}},"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":"Q1819932$AB13A425-7F3D-4A44-83CC-233B3E0C57E6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f90bf86fda3bb5b6a0c8f154146115ebe4082592","datavalue":{"value":{"text":"On the descriptive power of term rewriting systems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1819932$B6B31788-A790-4A1B-9F3A-D716AB537A03","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5aeb2f72d7f29dac5bbc734f0ab1a4d2031b8083","datavalue":{"value":"0614.68032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819932$1D4D3A5A-E88A-4C41-963E-02333873C25B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2477a2f32971d044505c34b6efd4a0dcf05485ec","datavalue":{"value":"10.1016/S0747-7171(86)80017-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819932$81241792-D702-4D64-B504-B8FF6D003312","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca21ff7d743cf6b0902f40630f2a6ab3da1a616c","datavalue":{"value":{"entity-type":"item","numeric-id":174769,"id":"Q174769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819932$9851C356-5D68-4E33-AA2D-D1BB77623D7D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea72303f92787da89554ee5fa15621068821a762","datavalue":{"value":{"entity-type":"item","numeric-id":99061,"id":"Q99061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819932$73DD7EAE-5287-4464-9761-C532377509C9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1819932$9B41BF0B-18D4-42FD-BEEF-BF9068E216EE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3acdd094d78af8be3ea9c9cb07d8a54cb9deee69","datavalue":{"value":"The paper discusses the descriptive power of term rewriting systems in the following sense: Let T be the set of terms over a fixed signature. The pair (\\(\\sim,N)\\), where \\(\\sim\\) is a congruence on T and N is a set of representatives for \\(\\sim\\), is said to be definable by a term rewriting system (TRS) R if \\(\\sim\\) is the congruence generated by R and N is the set of R-normal forms. The paper gives necessary and sufficient conditions on (\\(\\sim,N)\\) to be definable by a - possibly infinite - TRS. It turns out that (\\(\\sim,N)\\) may be definable by a TRS but not by a uniquely terminating (i.e. complete) one. So the descriptive power of weakly uniquely terminating TRSs (i.e. infinite derivation sequences may exist) is strictly greater than that of uniquely terminating ones. In order to find a minimal TRS defining (\\(\\sim,N)\\) the reduced TRS R for (\\(\\sim,N)\\) is introduced. It may fail to define (\\(\\sim,N)\\), but if every term has an R-normal form then R is a minimal TRS defining (\\(\\sim,N)\\). For string rewriting systems (\\(\\sim,N)\\) is definable by a SRS iff N is subword-closed. The conjecture that every such (\\(\\sim,N)\\) is definable by a uniquely terminating SRS is disproved.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819932$3FE93A1A-CBD4-4824-989C-4048B27E4496","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819932$92C411AF-A5A8-4F94-9458-EFEF24C24964","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"092d9a7dfbbaaa84ba458f8d83190fce94c9aa54","datavalue":{"value":"68Q65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819932$82870328-53E0-4A4B-A5E7-368496E302E1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"98f244a3c605456c720ef541480c545e5905b7f0","datavalue":{"value":"3995050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819932$0856F5BB-E4AC-46F2-80EA-4536C800A86C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe94f685a7ff0c48b5d608045acf908bae99a188","datavalue":{"value":"descriptive power of term rewriting systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819932$2C269022-7127-4AF3-9862-4960403B9D20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ae56fc627e36c80644a749f0f194a2a9784098a","datavalue":{"value":"string rewriting systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819932$5D977CD4-F1D0-4E46-83A0-D87B33A11CDC","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":"Q1819932$CE6BAF33-DE46-4689-990C-9604B6E4BA44","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"954424d38b0084062ecb04ce2fedd4da29a556c1","datavalue":{"value":{"entity-type":"item","numeric-id":3957939,"id":"Q3957939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819932$840229ED-E680-4724-BB25-684F19034124","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":"Q1819932$CEF7C1F6-357B-49A1-870D-5A9EFFA8C2CF","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":"Q1819932$72F73C92-FF5E-4012-83AC-42F40E518A8C","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":"Q1819932$2DFBC54B-D609-44C1-B5EF-101B190E6128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8670a1cb5138f59a7607a06c6c33e9eef7f2c9ea","datavalue":{"value":{"entity-type":"item","numeric-id":3938536,"id":"Q3938536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819932$6957192B-72A2-4BB6-B012-944B9EEFD4FE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba6ae5adfff606f4c874fd6335a3ef181c6fc4bd","datavalue":{"value":{"entity-type":"item","numeric-id":910850,"id":"Q910850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d15c7d3274cd4c800b07c833d1238b6c64c9c8e","datavalue":{"value":{"amount":"+0.9171619","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":"Q1819932$677A71A3-A779-4D7D-A82D-748F18104506","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e5073862a29f2c508fd4cd4072bc975a4b64607","datavalue":{"value":{"entity-type":"item","numeric-id":3757892,"id":"Q3757892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2fa66fc5b502477d3275adeab3043e7e657d0e71","datavalue":{"value":{"amount":"+0.9089123","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":"Q1819932$BE099422-BCF8-43C2-8F98-7EC9269CF48B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53fa858d8c83e041662670d67f4070c5fa01ebd4","datavalue":{"value":{"entity-type":"item","numeric-id":4364373,"id":"Q4364373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a859ec89f29cee6af51f110e9fe50dd0414c86b","datavalue":{"value":{"amount":"+0.90354466","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":"Q1819932$C011BBA0-7848-4EA9-85BE-C1C16B4BDE92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0beca14a5742b40438401972bbc9993097605816","datavalue":{"value":{"entity-type":"item","numeric-id":4376886,"id":"Q4376886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67f97d9cc9c3cd8834581bdcd2752896f1a72be5","datavalue":{"value":{"amount":"+0.9030061","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":"Q1819932$7098FB90-E870-48D8-9A77-935A234DA9E8","rank":"normal"},{"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":"62eb75119ea9ddb5c55bb721400dfccf074595d6","datavalue":{"value":{"amount":"+0.89967805","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":"Q1819932$1FADB672-2404-4D30-B306-BACA3A6C4708","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a9ef0c0a23baebfb6aff4039a40956035a32b8e","datavalue":{"value":{"entity-type":"item","numeric-id":5308463,"id":"Q5308463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dbc1e178db35dbaaec4b68a94e687c73703096b","datavalue":{"value":{"amount":"+0.8979152","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":"Q1819932$295AC832-6D3C-48B8-918B-7688EB283C9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47103bcb5cfe5161b4b8ed30e71ea66eb1ee3a6e","datavalue":{"value":{"entity-type":"item","numeric-id":5313795,"id":"Q5313795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"973944dce5a9d8c487f009a25fb4977306aed7f6","datavalue":{"value":{"amount":"+0.8972959","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":"Q1819932$50333330-6D8D-4237-97B4-268FA87550C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"094b56ecfa17507306c21215ee4485798f2d6e66","datavalue":{"value":{"entity-type":"item","numeric-id":3817590,"id":"Q3817590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e60b4e36066f601657fba026228d50bdd678b311","datavalue":{"value":{"amount":"+0.8967726","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":"Q1819932$8D6E4CD3-DF1C-4594-B832-B8DBD9FC8A72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0cb4c115a27c54e7c463bd6207da05fe042a7640","datavalue":{"value":{"entity-type":"item","numeric-id":4038704,"id":"Q4038704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea23e3e70bd5ad22553ca51f60b787519947502d","datavalue":{"value":{"amount":"+0.89267975","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":"Q1819932$A6CBB1BB-1D48-475F-8AC9-A3B3421B8C9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebb9888aac49fca20e557ba55d9fe21cf06b3e7b","datavalue":{"value":{"entity-type":"item","numeric-id":2778880,"id":"Q2778880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc6a00caa67ebda15cbdb1e97617f383bcafe3c7","datavalue":{"value":{"amount":"+0.8910958","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":"Q1819932$223113B9-A341-4967-A222-3CD9A6DD54C3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the descriptive power of term rewriting systems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_descriptive_power_of_term_rewriting_systems"}}}}}