Modified branching programs and their computational power
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...
Сохранить в:
| Главный автор: | |
|---|---|
| Формат: | Livre numérique |
| Язык: | Anglais |
| Опубликовано: |
Berlin [etc.] :
Springer
[20..].
Cham : Springer Nature |
| Серии: | Lecture notes in computer science
370 |
| Предметы: | |
| Online-ссылка: | Accès sur la plateforme de l'éditeur Accès sur la plateforme Istex Accès Université d'Orléans Accès INSA CVL |
| Примечание: |
Archives Springer e-books (Licence nationale) Archives Springer e-books (Licence nationale) |
| Autres localisations: | Voir dans le Sudoc |
| Edition sous un autre format: | • Modified branching programs and their computational power, Christoph Meinel, Berlin, Springer-Verlag, 1989, 1 vol. (VI-132 p.), Lecture notes in computer science, 3-540-51340-X • Modified Branching Programs and Their Computational Power, Texte imprimé, 9783662163597 |
| LEADER | 03396nam a22003977a 4500 | ||
|---|---|---|---|
| 001 | 945612 | ||
| 008 | 110927q2000 xxe ||| |||| 00| 0 eng d | ||
| 009 | PPN155234269 | ||
| 020 | |a 9783540461982 (PDF) | ||
| 041 | 0 | |a eng | |
| 082 | |a 519.234 | ||
| 082 | |a 004 | ||
| 100 | 1 | |a Meinel, Christoph, |d 1954-...., |c Professeur. | |
| 245 | 1 | 0 | |a Modified branching programs and their computational power |c Christoph Meinel. |
| 260 | |a Berlin [etc.] : |b Springer. | ||
| 260 | |a Cham : |b Springer Nature, |c [20..]. | ||
| 490 | 0 | |a Lecture notes in computer science |v 370 |x 1611-3349 | |
| 500 | |a Archives Springer e-books (Licence nationale) | ||
| 500 | |a Archives Springer e-books (Licence nationale) | ||
| 505 | 0 | |a Preliminaries -- Branching programs and their computational power -- Nondeterministic branching programs -- ?=branching programs and theirs computational power. | |
| 506 | |a Accès en ligne pour les établissements français bénéficiaires des licences nationales | ||
| 506 | |a Accès soumis à abonnement pour tout autre établissement | ||
| 506 | |a Conditions particulières de réutilisation pour les bénéficiaires des licences nationales. https://www.licencesnationales.fr/springer-nature-ebooks-contrat-licence-ln-2017 | ||
| 520 | |a 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. | ||
| 650 | |a Informatique | ||
| 650 | |a Algorithmes | ||
| 650 | |a Complexité de calcul (informatique) | ||
| 650 | |a Analyse combinatoire | ||
| 650 | |a Processus ramifiés | ||
| 776 | 0 | |0 021179158 |t Modified branching programs and their computational power |f Christoph Meinel |c Berlin |n Springer-Verlag |d 1989 |p 1 vol. (VI-132 p.) |s Lecture notes in computer science |z 3-540-51340-X | |
| 776 | 0 | |t Modified Branching Programs and Their Computational Power |b Texte imprimé |z 9783662163597 | |
| 856 | 4 | |q PDF |u https://doi.org/10.1007/BFb0017563 |z Accès sur la plateforme de l'éditeur | |
| 856 | 4 | |u https://revue-sommaire.istex.fr/ark:/67375/8Q1-DLG9G0R9-F |z Accès sur la plateforme Istex | |
| 856 | 4 | |5 452349901:747909016 |u https://ezproxy.univ-orleans.fr/login?url=https://doi.org/10.1007/BFb0017563 |z Accès Université d'Orléans | |
| 856 | 4 | |5 180339901:750921927 |u https://ezproxy.insa-cvl.fr/login?qurl=https://doi.org/10.1007/BFb0017563 |z Accès INSA CVL | |
| 997 | |0 945612 |1 Livre numérique |a Ressource numérique |b INSA |b ENSA |c 0/Bibliothèque numérique/ |c 1/Bibliothèque numérique/Autre ressource numérique/ | ||