{"entities":{"Q1099650":{"pageid":1110402,"ns":120,"title":"Item:Q1099650","lastrevid":69639558,"modified":"2026-04-13T08:23:22Z","type":"item","id":"Q1099650","labels":{"en":{"language":"en","value":"Unification problems with one-sided distributivity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4041330"}},"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":"Q1099650$0EC6B56D-2E31-4835-9034-C86BB618AFC7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"87646a1ff69352a6f6f2331be4e320fd9c0d6546","datavalue":{"value":{"text":"Unification problems with one-sided distributivity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1099650$10DF2B4E-A172-4513-BC41-FCCFC9F47BFE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9f7d7259e590063f5fcdd3a73c301f0575bacc44","datavalue":{"value":"0638.68104","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099650$11CEF75E-3918-4B2A-B36B-566F30A340C5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3a3415b08936175a1baf0de80ed6984397a70ea1","datavalue":{"value":"10.1016/S0747-7171(87)80026-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099650$780FA3C6-7EC3-4E51-893F-7405504F17D5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"57b62ee012be02b7b149d7a5975d257a2f361b4e","datavalue":{"value":{"entity-type":"item","numeric-id":324652,"id":"Q324652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099650$F08A7998-36D8-40C9-BE64-40EA15939427","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c49d90e623208eb4f3f5226194d5be245b33c22","datavalue":{"value":{"entity-type":"item","numeric-id":757059,"id":"Q757059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099650$6C4C9ADA-E1A0-4D80-B5E9-23882B25F56A","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":"Q1099650$53349695-4C5B-4E65-B1B7-67A90D24A411","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1099650$18931761-D621-44F1-AD6F-F34352E38AE1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d62c54e3980bf15a157e80081cb96bdcf8db2b3d","datavalue":{"value":"This work is a study of unification in some equational theories that have a one-sided distributivity axiom: \\(x\\times (y+z)=x\\times y+x\\times z\\). First one-sided distributivity, the theory which has only this axiom, is studied. It is shown that, although one-sided distributivity is a simple theory in many ways, its unification problem is not trivial, and known universal unification procedures fail to provide a decision procedure for it. We give a unification procedure based on a process of decomposition combined with a generalized occurs check, which may be applied in any permutative theory, and another test. These tests together ensure termination.    Next, we show that unification is undecidable if the laws of associativity \\(x+(y+z)=(x+y)+z\\) and a one-sided unit element \\(x\\times 1=x\\) are added to one-sided distributivity. Unification under one-sided distributivity with (one-sided) unit element is shown to be as hard as Markov's problem (associative unification), whereas unification under two-sided distributivity, with or without unit element, is NP-hard. The study of these problems is motivated by possible applications in circuit synthesis and by the need for gaining insight in the problem of combining theories with overlapping sets of operator symbols.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099650$DE3866E0-25E1-4D90-B00F-623DF545FEC7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6e7c2e9d67f9590a26e18c734f34db53ce5ec87","datavalue":{"value":"68T15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099650$8B45CF58-B537-41D0-B098-AF8BD6C03205","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4897136ea1c19614fe909b8db60c4ec176d94a78","datavalue":{"value":"08B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099650$6221EF19-B204-4BD6-8E5B-F90576E98B19","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"84030e968c5304eea976019c4020487d22dd6877","datavalue":{"value":"4041330","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099650$32668F5A-5E3A-4F1B-AEDF-1C5CE19FF7D5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3922eb0b8235fb2b824bcb3eaa0c8d395dbd512","datavalue":{"value":"unification","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099650$0A9C8B16-67A4-4A89-A31A-58A023D99CC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ac708066b077a4cbf2f59c943781969d75d6d03","datavalue":{"value":"equational theories","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099650$4CBD356F-67A8-4E7A-966D-21DF7E4AEAAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44a1a3c2a66d229deed75104f784f4fc9da9f976","datavalue":{"value":"one-sided distributivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099650$7425D182-A859-4039-B991-D2E2594F8426","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6f9621d61ad939b425e9a3236a679679d2f699d","datavalue":{"value":"Markov's problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099650$EE7ADBB9-EF9F-4346-847B-9F8D841A5DC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb784b48a848fdc41f25b24b7c7ca1d8af919b95","datavalue":{"value":"associative unification","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099650$623DBA3B-4FE4-4CEF-A291-2EF4CE8B6747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099650$7FED0446-5986-4F5B-80FA-176843870EC7","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":"Q1099650$53B73644-FBBB-4F00-9CBA-F973BC51A170","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b4d71bbab57e335181b2411d65d8e1ef4dc862e","datavalue":{"value":{"entity-type":"item","numeric-id":1067408,"id":"Q1067408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099650$14E6B93D-235C-4FF7-AD1D-377C38E8DD72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"175c1c6339231426570e05a46d3193da46e70701","datavalue":{"value":{"entity-type":"item","numeric-id":4401926,"id":"Q4401926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099650$F486C2A3-D30A-4518-A77B-4669FD8131E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099650$8BE8D894-6E5D-4C78-A27A-C71707594331","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e9acb750b5a1fcf5fe08b591fc6df182dd9e5e0","datavalue":{"value":{"entity-type":"item","numeric-id":3883561,"id":"Q3883561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099650$15245605-C266-4DEE-8B88-EA57643E784D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cae74153e0f085b8cfa1b39a51e5c7aa9c26c82d","datavalue":{"value":{"entity-type":"item","numeric-id":3338225,"id":"Q3338225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099650$3F485A91-8E16-46DA-8970-062021BEF516","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"092348088466a9288a4b352c8d624aae9ff71ffb","datavalue":{"value":{"entity-type":"item","numeric-id":4159542,"id":"Q4159542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099650$EEAC4AED-ECB5-44B3-8F5E-201232F9646D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c9465d6417bb77bd19e652eaf6c381784d12e8b","datavalue":{"value":{"entity-type":"item","numeric-id":3936229,"id":"Q3936229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099650$5BF64220-56F3-401A-85F7-213F827DFAC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9887b9b79e33b21dbc3558d55c26558304b5187","datavalue":{"value":{"entity-type":"item","numeric-id":1243575,"id":"Q1243575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099650$D59296BC-2AD7-4774-B4C6-AFF6972628AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65a7d163034968b8b573af486389b73d9c031e2e","datavalue":{"value":{"entity-type":"item","numeric-id":3707399,"id":"Q3707399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099650$18A2989B-C2A8-41FD-AA0A-E1896F66DB3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b0f90c485ed1d89b3250f5647f723259f01b989","datavalue":{"value":{"entity-type":"item","numeric-id":3313256,"id":"Q3313256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099650$88CC9B41-8D1E-45E8-9C20-75F6D716B0BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"932383d1ac997ed208ef47dcb574b592efaf75b3","datavalue":{"value":{"entity-type":"item","numeric-id":4065031,"id":"Q4065031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099650$44DEF08D-1244-4796-A1DB-4BF55CC8D100","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ce7f3ac921c8d836253d8bb64c9a6e7ec23075d","datavalue":{"value":{"entity-type":"item","numeric-id":3696499,"id":"Q3696499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"730bf1bafe35ca500573c9edcecaecb4baa5dcfe","datavalue":{"value":{"amount":"+0.9855451583862304","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":"Q1099650$28289A67-FC27-466C-AAEC-E235BCCD7015","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97395ded66542729cc7e1ed9223b23019cc591c4","datavalue":{"value":{"entity-type":"item","numeric-id":4282529,"id":"Q4282529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"437f606635588f8d1fd0e89e4fcc207c5e1b8f9f","datavalue":{"value":{"amount":"+0.8934580683708191","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":"Q1099650$E8BC669E-6C4B-4C9D-9CCD-46E49F2FCC7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bb4afc175ef8e7b41ce467192bd6110a48eba28","datavalue":{"value":{"entity-type":"item","numeric-id":5900732,"id":"Q5900732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8eb407e3fda47d4e94245853539daa6f04af70fe","datavalue":{"value":{"amount":"+0.8892210721969604","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":"Q1099650$78D9EF15-5186-448E-B10C-006EA335335F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b14ac514fbadeed2671d43af4c687f21fb724dd9","datavalue":{"value":{"entity-type":"item","numeric-id":674747,"id":"Q674747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"087f852c0d48bbdb0e341a0cf9c4428a232260bd","datavalue":{"value":{"amount":"+0.8738564848899841","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":"Q1099650$95959365-98ED-4D44-A32D-5C3B8A9EC8FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f16d5c38de60e77d11a38dda4871132280679b4","datavalue":{"value":{"entity-type":"item","numeric-id":2908474,"id":"Q2908474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb1c1c3d73606dc392893e891536f691643fe446","datavalue":{"value":{"amount":"+0.832125186920166","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":"Q1099650$DF7E3586-BDA1-4DFD-A985-E83017B9F459","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Unification problems with one-sided distributivity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Unification_problems_with_one-sided_distributivity"}}}}}