{"entities":{"Q1330665":{"pageid":1341415,"ns":120,"title":"Item:Q1330665","lastrevid":70157511,"modified":"2026-04-13T12:49:47Z","type":"item","id":"Q1330665","labels":{"en":{"language":"en","value":"On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 609771"}},"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":"Q1330665$A0131C1B-D250-4B3F-9F55-99D79798A159","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0fd5e797c792465bb758b7cfc0ce1fe298753f38","datavalue":{"value":{"text":"On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1330665$AA355004-A56C-49E4-B67E-DA412DC61A3E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5c0b381e97acd34eec683e08fbb20b19dbce55c7","datavalue":{"value":"0803.68049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330665$C36C1E3B-E380-45F7-A6EE-C8269F3133EA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3fc565f2c9bc2ec51dccbd6cd90a1103041a0cdc","datavalue":{"value":"10.1016/0020-0190(94)00048-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330665$66AF42E7-39DB-4CD8-AFE9-B6AF0E9EE49A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b435c2af0c1344152ba06d3e178493e195a140b0","datavalue":{"value":{"entity-type":"item","numeric-id":1330664,"id":"Q1330664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330665$6C462160-11B7-4F31-AAB8-2C3BD66A7F15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aad099f57a9ffbfe76501531fc67aa620054130c","datavalue":{"value":{"entity-type":"item","numeric-id":202501,"id":"Q202501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330665$0057FCBD-7EB4-433A-B064-753C5188E709","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330665$FE18ECCC-A1F1-4EE8-B541-EF73423140ED","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"71edc96fcbd008bfd3061c3ff4af97a6b34cf242","datavalue":{"value":{"time":"+1994-07-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1330665$8817A1CF-604D-499B-81FA-07EE5A2FC441","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7e9a18c05d7bf5bcd4580db7c1827b0ae694de77","datavalue":{"value":"One of the fundamental problems in computer-aided circuit design is the task of representing logic functions. Although, in principle, any valid representation is allowed, some representations may be preferred because they are more efficient in memory, more efficient to manipulate, or more indicative of the complexity of the final implementation. The search of an optimal trade-off between these competing objectives -- succinct representation of Boolean functions and feasible manipulation algorithms -- is a central theme of computer-aided logic synthesis.   One candidate which seems to satisfy these two conditions is the concept of decision graphs or branching programs.   The paper reports results of a systematic inspection of the computational complexity of basic tasks of Boolean manipulation such as satisfiability, tautology test, equivalence test, and binary Boolean synthesis in terms of different restricted types of branching programs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330665$C47D096D-A772-46AE-9B08-41838BC8D3BA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"12fea9828bf27e39c9e9f072731e1ed2d0f10101","datavalue":{"value":{"entity-type":"item","numeric-id":202501,"id":"Q202501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330665$2E9B09BA-A706-41A5-8FDB-BED9B67DB9BA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330665$73F2C5DB-E4A9-4BD3-ADD0-86038B46ECB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6ba0db88ec1d9208c9b2d78c4b1e523872c7ec39","datavalue":{"value":"68U07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330665$C2A0B34B-A230-4199-B8CA-569666631099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330665$3C393D3B-A48A-4E72-9616-79F3D301E972","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6d4c3be6327204bfe2989ff040effd58305b851e","datavalue":{"value":"609771","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330665$4C5CA758-8757-4322-AFEC-F3CDCB6F1A4E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"929ccfbb42c576f33cbc37973bcb7ca667bd3bd2","datavalue":{"value":"CAD","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330665$BA120919-6295-4C82-A6FC-832D7AC6B2D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"43d8de44b3f88bd19a871628a3509981cd748562","datavalue":{"value":"data structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330665$126F8025-43C0-4343-8EDF-A1E63B23F8D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6a0a073691266b0ecc66980e46d2aca401a95ab","datavalue":{"value":"BDD","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330665$1295C634-6C65-4808-A3EE-A585153B3A5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff9f78089affef06c072081bb824e40f99a75bd9","datavalue":{"value":"efficient algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330665$C9DB9C89-026A-4D33-AF47-3D3902573317","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88f18b5f62f151b295bc7357ab052bb2238fe4ba","datavalue":{"value":"computer-aided circuit design","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330665$7494F4FD-404F-4083-B41E-B0BB3A20B8B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb5a830579b475e59eaac799be7398a9142f423b","datavalue":{"value":"Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330665$AD3D8FCC-4A5D-4EFF-BB21-F0F9372B189A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c90c9fca965a4015e49012f483d2b7d700f5a60d","datavalue":{"value":"computer-aided logic synthesis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330665$A4CD76C7-615E-47C1-AD26-DC2C91F5A947","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b05f8a0c0bc2e21b398fb36320ee8521fada9b15","datavalue":{"value":"decision graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330665$363D52D1-6461-46D0-AF74-9218E40D7AF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec24897927a0742784fae89aed9a922bc2a81fec","datavalue":{"value":"branching programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330665$B8AE7C34-6BB5-47AB-9412-4E7D955830A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea79858dffcb5ba5636ac59d660860583c1e20a3","datavalue":{"value":"Boolean manipulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330665$374695C9-7007-4218-A4FF-FBA5E51AF627","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":"Q1330665$C1B3076B-87D4-4F86-B707-143567B2EC2F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"144269bdac30f2381dab6db8a5034be52c174bcf","datavalue":{"value":"https://doi.org/10.1016/0020-0190(94)00048-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1330665$A8080EC0-3BDC-4980-91E7-7C5B8C171E4C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ad91832d46330cb8a47a9cf8c0ae73d1d9b411a1","datavalue":{"value":"W1972591946","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330665$5BBBD517-3610-4492-BF6A-44983935A932","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0144faf3da4de6d410c51d8371e21d8e32667277","datavalue":{"value":{"entity-type":"item","numeric-id":4156322,"id":"Q4156322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330665$3AE2EA28-E45D-4EDE-A666-67E5200847DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e0bce9bac897f983fda4ecc0cf3bbfd3856074f","datavalue":{"value":{"entity-type":"item","numeric-id":1144943,"id":"Q1144943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330665$7F62E645-D1E0-430E-8B3D-C728FC07A891","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50324ccb6206134f253ce476b8660b15930be48f","datavalue":{"value":{"entity-type":"item","numeric-id":673087,"id":"Q673087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330665$BED25D07-3E38-4F6B-9F68-4C92D54A8F1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d0863918228d158fae088a6efc6f79f2c8e8057","datavalue":{"value":{"entity-type":"item","numeric-id":3724245,"id":"Q3724245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330665$E3A0DF4A-021A-451A-836D-B21958785B0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b49014f9db00400a426fee1b60bcc1c4b6081176","datavalue":{"value":{"entity-type":"item","numeric-id":4037091,"id":"Q4037091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330665$F7974753-CB36-46FD-A703-D6ADC13F517C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f67782435c81856906476d249cbb89a86efd5732","datavalue":{"value":{"entity-type":"item","numeric-id":4160379,"id":"Q4160379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330665$D8B03556-4752-4151-8005-7C39C86453C7","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":"Q1330665$94077468-FD0B-41CF-AB38-769AD0BA06B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1cdfb5536a521f63363e276a66d5cafa5c7f9ba","datavalue":{"value":{"entity-type":"item","numeric-id":5628016,"id":"Q5628016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330665$7519F9F3-CAB5-48C5-BE8F-55F7047D0B21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b7502174b8cd991b757104f1cb91cae8ae5a1fa","datavalue":{"value":{"entity-type":"item","numeric-id":1187665,"id":"Q1187665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330665$FACB8730-9BCF-495E-BB04-9374BB1228A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e6b3fc89d44e833288db945598366aa371ca997","datavalue":{"value":{"entity-type":"item","numeric-id":4005192,"id":"Q4005192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330665$8D8C9985-B4B2-433E-8AA0-9F6572703E85","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"884b5fb583b3564661e83be3959fce7d4aed8cdd","datavalue":{"value":{"entity-type":"item","numeric-id":4281654,"id":"Q4281654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a650e0636d90ffa1fc273816550b7a45b5056b8","datavalue":{"value":{"amount":"+0.891486406326294","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":"Q1330665$2AC2EB20-EB81-480D-BEE6-9FD819E9A1A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eaea0953ae6c10369c1f8aacd62d1412843a005a","datavalue":{"value":{"entity-type":"item","numeric-id":3724245,"id":"Q3724245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5ddeb1acda2cebdca64713b44d4afafe59255cf","datavalue":{"value":{"amount":"+0.8623270988464355","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":"Q1330665$CC44B2FA-EB09-42B8-BE36-C270A3A905BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea4a5293fc3f2080fc18789c5badf30e7fb2a30b","datavalue":{"value":{"entity-type":"item","numeric-id":4281560,"id":"Q4281560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e61e6f45244013fd86db246c44ed25736b826345","datavalue":{"value":{"amount":"+0.8292571306228638","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":"Q1330665$DA2533B8-24DF-412D-B58A-A337564605B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"525cd79179a87d0fbcd0cbac1ef38caca4d35aef","datavalue":{"value":{"entity-type":"item","numeric-id":4934627,"id":"Q4934627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43d0aeb478741de41f0ac7b9da947611314d0441","datavalue":{"value":{"amount":"+0.8273316025733948","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":"Q1330665$56036AEA-FE98-402E-A311-FCC8EAC95193","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eaed22b936074146c45eeed1209816c75fa6b489","datavalue":{"value":{"entity-type":"item","numeric-id":4005192,"id":"Q4005192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe7052e192c964ce03d79ea1f4a9ecde38ef00a0","datavalue":{"value":{"amount":"+0.8209236860275269","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":"Q1330665$8A02D464-9E60-4DCC-B975-C483019C706E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_analysis_and_manipulation_of_Boolean_functions_in_terms_of_decision_graphs"}}}}}