ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > NONSYNTACTIC (1:
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