Enumeration for MSO-Queries on Compressed Trees
Proceedings of the ACM on Management of Data(2024)
摘要
We present a linear preprocessing and output-linear delay enumeration
algorithm for MSO-queries over trees that are compressed in the
well-established grammar-based framework. Time bounds are measured with respect
to the size of the compressed representation of the tree. Our result extends
previous work on the enumeration of MSO-queries over uncompressed trees and on
the enumeration of document spanners over compressed text documents.
更多查看译文
关键词
evaluation over compressed data,mso-enumeration,straight-line programs,unranked trees
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要