Parameter reduction and automata evaluation for grammar-compressed trees

Markus Lohrey, Sebastian Maneth, Manfred Schmidt-Schauß

Research output: Contribution to journalArticlepeer-review


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, polynomial time algorithms are presented for testing whether a given (i) nondeterministic tree automaton or (ii) nondeterministic tree automaton with sibling-constraints or (iii) nondeterministic tree walking automaton, accepts a tree represented by a linear straight-line context-free tree grammar. It is also 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
Pages (from-to)1651-1669
Number of pages19
JournalJournal of Computer and System Sciences
Issue number5
Publication statusPublished - 2012


  • Context-free tree grammars


Dive into the research topics of 'Parameter reduction and automata evaluation for grammar-compressed trees'. Together they form a unique fingerprint.

Cite this