LEADER 03618nam  22006375  450 
001 996465722903316
005 20200701105233.0
010   $a3-540-46198-1
024 7 $a10.1007/BFb0017563
035   $a(CKB)1000000000233413
035   $a(SSID)ssj0000324931
035   $a(PQKBManifestationID)11254080
035   $a(PQKBTitleCode)TC0000324931
035   $a(PQKBWorkID)10315550
035   $a(PQKB)10109859
035   $a(DE-He213)978-3-540-46198-2
035   $a(PPN)155234269
035   $a(EXLCZ)991000000000233413
100   $a20121227d1989      u|             0
101 0 $aeng
135   $aurnn|008mamaa
181   $ctxt
182   $cc
183   $acr
200 10$aModified Branching Programs and Their Computational Power$b[electronic resource] /$fby Christoph Meinel
205   $a1st ed. 1989.
210  1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d1989.
215   $a1 online resource (VI, 132 p.) 
225 1 $aLecture Notes in Computer Science,$x0302-9743 ;$v370
300   $aBibliographic Level Mode of Issuance: Monograph
311   $a3-540-51340-X 
327   $aPreliminaries -- Branching programs and their computational power -- Nondeterministic branching programs -- ?=branching programs and theirs computational power.
330   $aBranching Programs are, besides Boolean circuits, the most important nonuniform model of computation. This volume gives a survey of the latest research in this field. It presents a branching program-based approach to complexity theory. Starting with a definition of branching programs and a review of the former research, nondeterministic branching programs are introduced and investigated, thus allowing the description of some fundamental complexity classes. The book then concentrates on the new concept of Omega-branching programs. Apart from the usual binary tests they contain features for evaluating certain elementary Boolean functions and are suited for characterizing space-bounded complexity classes. By means of these characterizations the author demonstrates the separation of some restricted complexity classes. In the appendix a number of extremely restricted graph-accessibility problems are given, which are, due to the branching program descriptions in chapters 1-3, p-projection complete in the classes under consideration.
410  0$aLecture Notes in Computer Science,$x0302-9743 ;$v370
606   $aProbabilities
606   $aComputers
606   $aAlgorithms
606   $aCombinatorics
606   $aProbability Theory and Stochastic Processes$3https://scigraph.springernature.com/ontologies/product-market-codes/M27004
606   $aComputation by Abstract Devices$3https://scigraph.springernature.com/ontologies/product-market-codes/I16013
606   $aAlgorithm Analysis and Problem Complexity$3https://scigraph.springernature.com/ontologies/product-market-codes/I16021
606   $aCombinatorics$3https://scigraph.springernature.com/ontologies/product-market-codes/M29010
615  0$aProbabilities.
615  0$aComputers.
615  0$aAlgorithms.
615  0$aCombinatorics.
615 14$aProbability Theory and Stochastic Processes.
615 24$aComputation by Abstract Devices.
615 24$aAlgorithm Analysis and Problem Complexity.
615 24$aCombinatorics.
676   $a519.2
700   $aMeinel$b Christoph$4aut$4http://id.loc.gov/vocabulary/relators/aut$0537947
906   $aBOOK
912   $a996465722903316
996   $aModified Branching Programs and Their Computational Power$92831459
997   $aUNISA