DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2014.457

Constructing Small Tree Grammars and Small Circuits for Formulas

Authors: Danny Hucke, Markus Lohrey, and Eric Noeth

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Abstract

It is shown that every tree of size n over a fixed set of sigma different ranked symbols can be decomposed into O(n/log_sigma(n)) = O((n * log(sigma))/ log(n)) many hierarchically defined pieces. Formally, such a hierarchical decomposition has the form of a straight-line linear context-free tree grammar of size O(n/log_sigma(n)), which can be used as a compressed representation of the input tree. This generalizes an analogous result for strings. Previous grammar-based tree compressors were not analyzed for the worst-case size of the computed grammar, except for the top dag of Bille et al., for which only the weaker upper bound of O(n/log^{0.19}(n)) for unranked and unlabelled trees has been derived. The main result is used to show that every arithmetical formula of size n, in which only m <= n different variables occur, can be transformed (in time O(n * log(n)) into an arithmetical circuit of size O((n * log(m))/log(n)) and depth O(log(n)). This refines a classical result of Brent, according to which an arithmetical formula of size n can be transformed into a logarithmic depth circuit of size O(n).

Cite as

Danny Hucke, Markus Lohrey, and Eric Noeth. Constructing Small Tree Grammars and Small Circuits for Formulas. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 457-468, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{hucke_et_al:LIPIcs.FSTTCS.2014.457,
  author =	{Hucke, Danny and Lohrey, Markus and Noeth, Eric},
  title =	{{Constructing Small Tree Grammars and Small Circuits for Formulas}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{457--468},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.457},
  URN =		{urn:nbn:de:0030-drops-48639},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.457},
  annote =	{Keywords: grammar-based compression, tree compression, arithmetical circuits}
}

Search Results

Documents authored by Noeth, Eric

Constructing Small Tree Grammars and Small Circuits for Formulas

Abstract

Cite as

Thanks for your feedback!

Could not send message