Coverart for item
The Resource Modified branching programs and their computational power, Christoph Meinel, (electronic book)

Modified branching programs and their computational power, Christoph Meinel, (electronic book)

Label
Modified branching programs and their computational power
Title
Modified branching programs and their computational power
Statement of responsibility
Christoph Meinel
Creator
Author
Subject
Language
eng
Summary
Branching 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
Member of
Action
digitized
Cataloging source
OCLCE
http://library.link/vocab/creatorName
Meinel, Christoph
Dewey number
519.2/34
Index
index present
LC call number
QA274.76
LC item number
.M45 1989
Literary form
non fiction
Nature of contents
  • dictionaries
  • bibliography
Series statement
Lecture notes in computer science
Series volume
370
http://library.link/vocab/subjectName
  • Branching processes
  • Computational complexity
  • théorie complexité
  • programme branchement
  • processus branchement
Label
Modified branching programs and their computational power, Christoph Meinel, (electronic book)
Instantiates
Publication
Antecedent source
file reproduced from original
Bibliography note
Includes bibliographical references (pages 127-130) and index
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Color
black and white
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Control code
SPR610217117
Dimensions
unknown
Extent
1 online resource (vi, 132 pages).
Form of item
online
Isbn
9783540513407
Level of compression
  • lossless
  • lossy
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Reformatting quality
  • preservation
  • access
Reproduction note
Electronic resource.
Specific material designation
remote
System details
Master and use copy. Digital master created according to Benchmark for Faithful Digital Reproductions of Monographs and Serials, Version 1. Digital Library Federation, December 2002.
Label
Modified branching programs and their computational power, Christoph Meinel, (electronic book)
Publication
Antecedent source
file reproduced from original
Bibliography note
Includes bibliographical references (pages 127-130) and index
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Color
black and white
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Control code
SPR610217117
Dimensions
unknown
Extent
1 online resource (vi, 132 pages).
Form of item
online
Isbn
9783540513407
Level of compression
  • lossless
  • lossy
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Reformatting quality
  • preservation
  • access
Reproduction note
Electronic resource.
Specific material designation
remote
System details
Master and use copy. Digital master created according to Benchmark for Faithful Digital Reproductions of Monographs and Serials, Version 1. Digital Library Federation, December 2002.

Library Locations

Processing Feedback ...