The complexity of tree automata and XPath on grammar-compressed trees

DOI10.1016/j.tcs.2006.07.024zbMath1153.68402OpenAlexW2148149459MaRDI QIDQ860863

Markus Lohrey, Sebastian Maneth

Publication date: 9 January 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.07.024

zbMATH Keywords

tree automatatree compressionXPath

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

XML compression via directed acyclic graphs, Grammar-Based Tree Compression, Approximation of smallest linear tree grammar, Processing succinct matrices and vectors, Fixpoint logics over hierarchical structures, Parameter reduction and automata evaluation for grammar-compressed trees, Recognition of directed acyclic graphs by spanning tree automata, Tree compression using string grammars, Colored operads, series on colored operads, and combinatorial generating systems, Constant-time tree traversal and subtree equality check for grammar-compressed trees, On the complexity of the smallest grammar problem over fixed alphabets, Parameter Reduction in Grammar-Compressed Trees, Unification with Singleton Tree Grammars, Tree compression with top trees, Slowing Down Top Trees for Better Worst-Case Compression

Uses Software

• XPath

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Closure properties and decision problems of dag automata
• A representation of trees by languages. II
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
• A representation of trees by languages. I
• On the complexity of database queries
• A PTIME-complete matching problem for SLP-compressed words
• The complexity of XPath query evaluation and XML typing
• The Smallest Grammar Problem
• Automated Reasoning with Analytic Tableaux and Related Methods
• Foundations of Software Science and Computation Structures
• Automata, Languages and Programming
• Word Problems and Membership Problems on Compressed Words
• Database Programming Languages
• Implementation and Application of Automata