Incremental branching programs

Gál, Anna; McKenzie, Pierre; Koucký, Michal

doi:10.4230/DagSemProc.06111.10

Document

Incremental branching programs

Authors Anna Gál, Pierre McKenzie, Michal Koucký

Part of: Volume: Dagstuhl Seminar Proceedings, Volume 6111
Part of: Series: Dagstuhl Seminar Proceedings (DagSemProc)
License: Creative Commons Attribution 4.0 International license
Publication Date: 2006-11-30

PDF

File

PDF

DagSemProc.06111.10.pdf

Filesize: 354 kB
20 pages

Document Identifiers

DOI: 10.4230/DagSemProc.06111.10
URN: urn:nbn:de:0030-drops-6230

Subject Classification

Keywords

Complexity theory
branching programs
logarithmic space
marking machines

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

We propose a new model of restricted branching programs
which we call {em incremental branching programs}. 
We show that {em syntactic}
incremental branching programs capture previously studied 
structured models of computation for the problem GEN, namely marking
machines [Cook74].
and Poon's extension [Poon93] of jumping automata 
on graphs [CookRackoff80].

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 syntactic incremental 
branching programs are
provably stronger than their deterministic counterpart when solving a
natural NL-complete GEN subproblem.
It remains open if syntactic incremental branching programs are as powerful
as unrestricted branching programs for GEN problems.

Joint work with Anna GÃƒÂ¡l and Michal KouckÃƒÂ½

Cite As Get BibTex

Anna Gál, Pierre McKenzie, and Michal Koucký. Incremental branching programs. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006) https://doi.org/10.4230/DagSemProc.06111.10

Author Details

Anna Gál

Pierre McKenzie

Michal Koucký

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail