@inproceedings{10.1145/3452021.3458320,
    Abstract = {Processing tree-structured data in the streaming model is a challenge: capturing regular properties of streamed trees by means of a stack is costly in memory, but falling back to finite-state automata drastically limits the computational power. We propose an intermediate stackless model based on register automata equipped with a single counter, used to maintain the current depth in the tree. We explore the power of this model to validate and query streamed trees. Our main result is an effective characterization of regular path queries (RPQs) that can be evaluated stacklessly---with and without registers. In particular, we confirm the conjectured characterization of tree languages defined by DTDs that are recognizable without registers, by Segoufin and Vianu (2002), in the special case of tree languages defined by means of an RPQ.},
    Address = {New York, NY, USA},
    Author = {Barloy, Corentin and Murlak, Filip and Paperman, Charles},
    BookTitle = {Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
    File = {Stackless Processing of Streamed Trees - 3452021.3458320.pdf},
    ISBN = {9781450383813},
    Keywords = {json, querying, weak validation, automata, xml, streaming},
    Location = {Virtual Event, China},
    Pages = {109--125},
    Publisher = {Association for Computing Machinery},
    Series = {PODS'21},
    Title = {Stackless Processing of Streamed Trees},
    URL = {https://doi.org/10.1145/3452021.3458320},
    Year = {2021},
    bdsk-url-1 = {https://doi.org/10.1145/3452021.3458320},
    date-added = {2021-07-15 11:30:49 +0200},
    date-modified = {2021-07-15 11:30:49 +0200},
    numpages = {17},
    doi = {10.1145/3452021.3458320}
}

@inproceedings{10.1145/3452021.3458320, Abstract = {Processing tree-structured data in the streaming model is a challenge: capturing regular properties of streamed trees by means of a stack is costly in memory, but falling back to finite-state automata drastically limits the computational power. We propose an intermediate stackless model based on register automata equipped with a single counter, used to maintain the current depth in the tree. We explore the power of this model to validate and query streamed trees. Our main result is an effective characterization of regular path queries (RPQs) that can be evaluated stacklessly---with and without registers. In particular, we confirm the conjectured characterization of tree languages defined by DTDs that are recognizable without registers, by Segoufin and Vianu (2002), in the special case of tree languages defined by means of an RPQ.}, Address = {New York, NY, USA}, Author = {Barloy, Corentin and Murlak, Filip and Paperman, Charles}, BookTitle = {Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems}, File = {Stackless Processing of Streamed Trees - 3452021.3458320.pdf}, ISBN = {9781450383813}, Keywords = {json, querying, weak validation, automata, xml, streaming}, Location = {Virtual Event, China}, Pages = {109--125}, Publisher = {Association for Computing Machinery}, Series = {PODS'21}, Title = {Stackless Processing of Streamed Trees}, URL = {https://doi.org/10.1145/3452021.3458320}, Year = {2021}, bdsk-url-1 = {https://doi.org/10.1145/3452021.3458320}, date-added = {2021-07-15 11:30:49 +0200}, date-modified = {2021-07-15 11:30:49 +0200}, numpages = {17}, doi = {10.1145/3452021.3458320} }