Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Jez, Artur
Lohrey, Markus

dblp
dblp

Not MPG Author(s):

Lohrey, Markus

Editor(s):

Mayr, Ernst
Portier, Natacha

dblp
dblp

Not MPII Editor(s):

Mayr, Ernst
Portier, Natacha

BibTeX cite key*:

Jez2014STACS

Title, Booktitle

Title*:

Approximation of smallest linear tree grammar

Booktitle*:

31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Event, URLs

URL of the conference:

http://stacs2014.sciencesconf.org/

URL for downloading the paper:

http://drops.dagstuhl.de/opus/volltexte/2014/4478/

Event Address*:

Lyon, France

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

5 March 2014

Event End Date:

8 March 2014

Publisher

Name*:

Schloss Dagstuhl--Leibniz-Zentrum fuer Informati

URL:

http://www.dagstuhl.de/

Address*:

Dagstuhl-Wadern, Germany

Type:

Extended Abstract

Vol, No, Year, pp.

Series:

Leibniz International Proceedings in Informatics

Volume:

23

Number:


Month:

March

Pages:

445-457

Year*:

2014

VG Wort Pages:


ISBN/ISSN:

978-3-939897-65-1

Sequence Number:


DOI:

10.4230/LIPIcs.STACS.2014.445



Note, Abstract, ©


(LaTeX) Abstract:

A simple linear-time algorithm
for constructing a linear
context-free tree grammar of size $O(r^2 g \log n)$
for a given input tree $T$ of size $n$ is presented, where $g$ is the size of
a minimal linear context-free tree grammar for $T$, and $r$ is the maximal rank
of symbols in $T$ (which is a constant in many applications). This is the first
example of a grammar-based tree compression algorithm with an
approximation ratio polynomial in $g$. The analysis of the algorithm uses an extension of the recompression technique
(used in the context of grammar-based string compression)
from strings to trees.

Keywords:

Grammar-based compression, Tree compression, Tree-grammars



Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Jez2014STACS,
AUTHOR = {Jez, Artur and Lohrey, Markus},
EDITOR = {Mayr, Ernst and Portier, Natacha},
TITLE = {Approximation of smallest linear tree grammar},
BOOKTITLE = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
PUBLISHER = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informati},
YEAR = {2014},
TYPE = {Extended Abstract},
VOLUME = {23},
PAGES = {445--457},
SERIES = {Leibniz International Proceedings in Informatics},
ADDRESS = {Lyon, France},
MONTH = {March},
ISBN = {978-3-939897-65-1},
DOI = {10.4230/LIPIcs.STACS.2014.445},
}


Entry last modified by Artur Jez, 12/15/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
11/24/2014 02:04:23 PM
Revision
1.
0.


Editor
Artur Jez
Artur Jez


Edit Date
11/24/2014 04:33:42 PM
11/24/2014 02:04:23 PM