Parameter reduction and automata evaluation for grammar-compressed trees
type: Item
instance of: scholarly article
title: Parameter reduction and automata evaluation for grammar-compressed trees
zbMATH Open document ID: 1246.68114
author: Markus Lohrey
author: Sebastian Maneth
author: Manfred Schmidt-Schauß
published in: Journal of Computer and System Sciences
publication date: 2012-08-17T00:00:00Z
Mathematics Subject Classification ID: 68P30
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 6067751
zbMATH Keywords: straight-line programs
zbMATH Keywords: tree compression
zbMATH Keywords: tree automata
zbMATH Keywords: context-free tree grammars
describes a project that uses: TreeRePair
MaRDI profile type: Publication
full work available at URL: j.jcss.2012.03.003
OpenAlex ID: W2049785143
cites work: Automata, Languages and Programming
cites work: The Smallest Grammar Problem
cites work: Choosing Word Occurrences for the Smallest Grammar Problem
cites work: Q4347161
cites work: Processing Compressed Texts: A Tractability Border
cites work: Fast equality test for straight-line compressed strings
cites work: The complexity of tree automata and XPath on grammar-compressed trees
cites work: First-Order Unification on Compressed Terms
cites work: Unification and matching on compressed terms
cites work: Unification with Singleton Tree Grammars
cites work: The Complexity of Monadic Second-Order Unification
cites work: Equality and disequality constraints on direct subterms in tree automata
cites work: Tree Automata with Memory, Visibility and Structural Constraints
cites work: Tree-Walking Automata Do Not Recognize All Regular Languages
cites work: Tree-Walking Automata
cites work: Complexity of Pebble Tree-Walking Automata
cites work: Parameter Reduction in Grammar-Compressed Trees
cites work: Q3862379
cites work: Q4179852
cites work: A representation of trees by languages. I
cites work: Translations on a context free grammar
cites work: Spinal-formed context-free tree grammars
cites work: Bounded Second-Order Unification Is NP-Complete
cites work: On the complexity of bounded second-order unification and stratified context unification
cites work: Tree transducers, L systems, and two-way machines
cites work: The HOM problem is decidable
cites work: TREE AUTOMATA WITH GLOBAL CONSTRAINTS
DOI: 10.1016/J.JCSS.2012.03.003
Recommended article: Parameter Reduction in Grammar-Compressed Trees
Recommended article: Grammar-Based Tree Compression
Recommended article: Algorithmic Compression of Finite Tree Languages by Rigid Acyclic Grammars
Recommended article: Syntax Directed Compression of Trees Using Pushdown Automata
Recommended article: The complexity of tree automata and XPath on grammar-compressed trees
Recommended article: Tree compression using string grammars
Recommended article: Grammar-based compression of unranked trees
Recommended article: Q3323278
description: scientific article; zbMATH DE number 6067751