Read While You Wait - Get immediate ebook access, if available*, when you order a print book

Lecture Notes in Computer Science

Modified Branching Programs and Their Computational Power

Authors: Meinel, Christoph

Free Preview

Buy this book

eBook $69.99
price for USA in USD
  • The eBook version of this title will be available soon
  • ISBN 978-3-540-46198-2
  • Digitally watermarked, DRM-free
  • Included format:
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Softcover $89.99
price for USA in USD
  • ISBN 978-3-540-51340-7
  • Free shipping for individuals worldwide
  • Immediate ebook access, if available*, with your print order
  • Usually dispatched within 3 to 5 business days.
About this book

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.

Table of contents (5 chapters)

Table of contents (5 chapters)
  • Introduction

    Pages 1-6

  • Preliminaries

    Pages 7-10

  • Branching programs and their computational power

    Pages 11-24

  • Nondeterministic branching programs

    Pages 25-49

  • Ω=branching programs and theirs computational power

    Pages 50-126

Buy this book

eBook $69.99
price for USA in USD
  • The eBook version of this title will be available soon
  • ISBN 978-3-540-46198-2
  • Digitally watermarked, DRM-free
  • Included format:
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Softcover $89.99
price for USA in USD
  • ISBN 978-3-540-51340-7
  • Free shipping for individuals worldwide
  • Immediate ebook access, if available*, with your print order
  • Usually dispatched within 3 to 5 business days.
Loading...

Recommended for you

Loading...

Bibliographic Information

Bibliographic Information
Book Title
Modified Branching Programs and Their Computational Power
Authors
Series Title
Lecture Notes in Computer Science
Series Volume
370
Copyright
1989
Publisher
Springer-Verlag Berlin Heidelberg
Copyright Holder
Springer-Verlag Berlin Heidelberg
eBook ISBN
978-3-540-46198-2
DOI
10.1007/BFb0017563
Softcover ISBN
978-3-540-51340-7
Series ISSN
0302-9743
Edition Number
1
Number of Pages
VI, 132
Topics

*immediately available upon purchase as print book shipments may be delayed due to the COVID-19 crisis. ebook access is temporary and does not include ownership of the ebook. Only valid for books with an ebook version. Springer Reference Works are not included.