Abstract: We propose a new model of restricted branching programs which we call incremental branching programs. We show that syntac- tic incremental branching programs capture previously studied struc- tured models of computation for the problem GEN, namely marking machines (Co74) and Poon's extension (Po93) of jumping automata on graphs (CoRa80). We then prove exponential size lower bounds for our syntactic incremental model, and for some other restricted branching program models as well. We further show that nondeterministic syn- tactic incremental branching programs are provably stronger than their deterministic counterpart when solving a natural NL-complete GEN sub- problem. It remains open if syntactic incremental branching programs are as powerful as unrestricted branching programs for GEN problems.
Publication Year: 2009
Publication Date: 2009-01-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot