The complexity of tree automata and XPath on grammar-compressed trees
type: Item
instance of: scholarly article
title: The complexity of tree automata and XPath on grammar-compressed trees
zbMATH Open document ID: 1153.68402
author: Markus Lohrey
author: Sebastian Maneth
published in: Theoretical Computer Science
publication date: 2007-01-09T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 5083509
zbMATH Keywords: tree automata
zbMATH Keywords: XPath
zbMATH Keywords: tree compression
describes a project that uses: XPath
MaRDI profile type: Publication
full work available at URL: j.tcs.2006.07.024
OpenAlex ID: W2148149459
cites work: Closure properties and decision problems of dag automata
cites work: Database Programming Languages
cites work: The Smallest Grammar Problem
cites work: A representation of trees by languages. I
cites work: A representation of trees by languages. II
cites work: Q4393480
cites work: Q3323279
cites work: The complexity of XPath query evaluation and XML typing
cites work: The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
cites work: Q2778879
cites work: Word Problems and Membership Problems on Compressed Words
cites work: Implementation and Application of Automata
cites work: Foundations of Software Science and Computation Structures
cites work: A PTIME-complete matching problem for SLP-compressed words
cites work: Automated Reasoning with Analytic Tableaux and Related Methods
cites work: Q3221403
cites work: On the complexity of database queries
cites work: Q4951112
cites work: Automata, Languages and Programming
DOI: 10.1016/J.TCS.2006.07.024
Recommended article: Implementation and Application of Automata
Recommended article: Parameter reduction and automata evaluation for grammar-compressed trees
Recommended article: Q4994134
Recommended article: Q4415261
Recommended article: The Complexity of Tree Automata and Logics of Programs
Recommended article: Alternating automata on data trees and XPath satisfiability
Recommended article: Syntax Directed Compression of Trees Using Pushdown Automata
Recommended article: Algorithmic Compression of Finite Tree Languages by Rigid Acyclic Grammars
Recommended article: Foundations of Software Science and Computation Structures
Recommended article: On the Nonterminal Complexity of Tree Controlled Grammars
description: scientific article; zbMATH DE number 5083509