Parameter Reduction in Grammar-Compressed Trees

DOI10.1007/978-3-642-00596-1_16zbMath1234.68182OpenAlexW1669099564MaRDI QIDQ3617731

Sebastian Maneth, Markus Lohrey, Manfred Schmidt-Schauss

Publication date: 31 March 2009

Published in: Foundations of Software Science and Computational Structures (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-00596-1_16

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

Congruence Closure of Compressed Terms in Polynomial Time, Parameter reduction and automata evaluation for grammar-compressed trees, Unification with Singleton Tree Grammars

Cites Work

• The complexity of tree automata and XPath on grammar-compressed trees
• Tree transducers, L systems, and two-way machines
• Spinal-formed context-free tree grammars
• Bounded Second-Order Unification Is NP-Complete
• Automata, Languages and Programming
• Tree Automata with Memory, Visibility and Structural Constraints