{"entities":{"Q1356507":{"pageid":1367246,"ns":120,"title":"Item:Q1356507","lastrevid":70954560,"modified":"2026-04-13T18:28:42Z","type":"item","id":"Q1356507","labels":{"en":{"language":"en","value":"Positive and Horn decomposability of partially defined Boolean functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1018584"}},"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":"Q1356507$A09732AB-C664-4E03-A3DA-1FA1F1F35F5A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5b5f0942eb66a6b245b27ed44bae34eec37dc604","datavalue":{"value":{"text":"Positive and Horn decomposability of partially defined Boolean functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1356507$876DB5EE-558E-4CD3-837E-12F8432BE3E1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"502ace48a68a40626029a211b73b6f6a4d4be324","datavalue":{"value":"0873.06011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356507$09D0DA57-2F66-400F-85C4-21A71F92D21A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5ae8b1bf65cde1115754e6c7e95417e2cdfdee71","datavalue":{"value":"10.1016/S0166-218X(96)00053-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356507$5A685759-D8D3-4962-BB36-952285D8839C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cffea2588f41343c1ca50bec4f0b17d24b9d478b","datavalue":{"value":{"entity-type":"item","numeric-id":171929,"id":"Q171929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356507$A036E9BD-3AB2-4D59-8A96-6C395AF95FA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aaf356e2e065b420d1e5cfd7f6ac58b1a1a166cb","datavalue":{"value":{"entity-type":"item","numeric-id":1356506,"id":"Q1356506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356507$9C141287-2292-46F3-BBAF-2D0B93A4B111","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"746535ddb96ae77c4a55cf2874e59b3bf4f00d57","datavalue":{"value":{"entity-type":"item","numeric-id":171928,"id":"Q171928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356507$B717F327-7E4D-46AD-BA2E-745956BF0B3F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356507$1BA70E0D-1E95-4476-B035-17FA08B92982","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a485241a3a3b9daf7939aecb397ceccd34cb8917","datavalue":{"value":{"time":"+1997-10-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1356507$592DE7B4-F285-4213-B2BA-83FD70476CD9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3395a2cd6863e39784161d0f578415f36fc38e6f","datavalue":{"value":"http://www.elsevier.com/locate/dam","type":"string"},"datatype":"url"},"type":"statement","id":"Q1356507$3025FC79-45EE-4C07-914E-11CB4C60B73E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"93c1e406724c035f61ed2082ee068f3012c842e8","datavalue":{"value":"Let \\(T\\) be a set of positive examples, \\(F\\) a set of negative examples, i.e. \\(T,F\\subset\\{0,1\\}^n\\), \\(T\\cap F=\\emptyset\\), and let \\((T,F)\\) be the partially defined Boolean function (pdBf), defined by  \\[ (T,F)(\\nu)=\\begin{cases} 1\\text{ if }\\nu\\in T\\\\ 0\\text{ if }\\nu\\in F\\end{cases} \\]  Given a pdBf \\((T,F)\\) and a family of subsets \\(S_i\\subseteq\\{1,2,\\dots,n\\}\\), \\(i=0,\\dots,k\\), the decomposability problem is to decide the existence of Boolean functions \\(h_1,\\dots,h_k\\), \\(g\\) such that the function \\(f(\\nu)=g(\\nu[S_0],h_1(\\nu[S_1]),h_2(\\nu[S_2]),\\dots,h_k(\\nu[S_k]))\\) is an extension of the pdBf \\((T,F)\\), where \\(\\nu[S]\\) denotes the projection of the vector \\(\\nu\\) on the subset \\(S\\) of indices. Let \\(P\\), \\(H\\) denote classes of positive and Horn functions and let, e.g., \\(P(S_0,P(S_1),\\dots,P(S_k))\\) be a decomposition \\(g(\\nu[S_0],h_1(\\nu[S_1]),h_2(\\nu[S_2]),\\dots,h_k(\\nu[S_k]))\\) where all functions \\(g\\), \\(h_i\\) are positive. Several results on the complexity of finding decompositions have been obtained, e.g., it is shown that for schemes \\(P(S_0,P(S_1),P(S_2),P(S_3))\\), \\(P(S_0,P(S_1),H(S_2))\\) the decomposability problem is NP-complete, but \\(P(P(S_1),H(S_2))\\) and \\(H(P(S_1),P(S_2))\\) both can be solved in polynomial time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356507$DE10F3B1-1C9A-4D9F-9F23-4725AA845BC5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f3eb9b2932c3fdc120e877804d57f4cb2d94e9","datavalue":{"value":"06E30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356507$C7D885CC-2444-4197-926F-1EDD1AF5EDD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cfe779e91fe9c53ee133568259955801965765ae","datavalue":{"value":"68T05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356507$2783B323-AF7E-4A01-8A44-BEE6E2D9FF37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356507$9F8F8217-C9FD-4810-B6A6-B5DF90393403","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"18614c088c45477d4ab54598604e592d42dfb50e","datavalue":{"value":"1018584","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356507$0A18287E-C982-4289-8621-2DB24E6A7CC3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba8721bb1f9a5905d40f11e5fd8b98caf204716","datavalue":{"value":"partial Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356507$62902601-04AA-4973-9F21-635B4068BE3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356507$D95B4C2F-4C83-4C11-98E3-8413E7750CD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d014c4fad10cedacf413347444022073cc4cafa1","datavalue":{"value":"positive functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356507$44ED2945-6B68-4CF7-A30C-F1AC6B16B52A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85fe3d889576edb55507d05e1a84b0050d9d44b0","datavalue":{"value":"positive examples","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356507$B4D255EE-577C-47DE-B6D8-A6C8A0A7BF72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"337ae0ee98cb4ffc115f44fca224f0472cf2522b","datavalue":{"value":"negative examples","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356507$D0D3DAE5-107B-47F7-B24D-AA913FC4A310","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d19f9da1e4e1b7ee3f5ef5dadf4765a35f7ed24","datavalue":{"value":"Horn functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356507$012ADE7E-CBE7-4BAB-B3AD-EDCE0427C627","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"615f2a3773e3a9a3bad386a540fbc6c58cfa22ee","datavalue":{"value":"decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356507$BA587C00-7B68-4163-826A-ACFC384D65EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66bea9b6d9c866baa791493f0615aeab5165082d","datavalue":{"value":"decomposability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356507$DC8FE230-FB54-4550-BF38-B4BE482DF1D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356507$D5CDA7C1-AFE5-413A-B108-8023E18C614A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4e1df29911c330da2d8d89435a35b182dae9e523","datavalue":{"value":{"entity-type":"item","numeric-id":589408,"id":"Q589408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356507$749B71A0-5BDF-4AF7-A753-3380E049F5DA","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":"Q1356507$883D9F8C-5804-445B-9889-C41CDB2F80F5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cf035d2fecb7e445991dd16e141f37bab3768a8","datavalue":{"value":{"entity-type":"item","numeric-id":1254112,"id":"Q1254112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356507$1F118141-6952-4E40-8007-998CF6FEC6DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d49d96a9389dc464cf7afcb91013bd72b790e00","datavalue":{"value":{"entity-type":"item","numeric-id":1383161,"id":"Q1383161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356507$CC767181-620D-4A9A-AB19-5AE54B081DF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25ac9b94479986b4cb02b2e68fcb05c7f04e2a7b","datavalue":{"value":{"entity-type":"item","numeric-id":3491589,"id":"Q3491589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356507$D754DD66-5541-41B5-B405-5558540A5DA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42dc2cae0abcd30bc9f7d35178b90ca3527edb89","datavalue":{"value":{"entity-type":"item","numeric-id":3893838,"id":"Q3893838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356507$64C99D30-B837-4A89-8F2A-40458DE7CFD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c403665aa6e3aa64da28618956f2f116df15324","datavalue":{"value":{"entity-type":"item","numeric-id":1204870,"id":"Q1204870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356507$4BAF8536-C25B-4CAC-A0B4-C0F9517B4A0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a73f079fad88596351ff709cf186cec234a2805","datavalue":{"value":{"entity-type":"item","numeric-id":3723723,"id":"Q3723723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356507$06150B96-AD62-438C-BD30-820A461FF147","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":"Q1356507$53C48C36-6A83-4CD8-95AB-410D089CBF6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"346f6aaab33baaaa893f7b1de3c781ac8f52b363","datavalue":{"value":{"entity-type":"item","numeric-id":5668427,"id":"Q5668427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356507$5C291CB2-2055-4C76-89CB-AC6A85A2C19E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a49c45cfeee592259d7dad085948a609b194d064","datavalue":{"value":{"entity-type":"item","numeric-id":5630824,"id":"Q5630824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356507$65272BD6-41F2-43AC-AF2A-7FA4F0118BB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"143421a0cbe4ba34cedbed6f5fa70d101952a550","datavalue":{"value":{"entity-type":"item","numeric-id":3668890,"id":"Q3668890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356507$9CECAC85-5522-4507-93E8-0629DCCD56A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"206f75359923c1f185ca3ff397d16f2430804d83","datavalue":{"value":{"entity-type":"item","numeric-id":4268864,"id":"Q4268864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356507$854A9FA4-81D3-4045-9B18-6CEB0B36A680","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"685f64f9fb2880bd21b03911ef73e9f9571bb562","datavalue":{"value":{"entity-type":"item","numeric-id":3997892,"id":"Q3997892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356507$BE5E73D3-8482-4485-89B2-B3DBDC881520","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"dc9051597bf7a74a0f8e56736c609c1ae189cb9b","datavalue":{"value":"W2090464622","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356507$53883D7B-6F5E-4F09-B9DB-3C29CE7B4188","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3893fe11e21a9201bdd795e2f14bb53a7c5e420","datavalue":{"value":{"entity-type":"item","numeric-id":1900137,"id":"Q1900137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"336577e4ac976098e31cf5c37e893043563141d1","datavalue":{"value":{"amount":"+0.8324616551399231","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":"Q1356507$09851AE1-6461-4C66-B551-20106CF7050F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"921151aa2b2e06599b1b28c7f8ed2d182ec3d018","datavalue":{"value":{"entity-type":"item","numeric-id":4268864,"id":"Q4268864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb67bc6a9f8651ecc828c49f6c6d49654658143d","datavalue":{"value":{"amount":"+0.8040105700492859","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":"Q1356507$DD7B6C37-5A1D-46FC-A35F-19A0B5D7C97F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa6c0e98fb238b6195c2e9478c7015fa6d160878","datavalue":{"value":{"entity-type":"item","numeric-id":2181249,"id":"Q2181249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b15fe33910f1379c86ecbe73202d2d9ba71f4cb5","datavalue":{"value":{"amount":"+0.7984544038772583","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":"Q1356507$73610EB9-0B19-40F4-9645-7D4648FC33D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92ff0eadc4346484f11e5db7e7f7abb8def3fc83","datavalue":{"value":{"entity-type":"item","numeric-id":4499532,"id":"Q4499532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e06914e496dce861efe435556b1c0c488c9c67b","datavalue":{"value":{"amount":"+0.786726713180542","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":"Q1356507$37D5CFEA-C352-4A1E-AF0F-42ED746074E2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Positive and Horn decomposability of partially defined Boolean functions","badges":[]}}}}}