DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2017.36

A Unified Method for Placing Problems in Polylogarithmic Depth

Authors: Andreas Krebs, Nutan Limaye, and Michael Ludwig

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract

In this work we consider the term evaluation problem which is, given a term over some algebra and a valid input to the term, computing the value of the term on that input. In contrast to previous methods we allow the algebra to be completely general and consider the problem of obtaining an efficient upper bound for this problem. Many variants of the problems where the algebra is well behaved have been studied. For example, the problem over the Boolean semiring or over the semiring (N,+,*). We extend this line of work. Our efficient term evaluation algorithm then serves as a tool for obtaining polylogarithmic depth upper bounds for various well-studied problems. To demonstrate the utility of our result we show new bounds and reprove known results for a large spectrum of problems. In particular, the applications of the algorithm we consider include (but are not restricted to) arithmetic formula evaluation, word problems for tree and visibly pushdown automata, and various problems related to bounded tree-width and clique-width graphs.

Cite as

Andreas Krebs, Nutan Limaye, and Michael Ludwig. A Unified Method for Placing Problems in Polylogarithmic Depth. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{krebs_et_al:LIPIcs.FSTTCS.2017.36,
  author =	{Krebs, Andreas and Limaye, Nutan and Ludwig, Michael},
  title =	{{A Unified Method for Placing Problems in Polylogarithmic Depth}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{36:1--36:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.36},
  URN =		{urn:nbn:de:0030-drops-83805},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.36},
  annote =	{Keywords: Polylogarithmic depth, Term evaluation, Parallel algorithms}
}

Document

DOI: 10.4230/LIPIcs.STACS.2015.594

Visibly Counter Languages and Constant Depth Circuits

Authors: Andreas Krebs, Klaus-Jörn Lange, and Michael Ludwig

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract

We examine visibly counter languages, which are languages recognized by visibly counter automata (a.k.a. input driven counter automata). We are able to effectively characterize the visibly counter languages in AC^0 and show that they are contained in FO[+].

Cite as

Andreas Krebs, Klaus-Jörn Lange, and Michael Ludwig. Visibly Counter Languages and Constant Depth Circuits. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 594-607, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{krebs_et_al:LIPIcs.STACS.2015.594,
  author =	{Krebs, Andreas and Lange, Klaus-J\"{o}rn and Ludwig, Michael},
  title =	{{Visibly Counter Languages and Constant Depth Circuits}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{594--607},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.594},
  URN =		{urn:nbn:de:0030-drops-49447},
  doi =		{10.4230/LIPIcs.STACS.2015.594},
  annote =	{Keywords: visibly counter automata, constant depth circuits, AC0, FO\lbrack+\rbrack}
}

Search Results

Documents authored by Ludwig, Michael

A Unified Method for Placing Problems in Polylogarithmic Depth

Abstract

Cite as

Visibly Counter Languages and Constant Depth Circuits

Abstract

Cite as

Thanks for your feedback!

Could not send message