Back to Search
Start Over
Parameter reduction and automata evaluation for grammar-compressed trees
- Source :
-
Journal of Computer & System Sciences . Sep2012, Vol. 78 Issue 5, p1651-1669. 19p. - Publication Year :
- 2012
-
Abstract
- Abstract: 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. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 78
- Issue :
- 5
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 76352083
- Full Text :
- https://doi.org/10.1016/j.jcss.2012.03.003