Parameter Reduction in Grammar-Compressed Trees

Markus Lohrey, Sebastian Maneth, Manfred Schmidt-Schauß

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Trees can be conveniently compressed with linear straight-line context-free tree grammars. Such grammars generalize straight-line context-free string grammars which are widely used in the development of algorithms that execute directly on compressed structures (without prior decompression). It is shown that every linear straight-line context-free tree grammar can be transformed in polynomial time into a monadic (and linear) one. A tree grammar is monadic if each nonterminal uses at most one context parameter. Based on this result, a polynomial time algorithm is presented for testing whether a given nondeterministic tree automaton with sibling constraints accepts a tree given by a linear straight-line context-free tree grammar. It is shown that if tree grammars are nondeterministic or non-linear, then reducing their numbers of parameters cannot be done without an exponential blow-up in grammar size.
Original languageEnglish
Title of host publicationFoundations of Software Science and Computational Structures
Subtitle of host publication12th International Conference, FOSSACS 2009, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009, York, UK, March 22-29, 2009. Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages15
ISBN (Electronic)978-3-642-00596-1
ISBN (Print)978-3-642-00595-4
Publication statusPublished - 2009


Dive into the research topics of 'Parameter Reduction in Grammar-Compressed Trees'. Together they form a unique fingerprint.

Cite this