Algorithmic Compression of Finite Tree Languages by Rigid Acyclic Grammars

DOI10.1145/3127401MaRDI QIDQ4608715zbMATH OpenOpenAlexFDO

Authors Sebastian Eberhard, Gabriel Ebner, Stefan Hetzl

Publication date 22 March 2018

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3127401

zbMATH Keywords

finite tree languagesgrammar-based compressionMaxSAT

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• Compressibility of Finite Languages by Grammars
• Grammar-Based Tree Compression
• Syntax directed compression of trees using pushdown automata
• Parameter reduction and automata evaluation for grammar-compressed trees
• Parameter Reduction in Grammar-Compressed Trees
• scientific article; zbMATH DE number 2119662

Cited in

(7)

• Complexity of decision problems on totally rigid acyclic tree grammars
• Anti-unification and the theory of semirings
• On the generation of quantified lemmas
• Parameter reduction and automata evaluation for grammar-compressed trees
• Higher-order pattern generalization modulo equational theories
• Compressibility of Finite Languages by Grammars
• The complexity of tree automata and XPath on grammar-compressed trees

This page was built for publication: Algorithmic Compression of Finite Tree Languages by Rigid Acyclic Grammars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608715)