Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Nonsyntactic (1:
TR98-045 | 17th July 1998
Detlef Sieling

A Separation of Syntactic and Nonsyntactic (1,+k)-Branching Programs

For (1,+k)-branching programs and read-k-times branching
programs syntactic and nonsyntactic variants can be distinguished. The
nonsyntactic variants correspond in a natural way to sequential
computations with restrictions on reading the input while lower bound
proofs are easier or only known for the syntactic variants. In this
paper it is shown ... more >>>

ISSN 1433-8092 | Imprint