Enumeration for MSO-Queries on Compressed Trees
<|reference_start|>Enumeration for MSO-Queries on Compressed Trees: 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.<|reference_end|>
@article{lohrey2024enumeration,
    title={Enumeration for MSO-Queries on Compressed Trees},
    author={Markus Lohrey, Markus L. Schmid},
    journal={arXiv preprint arXiv:2403.03067},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.03067},
    primaryClass={cs.FL cs.DB}
}