Parameter reduction and automata evaluation for grammar-compressed trees

DOI10.1016/j.jcss.2012.03.003zbMath1246.68114OpenAlexW2049785143MaRDI QIDQ440015

Sebastian Maneth, Markus Lohrey, Manfred Schmidt-Schauss

Publication date: 17 August 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2012.03.003

zbMATH Keywords

straight-line programstree automatatree compressioncontext-free tree grammars

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42)

Related Items (17)

XML compression via directed acyclic graphs ⋮ Compressed Tree Canonization ⋮ Grammar-Based Tree Compression ⋮ Approximation of smallest linear tree grammar ⋮ Nominal Unification and Matching of Higher Order Expressions with Recursive Let ⋮ Constructing small tree grammars and small circuits for formulas ⋮ Linear pattern matching of compressed terms and polynomial rewriting ⋮ Regular matching and inclusion on compressed tree patterns with constrained context variables ⋮ The generative power of delegation networks ⋮ Tree compression using string grammars ⋮ Multiple context-free tree grammars: lexicalization and characterization ⋮ Grammar-based compression of unranked trees ⋮ Constant-time tree traversal and subtree equality check for grammar-compressed trees ⋮ On the complexity of the smallest grammar problem over fixed alphabets ⋮ Largest common prefix of a regular tree language ⋮ Constant delay traversal of grammar-compressed graphs with bounded rank ⋮ Vulnerability aware graphs for RFID protocol security benchmarking

Uses Software

• TreeRePair

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast equality test for straight-line compressed strings
• The complexity of tree automata and XPath on grammar-compressed trees
• Tree transducers, L systems, and two-way machines
• A representation of trees by languages. I
• Spinal-formed context-free tree grammars
• The HOM problem is decidable
• On the complexity of Bounded Second-Order Unification and Stratified Context Unification
• Unification and matching on compressed terms
• Processing Compressed Texts: A Tractability Border
• Bounded Second-Order Unification Is NP-Complete
• Tree-Walking Automata
• The Smallest Grammar Problem
• Choosing Word Occurrences for the Smallest Grammar Problem
• TREE AUTOMATA WITH GLOBAL CONSTRAINTS
• Parameter Reduction in Grammar-Compressed Trees
• Tree-Walking Automata Do Not Recognize All Regular Languages
• The Complexity of Monadic Second-Order Unification
• Unification with Singleton Tree Grammars
• Equality and disequality constraints on direct subterms in tree automata
• First-Order Unification on Compressed Terms
• Complexity of Pebble Tree-Walking Automata
• Automata, Languages and Programming
• Translations on a context free grammar
• Tree Automata with Memory, Visibility and Structural Constraints

This page was built for publication: Parameter reduction and automata evaluation for grammar-compressed trees