Modified branching programs and their computational power (Q1187665): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
| (One intermediate revision by one other user not shown) | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| links / mardi / name | links / mardi / name | ||
Latest revision as of 02:28, 5 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Modified branching programs and their computational power |
scientific article |
Statements
Modified branching programs and their computational power (English)
0 references
17 September 1992
0 references
This book gives a concise treatment of results concerning the nonuniform computation model of branching programs. Branching programs generalize the concept of decision trees, but are less powerful than Boolean circuits. The relationships to the uniform Turing machine model are explored and exact characterizations, as well as lower and upper bounds, are presented. Among others, the modifications studied in this book consist of read-once-only, nondeterministic, bounded-width, and \(\omega\)- branching programs, and combinations thereof.
0 references
branching program
0 references
logarithmic space complexity
0 references
nonuniform computation
0 references
