Parameter reduction and automata evaluation for grammar-compressed trees

Rytter, 2004, Grammar compression, LZ-encodings, and string algorithms with implicit input, vol. 3142, 15

Charikar, 2005, The smallest grammar problem, IEEE Trans. Inform. Theory, 51, 2554, 10.1109/TIT.2005.850116

Carrascosa, 2010, Choosing word occurrences for the smallest grammar problem, vol. 6031, 154

Karpinski, 1997, An efficient pattern-matching algorithm for strings with short descriptions, Nordic J. Comput., 4, 172

Miyazaki, 2000, An improved pattern matching algorithm for strings in terms of straight-line programs, J. Discrete Algorithms, 1, 187

Rytter, 2000, Compressed and fully compressed pattern-matching in one and two dimensions, Proc. IEEE, 88, 1769, 10.1109/5.892712

Plandowski, 1994, Testing equivalence of morphisms on context-free languages, vol. 855, 460

Lifshits, 2007, Processing compressed texts: A tractability border, vol. 4580, 228

M. Schmidt-Schauß, G. Schnitger, Fast equality test for straight-line compressed strings, Frank report 45, Institut für Informatik, Fachbereich Informatik und Mathematik, J.W. Goethe-Universität, Frankfurt am Main, 2011.

Busatto, 2008, Efficient memory representation of XML document trees, Inf. Syst., 33, 456, 10.1016/j.is.2008.01.004

Lohrey, 2006, The complexity of tree automata and XPath on grammar-compressed trees, Theoret. Comput. Sci., 363, 196, 10.1016/j.tcs.2006.07.024

Lamping, 1990, An algorithm for optimal lambda calculus reductions, 16

Lohrey, 2011, Tree structure compression with repair, 353

Buneman, 2003, Path queries on compressed XML, 141

M. Schmidt-Schauß, Polynomial equality testing for terms with shared substructures, Frank report 21, Institut für Informatik, Fachbereich Informatik und Mathematik, J.W. Goethe-Universität, Frankfurt am Main, 2005.

Fisher, 2007, Structural selectivity estimation for XML documents, 626

S. Maneth, T. Sebastian, Fast and tiny structural self-indexes for XML, CoRR abs/1012.5696, 2010.

Gascón, 2011, First-order unification on compressed terms, vol. 10, 51

Gascón, 2011, Unification and matching on compressed terms, ACM Trans. Comput. Log., 12, 10.1145/1970398.1970402

Gascón, 2009, Unification with singleton tree grammars, vol. 5595, 365

Gascón, 2008, Context matching for compressed terms, 93

Levy, 2008, The complexity of monadic second-order unification, SIAM J. Comput., 38, 1113, 10.1137/050645403

Bogaert, 1992, Equality and disequality constraints on direct subterms in tree automata, vol. 577, 161

Comon

Comon-Lundh, 2007, Tree automata with memory, visibility and structural constraints, vol. 4423, 168

Bojanczyk, 2008, Tree-walking automata do not recognize all regular languages, SIAM J. Comput., 38, 658, 10.1137/050645427

Bojanczyk

Samuelides, 2007, Complexity of pebble tree-walking automata, vol. 4639, 458

Lohrey, 2009, Parameter reduction in grammar-compressed trees, vol. 5504, 212

Hopcroft, 1979

Hopcroft, 2003

Gécseg, 1997, Tree languages, 1

Courcelle, 1978, A representation of trees by languages I, Theoret. Comput. Sci., 6, 255, 10.1016/0304-3975(78)90008-7

Aho, 1971, Translations on a context-free grammar, Inform. and Control, 19, 439, 10.1016/S0019-9958(71)90706-6

Engelfriet, 2007, XML transformation by tree-walking transducers with invisible pebbles, 63

M. Fischer, Grammars with macro-like productions, PhD thesis, Harvard University, Massachusetts, 1968.

Fujiyoshi, 2000, Spinal-formed context-free tree grammars, Theory Comput. Syst., 33, 59, 10.1007/s002249910004

Levy, 2006, Bounded second-order unification is NP-complete, vol. 4098, 400

Levy, 2011, On the complexity of bounded second-order unification and stratified context unification, Log. J. IGPL, 19, 763, 10.1093/jigpal/jzq010

M. Saadi, Auswertung von Tree Walking Automaten auf komprimierten Daten, Masterʼs thesis, Universität, Leipzig, 2009.

Engelfriet, 1980, Tree transducers, L systems, and two-way machines, J. Comput. System Sci., 20, 150, 10.1016/0022-0000(80)90058-6

Godoy, 2010, The HOM problem is decidable, 485

Barguñó, 2010, The emptiness problem for tree automata with global constraints, 263

Filiot, 2010, Tree automata with global constraints, Internat. J. Found. Comput. Sci., 21, 571, 10.1142/S012905411000743X