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:
  • Immediate eBook download after purchase and usable on all devices
  • Bulk discounts from 10 eBooks
Softcover $89.99
price for USA in USD
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:
  • Immediate eBook download after purchase and usable on all devices
  • Bulk discounts from 10 eBooks
Softcover $89.99
price for USA in USD
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