{"entities":{"Q1187665":{"pageid":1198414,"ns":120,"title":"Item:Q1187665","lastrevid":46258063,"modified":"2025-12-24T10:21:37Z","type":"item","id":"Q1187665","labels":{"en":{"language":"en","value":"Modified branching programs and their computational power"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 43702"}},"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":"Q1187665$C2E796D7-80AC-4CC0-BE51-FF2D88CC3A97","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9c6e65f9ad836ffa851c85e3d30ad4da687b52bd","datavalue":{"value":{"text":"Modified branching programs and their computational power","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1187665$D5BBCAF7-E517-4AD7-8736-4DF5161734CD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dcb3599366376212f4117ca6bfc63ff1c3fdb22a","datavalue":{"value":"0669.68042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187665$4FD5359B-32ED-487F-8009-F5DD3F44AC8C","rank":"normal"}],"P16":[{"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":"Q1187665$F72A4878-C23D-4DFB-9967-9D731C3A0287","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":"Q1187665$484213B2-D720-43D9-B894-7CF65BE56CEA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7883d6b4a608e309b16b988a97013f465b2e60b3","datavalue":{"value":{"time":"+1992-09-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1187665$9C5808C3-4BC7-439E-B05B-FA9B0BF70BAB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dfd04c697a8d83e6acbf4614667874cffcfe91c2","datavalue":{"value":"This book gives a concise treatment of results concerning the nonuniform computation model of branching programs. Branching programs generalize the concept of decision trees, but are less powerful than Boolean circuits. The relationships to the uniform Turing machine model are explored and exact characterizations, as well as lower and upper bounds, are presented. Among others, the modifications studied in this book consist of read-once-only, nondeterministic, bounded-width, and \\(\\omega\\)- branching programs, and combinations thereof.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1187665$74E8673D-ECE0-4BC3-81A4-7B61D1C5BB9C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187665$6D409456-148B-4705-AD89-6D0C498C1FC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"24aafcf24a21bd70cd3b62d3f5f72a6d0d82d816","datavalue":{"value":"68-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187665$637CA44D-30DB-4021-9FFB-6D324F9C4821","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187665$38F33CFF-654D-43AD-A5A2-0845D4640A3A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bc7aaa89c81add656bb921ba806fb45865d7cf58","datavalue":{"value":"43702","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187665$906E697B-1E3A-4FA2-B0F8-CEC164A42768","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bf1c8d33f6fc76ac2e221ea69999b4912603564","datavalue":{"value":"branching program","type":"string"},"datatype":"string"},"type":"statement","id":"Q1187665$2A346405-3732-47C5-A54E-CE5C70097FF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"37c6ca6e5961fc7fcf105580bd33bbecbe5ab0bf","datavalue":{"value":"logarithmic space complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1187665$167D6F9C-4178-44CB-9482-D7653C297038","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5112e82ee58f2b69f4c035d8bc9fb51594a74260","datavalue":{"value":"nonuniform computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1187665$20D214C4-8AE9-4F1E-970B-FFFD7E06E8CF","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":"Q1187665$9B79F8BD-227E-4595-8B55-B15B11940265","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7da6f08fafe05d7302fa6e8f44fc4d4e268df319","datavalue":{"value":{"entity-type":"item","numeric-id":3976028,"id":"Q3976028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ef0f8101d6039c457e57d41c803bd3ec6fc73b7","datavalue":{"value":{"amount":"+0.8060347437858582","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":"Q1187665$6FC9E38B-F5AD-4C8B-BF4B-68751171C099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b321b9c9dc74ff9bee97fa166c0af04ef55136a","datavalue":{"value":{"entity-type":"item","numeric-id":3783568,"id":"Q3783568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef32b51a77e7629b60c71f1e506d88d8523cc93a","datavalue":{"value":{"amount":"+0.7918574810028076","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":"Q1187665$AFE204CE-7AE6-489B-8371-64711795A399","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64350110356d42c5968ddbdab6f7ae1d882b6c44","datavalue":{"value":{"entity-type":"item","numeric-id":1116338,"id":"Q1116338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22149536b1d7ee9128844d9b4102c29489271b1d","datavalue":{"value":{"amount":"+0.7888581156730652","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":"Q1187665$4CB9404E-0912-4E26-BF92-1B8104B7AFCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"433fa7f6a6b22854d70793abe6941c0ac4fd7468","datavalue":{"value":{"entity-type":"item","numeric-id":4462678,"id":"Q4462678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce6fd9a3298ca4bbe1895f297967cb9277ae5f64","datavalue":{"value":{"amount":"+0.7855035662651062","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":"Q1187665$2A4F92AE-AC51-4FEC-829D-982B5BC18A13","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1187665","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1187665"}}}}}