{"entities":{"Q3838765":{"pageid":5868670,"ns":120,"title":"Item:Q3838765","lastrevid":108373610,"modified":"2026-11-06T03:57:35Z","type":"item","id":"Q3838765","labels":{"en":{"language":"en","value":"Solving disequations modulo some class of rewrite systems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1189063"}},"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":"Q3838765$FEDDD900-9C83-45B2-8085-E0FED6AC04A2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"091577f42b02fe0b9754f135af50c523c5402ab6","datavalue":{"value":"0906.03008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3838765$8944F28D-AF18-4015-B0EB-9C4DD1904790","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a0a7d6ec5434254be6a0e1c98f710f162b50225","datavalue":{"value":{"entity-type":"item","numeric-id":877841,"id":"Q877841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3838765$8E515CBC-597D-48A2-B86B-707616563CD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fcc953e7dff7d26bdcb07d2cdf423e7bdad75f63","datavalue":{"value":{"entity-type":"item","numeric-id":1675158,"id":"Q1675158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3838765$333668F4-B5B8-42C6-B83C-D7E82C1D1FD7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"03698f5ec2670b440edc2f3fcc278ec7f9d935e2","datavalue":{"value":{"time":"+1999-02-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3838765$D7B1F833-15E6-4F5B-B35B-6FF7582D6C5C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"10eaeaf8bbf8231bbfc812aab8956e260b5a9f12","datavalue":{"value":"03B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3838765$58ABEABB-F28A-456D-B5F6-2DBFC1367C51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3838765$7BFFAFCC-9DA4-401C-8682-D9FDB6F1EA6F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9d1f2741fc5ae236104bd5d10ee9785ba08cb64a","datavalue":{"value":"1189063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3838765$A1038334-CCCF-4346-8F77-50F81460F118","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e94525ee9ddac27acf6c5c07b63dac486114f332","datavalue":{"value":"disunification","type":"string"},"datatype":"string"},"type":"statement","id":"Q3838765$5E52B763-42C3-44B2-BF0B-99141296617F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0bcf84584bad3fe3604d99501f4fec1b7404f6c2","datavalue":{"value":"E-unification","type":"string"},"datatype":"string"},"type":"statement","id":"Q3838765$E9FF3463-FE56-4ACB-BCC9-75AB8E98CCC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a664fc87eb2216b1fad976387dcf6ff589b12b5","datavalue":{"value":"term rewriting","type":"string"},"datatype":"string"},"type":"statement","id":"Q3838765$440489DC-9470-44B6-9D49-F4E65368572A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d034712004aab6f962f36b52a7a07ebb5b03551","datavalue":{"value":"tree tuple synchronised grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q3838765$ACE1CD73-3A69-4D9A-9A09-438F8B946F39","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"32dae26506ed7b7d490e6f4de337f1bbf687f144","datavalue":{"value":{"entity-type":"item","numeric-id":15552,"id":"Q15552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3838765$E3BDBA3B-3AC2-4602-BAFC-BA2DD7C5DDD7","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":"Q3838765$60146C6D-D1E5-4D95-81C4-3E4973B348CA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"681d0b71c1d176babce5cb2612de8221f951a068","datavalue":{"value":{"entity-type":"item","numeric-id":4310836,"id":"Q4310836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36c513138acf1ccb924e2897857db8e2f6ed5b5e","datavalue":{"value":{"amount":"+0.780720591545105","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":"Q3838765$64E93DEC-3BAC-411C-9442-DE3430EC6F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df0d05e3017f3ba17287c82928f9843aabc791e0","datavalue":{"value":{"entity-type":"item","numeric-id":3818292,"id":"Q3818292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"580ad1f7ac6627123e49bbc6f42e18429529623a","datavalue":{"value":{"amount":"+0.7683950066566467","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":"Q3838765$3E6948CE-1364-4E33-9F10-0131E797B3BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2cb67eb28a0ce730c6dcf90fbf8553cc26a9d994","datavalue":{"value":{"entity-type":"item","numeric-id":1197097,"id":"Q1197097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2025e8cd04965e45a612ab9d3c7318508103ecc","datavalue":{"value":{"amount":"+0.757744312286377","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":"Q3838765$C20F4163-3E12-4B4B-A395-4D2AE7C33B6B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c50d1ff1cb4e0f6ab89343638f38a839e2f70575","datavalue":{"value":{"text":"Solving disequations modulo some class of rewrite systems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3838765$9E32BA2A-E9DF-4BB4-A0EF-A0E7683E6789","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0c098155d5d003be41e0641d0e257a089b39af53","datavalue":{"value":"10.1007/BFB0052365","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3838765$6479965F-668F-4E11-93B0-05071DC23BD5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ff4dd0618d78e900019b15ad4c713b8de8b104b6","datavalue":{"value":"The authors discuss the problem of solving disequations, i.e. formulas of the form \\(s \\not= t\\) modulo a theory that is given by a set of equations \\(E\\). They show that the problem is decidable, provided the equations in \\(E\\) can be organised as a rewrite system that is both confluent and constructor based and furthermore satisfies the following restrictions: 1. The rewrite rules have to be linear. 2. If a subterm \\(r\\) of the right hand side of a rewrite rule unifies with the left hand side \\(l\\) of a rewrite rule, the most general unifier \\(\\mu\\) of \\(l\\) and \\(r\\) must be a renaming of the variables occurring in \\(l\\). 3. There may be no nested occurrences of defined function symbols on the right hand side of a rewrite rule. 4. The disequations to be solved have to be linear. The present paper is a continuation of the paper ``E-unification by means of tree tuple synchronized grammars'' [Discrete Math. Theor. Comput. Sci. 1, 69-98 (1997)], which is written by the same authors. In that paper it is shown that the problem of solving an equation modulo a rewrite system is decidable, provided the above conditions are satisfied. Furthermore, it is shown there that the problem gets undecidable if any one of the above conditions is dropped. Unfortunately, the authors do not discuss the above conditions and they do not give any examples of ``natural'' term rewrite systems satisfying these conditions. The authors achieve their result by encoding term rewrite systems by means of tree tuple synchronised grammars (TTSG's). This development is technically quite involved, hence difficult to follow. For the entire collection see [Zbl 0888.00017].","type":"string"},"datatype":"string"},"type":"statement","id":"Q3838765$AD7CE42A-A49E-4637-9D12-2756B8B5BB73","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3838765$714E5F60-A02C-4AA8-BCD8-6CCD14995FB7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Solving disequations modulo some class of rewrite systems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Solving_disequations_modulo_some_class_of_rewrite_systems"}}}}}