License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-6230
URL: http://drops.dagstuhl.de/opus/volltexte/2006/623/
Go to the corresponding Portal


Gl, Anna ; McKenzie, Pierre ; Kouck, Michal

Incremental branching programs

pdf-format:
Document 1.pdf (355 KB)


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ý

BibTeX - Entry

@InProceedings{gl_et_al:DSP:2006:623,
  author =	{Anna G{\'a}l and Pierre McKenzie and Michal Koucký},
  title =	{Incremental branching programs},
  booktitle =	{Complexity of Boolean Functions},
  year =	{2006},
  editor =	{Matthias Krause and Pavel Pudl{\'a}k and R{\"u}diger Reischuk and Dieter van Melkebeek},
  number =	{06111},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/623},
  annote =	{Keywords: Complexity theory, branching programs, logarithmic space, marking machines}
}

Keywords: Complexity theory, branching programs, logarithmic space, marking machines
Seminar: 06111 - Complexity of Boolean Functions
Issue Date: 2006
Date of publication: 30.11.2006


DROPS-Home | Fulltext Search | Imprint Published by LZI