{"entities":{"Q4462678":{"pageid":6492277,"ns":120,"title":"Item:Q4462678","lastrevid":48271696,"modified":"2026-01-04T04:42:27Z","type":"item","id":"Q4462678","labels":{"en":{"language":"en","value":"Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2066226"}},"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":"Q4462678$4DFD6D79-7CBC-430C-8282-1AC0FB193A3E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"54ee25e395755037886e0dd76c4599ed9b3a6ae2","datavalue":{"value":{"text":"Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4462678$3F28C405-C99A-47B7-8CA3-CBB3FC28C764","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a89ae5bc6e8d24882a80f0078be27b3ee72e3ec6","datavalue":{"value":"1084.68049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4462678$4C212857-B7D7-4958-80B9-0F7FFEB9338A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"be4ee1fbd4b7733cd16d69d04f0190aaf1da757e","datavalue":{"value":{"entity-type":"item","numeric-id":171934,"id":"Q171934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$EF976534-80B7-4597-9930-DA9D464DFDD9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"cb11a7d64aa2e2ac6f5f0a641dfeb8e0525b889d","datavalue":{"value":{"entity-type":"item","numeric-id":2720405,"id":"Q2720405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$F0D13296-0325-4A20-8A14-4E658FA8EB69","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7f2c658547352f67a9de92adfcc83c5224bfe428","datavalue":{"value":{"time":"+2004-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4462678$B89A63BD-27CC-47DA-BB00-976578016D28","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a41fcbe02ccdfb467d7bdba9b5b6dbc97e728f80","datavalue":{"value":"http://www.numdam.org/item?id=ITA_2003__37_1_51_0","type":"string"},"datatype":"url"},"type":"statement","id":"Q4462678$469C7BAB-D03A-413E-B3BE-86AC2360D5B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"6f9c7561a336d1878b88f69894b6a589663e0e42","datavalue":{"value":"https://eudml.org/doc/92713","type":"string"},"datatype":"url"},"type":"statement","id":"Q4462678$DD867DC7-F062-4B56-A6E6-DA2ABF107F55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"9501e428b65c0dac0cc52cf4e67e84f815e19afc","datavalue":{"value":"https://semanticscholar.org/paper/a7cb45c36a032329180ceb1198ccbbd4a80d6bd7","type":"string"},"datatype":"url"},"type":"statement","id":"Q4462678$700E077E-599B-4EB1-A6BB-2E435104B6C6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4462678$628F33A8-7090-424A-95F5-95F87EF1190C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4462678$25CB6C7E-2D10-4252-A4BF-103345CA78CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4462678$42BCA57E-4A13-4F58-8FF5-5C3FDBCB05AF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9aafb75317e6fbec23e6cecf6b4a2ace2728d2c6","datavalue":{"value":"2066226","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4462678$35D638E2-A07B-4E1D-B516-106949B9CA9C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da67da54e89e7c80f20f3f95c3ceec18bb927753","datavalue":{"value":"Computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4462678$20ABCF3F-1324-4939-84D7-A21187662867","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1296749c47c91f5d2a0da93372cc04163e57d3a","datavalue":{"value":"read-once branching programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q4462678$D030AB38-E1A6-4398-8756-3032C504B53B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f532e2b08234dd6967fc70eafbf0c8f20a836d3e","datavalue":{"value":"nondeterminism","type":"string"},"datatype":"string"},"type":"statement","id":"Q4462678$E0F2F464-E225-4207-A489-B8D3D4551613","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q4462678$23DBFDD5-5043-412A-AE3E-08984D643867","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":"Q4462678$39265C9E-1968-4AE7-BA7F-E9CF476990DB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8256c0a60a09bafeb703b9594c11dec2adbf3f3d","datavalue":{"value":"W1980708571","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4462678$7C85F1BD-7A5C-4291-8C43-6A0FFB4250B8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"29c30f9f448fb1fd75a320e8b96473cbce649725","datavalue":{"value":{"entity-type":"item","numeric-id":3579215,"id":"Q3579215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$F2DC5DE4-5CFD-4365-AE3B-2EC56AB204FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f21d2c43380fd71ce30b186cde8cfc3789054c2","datavalue":{"value":{"entity-type":"item","numeric-id":2771493,"id":"Q2771493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$B132E0DA-E908-485F-8FE8-D6D4CC5648C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c28b51a029cd5d9ed4bf45e2efbc485db83b48ac","datavalue":{"value":{"entity-type":"item","numeric-id":2508966,"id":"Q2508966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$BC4D91A5-5267-4A65-8107-B39854E7139C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f23e3b780ea96a3b7b9f87e464364a10f68906a","datavalue":{"value":{"entity-type":"item","numeric-id":4708564,"id":"Q4708564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$B78D6353-0D3F-4AF6-B6E6-BEE77D4822E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f4150d4584eafb8457c578c72e61f86894bc805","datavalue":{"value":{"entity-type":"item","numeric-id":2366719,"id":"Q2366719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$38C7598C-F35C-46D2-AACB-37A6A8CF36EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9fabf48f951d01714a9f0de36bc42525e27638d","datavalue":{"value":{"entity-type":"item","numeric-id":4779145,"id":"Q4779145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$5AC6EAF7-129A-4D01-B694-8AFF9FC57810","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":"Q4462678$6A875EAA-A5B8-46F8-8600-6EF6AD366905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1626c6a073fae5477a342820cd5f34f4b930a32b","datavalue":{"value":{"entity-type":"item","numeric-id":4281560,"id":"Q4281560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$5E12BFB5-A95F-438C-ADD2-E91AEAD39232","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2779c135e276cb2ba89f1577b854a83ed2c3554d","datavalue":{"value":{"entity-type":"item","numeric-id":4419787,"id":"Q4419787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$D998FA56-9014-493A-83DF-3D35F2A7C961","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80f06e31eaae3e7c9bdc20c4ffadaf92d3ac9fa0","datavalue":{"value":{"entity-type":"item","numeric-id":4337605,"id":"Q4337605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$2A4D2D92-F717-4B4D-A495-2DC0DF111DD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba0e3077adaf2d2173485f335661cf097a36b4bf","datavalue":{"value":{"entity-type":"item","numeric-id":4737247,"id":"Q4737247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$33F54D6B-CEFF-4DDE-92E5-55A9E7D271F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ec4896edc35f1e12505542682c8c6b6145a21f0","datavalue":{"value":{"entity-type":"item","numeric-id":4875692,"id":"Q4875692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$6C4DAAEA-7682-4081-8C9A-02F93B964B13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cf789eef750075301c91d62be053b2c28c47fe2","datavalue":{"value":{"entity-type":"item","numeric-id":685120,"id":"Q685120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$FC9EE9F8-6AC5-4202-A3F4-732D3FDC3AFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"514b291bcc18717499c847de12de372fe9e5cca0","datavalue":{"value":{"entity-type":"item","numeric-id":5545524,"id":"Q5545524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$C9C7822A-0342-4CE8-8DF2-D997F4B25F48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ad4af54afc577078985b72b533b0637abf0eb7f","datavalue":{"value":{"entity-type":"item","numeric-id":4536401,"id":"Q4536401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$6437A3B0-5BF7-4006-9266-76706E3A6532","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6dca15c419555d8d22c489f4f641b7f15932d47","datavalue":{"value":{"entity-type":"item","numeric-id":1575258,"id":"Q1575258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$4D2916BE-2BF1-446F-AED1-2560F0267F4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd29d824dbce9664110e60e74e7edbbffcc7c5d9","datavalue":{"value":{"entity-type":"item","numeric-id":673788,"id":"Q673788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$4276F100-FAC1-48A3-A78B-D9A4FFDA87FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cf05c9957ec360576e1a7126bd6cf1c9fd1b152","datavalue":{"value":{"entity-type":"item","numeric-id":5949487,"id":"Q5949487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$8A67059D-FEA0-4403-AC4C-9C179DA83761","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2c4125497f2218907cf62cd27810e71c18d00ab","datavalue":{"value":{"entity-type":"item","numeric-id":4542589,"id":"Q4542589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$DC0805A4-61E8-401C-8306-29D818CFC6A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8624ac8b08c43bff2290ca70392ccbd3bba72141","datavalue":{"value":{"entity-type":"item","numeric-id":3762226,"id":"Q3762226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$1C4F4A79-3373-452E-A389-37E8EB471CA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ee9bdbd9786926088840fd488fe60b509eb451c","datavalue":{"value":{"entity-type":"item","numeric-id":4485697,"id":"Q4485697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$332A610D-3756-4680-B07E-DB0578988BD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf36e4d08916e5eb2b7aca189552e4a7c8e235a6","datavalue":{"value":{"entity-type":"item","numeric-id":4736860,"id":"Q4736860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4462678$D6656F3B-484F-41E5-88F3-3E4907CD8FF6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4abda774e45f81fefb1c47f8c28fca7a11562b66","datavalue":{"value":"10.1051/ITA:2003010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4462678$24FE991D-6CEB-4FB2-A949-3DCCA8F65A3A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7cbe26e1561e31ec681dfedcc0e0b2bf4c86e8ec","datavalue":{"value":{"entity-type":"item","numeric-id":4418658,"id":"Q4418658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a93b45e796742385e0fbadcf1517f11731d904f1","datavalue":{"value":{"amount":"+0.9875367879867554","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":"Q4462678$94008C33-2B97-4FB2-B618-A39F8A6D19E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da5708ab69a29b6229d2e4c713f885188bc48c3b","datavalue":{"value":{"entity-type":"item","numeric-id":1007589,"id":"Q1007589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf84e6fb0ea450e4a90baf237dab5414610e1ed0","datavalue":{"value":{"amount":"+0.8586925864219666","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":"Q4462678$1B987B84-7E28-42F3-99CD-D12BFDC22835","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c919c1f7ef269b227e88db23ba52b362d3a237c","datavalue":{"value":{"entity-type":"item","numeric-id":4708564,"id":"Q4708564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30c2b6849e7973e53ad29ef6257942ecf1ea59e3","datavalue":{"value":{"amount":"+0.8470539450645447","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":"Q4462678$716099E7-9D26-44AB-9F58-1D0A73E4A6AC","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":"81e117bf01e8156245ea02521f7fe49ae6de2038","datavalue":{"value":{"amount":"+0.8460037112236023","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":"Q4462678$FC863C86-C502-439D-87EF-C60ADD8D7B4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87e84e50d7c7669119aaf1668677f74c84898351","datavalue":{"value":{"entity-type":"item","numeric-id":2581005,"id":"Q2581005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a489e9541706d0968c6aacdecae8881972e41096","datavalue":{"value":{"amount":"+0.8408408164978027","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":"Q4462678$B79BCEEC-1CB9-4204-8D45-2EBE24DD401B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4462678","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4462678"}}}}}