@inproceedings(alserhalibench,
 author       = {Al~Serhali, Antonio and Joachim Niehren},
 year         = {2022},
 title        = {{A Benchmark Collection of Deterministic Automata for XPath Queries}},
 booktitle    = {{XML Prague 2022}},
 address      = {Prague, Czech Republic},
 url          = {https://hal.inria.fr/hal-03527888},
)
@inproceedings(Alur07,
 author       = {Rajeev Alur},
 year         = {2007},
 title        = {Marrying Words and Trees},
 booktitle    = {26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems},
 publisher    = {ACM-Press},
 pages        = {233--242},
 url          = {http://dx.doi.org/10.1145/1265530.1265564},
)
@inproceedings(AlurMadhusudan04,
 author       = {Rajeev Alur and P.~Madhusudan},
 year         = {2004},
 title        = {Visibly pushdown languages},
 editor       = {L{\'{a}}szl{\'{o}} Babai},
 booktitle    = {Proceedings of the 36th Annual {ACM} Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004},
 publisher    = {{ACM}},
 pages        = {202--211},
 doi          = {10.1145/1007352.1007390},
)
@article(AlurMadhusudan09,
 author       = {Rajeev Alur and P.~Madhusudan},
 year         = {2009},
 title        = {Adding nesting structure to words},
 journal      = {Journal of the ACM},
 volume       = {56},
 number       = {3},
 pages        = {1--43},
 url          = {http://doi.acm.org/10.1145/1516512.1516518},
)
@inproceedings(DBLP:conf/birthday/BojanczykW08,
 author       = {Mikolaj Bojanczyk and Igor Walukiewicz},
 year         = {2008},
 title        = {Forest algebras},
 editor       = {J{\"{o}}rg Flum and Erich Gr{\"{a}}del and Thomas Wilke},
 booktitle    = {Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]},
 series       = {Texts in Logic and Games},
 volume       = {2},
 publisher    = {Amsterdam University Press},
 pages        = {107--132},
)
@incollection(BRAUNMUHL19851,
 author       = {Burchard von Braunm\IeC{\"u}hl and Rutger Verbeek},
 year         = {1985},
 title        = {Input Driven Languages are Recognized in log n Space},
 editor       = {Marek Karplnski and {van Leeuwen}, Jan},
 booktitle    = {Topics in the Theory of Computation},
 series       = {North-Holland Mathematics Studies},
 volume       = {102},
 publisher    = {North-Holland},
 pages        = {1 -- 19},
 doi          = {10.1016/S0304-0208(08)73072-X},
)
@article(Buchi60,
 author       = {J.~Richard Büchi},
 year         = {1960},
 title        = {Weak Second-Order Arithmetic and Finite Automata},
 journal      = {Mathematical Logic Quarterly},
 volume       = {6},
 number       = {1-6},
 pages        = {66--92},
 doi          = {10.1002/malq.19600060105},
 eprint       = {https://onlinelibrary.wiley.com/doi/pdf/10.1002/malq.19600060105},
)
@inproceedings(CarmeNiehrenTommasi04,
 author       = {Julien Carme and Joachim Niehren and Marc Tommasi},
 year         = {2004},
 title        = {Querying Unranked Trees with Stepwise Tree Automata},
 editor       = {Vincent van Oostrom},
 booktitle    = {Rewriting Techniques and Applications, 15th International Conference, {RTA} 2004, Aachen, Germany, June 3-5, 2004, Proceedings},
 series       = {Lecture Notes in Computer Science},
 volume       = {3091},
 publisher    = {Springer},
 pages        = {105--118},
 doi          = {10.1007/978-3-540-25979-4\_8},
)
@misc(TATA07,
 author       = {Hubert Comon and Max Dauchet and R\'{e}mi Gilleron and Christof L\"{o}ding and Florent Jacquemard and Denis Lugiez and Sophie Tison and Marc Tommasi},
 year         = {2007},
 title        = {Tree Automata Techniques and Applications},
 howpublished = {Available online since 1997: \url{http://tata.gforge.inria.fr}},
)
@article(debarbieux15,
 author       = {Denis Debarbieux and Olivier Gauwin and Joachim Niehren and Tom Sebastian and Mohamed Zergaoui},
 year         = {2015},
 title        = {Early nested word automata for XPath query answering on {XML} streams},
 journal      = {Theor. Comput. Sci.},
 volume       = {578},
 pages        = {100--125},
 doi          = {10.1016/j.tcs.2015.01.017},
)
@article(DBLP:journals/siamcomp/DietzfelbingerKMHRT94,
 author       = {Martin Dietzfelbinger and Anna~R. Karlin and Kurt Mehlhorn and Friedhelm~Meyer auf~der Heide and Hans Rohnert and Robert~Endre Tarjan},
 year         = {1994},
 title        = {Dynamic Perfect Hashing: Upper and Lower Bounds},
 journal      = {{SIAM} J. Comput.},
 volume       = {23},
 number       = {4},
 pages        = {738--761},
 doi          = {10.1137/S0097539791194094},
)
@misc(FranceschetXPathPT,
 author       = {Massimo Franceschet},
 title        = {XPathMark Performance Test},
 howpublished = {\url{https://users.dimi.uniud.it/~massimo.franceschet/xpathmark/PTbench.html}},
 note         = {Accessed: 2020-10-25},
)
@article(GauwinNiehrenRoos08,
 author       = {Olivier Gauwin and Joachim Niehren and Yves Roos},
 year         = {2008},
 title        = {Streaming Tree Automata},
 journal      = {Information Processing Letters},
 volume       = {109},
 number       = {1},
 pages        = {13--17},
 doi          = {10.1016/j.ipl.2008.08.002},
)
@inproceedings(GauwinNiehrenTison09b,
 author       = {Olivier Gauwin and Joachim Niehren and Sophie Tison},
 year         = {2009},
 title        = {Earliest Query Answering for Deterministic Nested Word Automata},
 booktitle    = {17th International Symposium on Fundamentals of Computer Theory},
 series       = {Lecture Notes in Computer Science},
 volume       = {5699},
 publisher    = {Springer Verlag},
 pages        = {121--132},
 doi          = {10.1007/978-3-642-03409-1\_12},
)
@misc(lickbench,
 author       = {Anthony Lick and Schmitz Sylvain},
 year         = {Last visited April 13th 2022},
 title        = {{XP}ath {B}enchmark},
 url          = {https://archive.softwareheritage.org/browse/directory/1ea68cf5bb3f9f3f2fe8c7995f1802ebadf17fb5},
)
@inproceedings(DBLP:conf/icalp/Mehlhorn80,
 author       = {Kurt Mehlhorn},
 year         = {1980},
 title        = {Pebbling Moutain Ranges and its Application of DCFL-Recognition},
 editor       = {J.~W. de~Bakker and Jan van Leeuwen},
 booktitle    = {Automata, Languages and Programming, 7th Colloquium, Noordweijkerhout, The Netherlands, July 14-18, 1980, Proceedings},
 series       = {Lecture Notes in Computer Science},
 volume       = {85},
 publisher    = {Springer},
 pages        = {422--435},
 doi          = {10.1007/3-540-10003-2\_89},
)
@inproceedings(MozafariZengZaniolo12,
 author       = {Barzan Mozafari and Kai Zeng and Carlo Zaniolo},
 year         = {2012},
 title        = {High-performance complex event processing over {XML} streams},
 editor       = {K.~Sel\c{c}uk Candan and Yi~Chen and Richard~T. Snodgrass and Luis Gravano and Ariel Fuxman and K.~Sel\c{c}uk Candan and Yi~Chen and Richard~T. Snodgrass and Luis Gravano and Ariel Fuxman},
 booktitle    = {SIGMOD Conference},
 publisher    = {ACM},
 pages        = {253--264},
 doi          = {10.1145/2213836.2213866},
)
@inproceedings(NeumannSeidl98,
 author       = {Andreas Neumann and Helmut Seidl},
 year         = {1998},
 title        = {Locating Matches of Tree Patterns in Forests},
 booktitle    = {Foundations of Software Technology and Theoretical Computer Science},
 series       = {Lecture Notes in Computer Science},
 volume       = {1530},
 publisher    = {Springer Verlag},
 pages        = {134--145},
 doi          = {10.1007/978-3-642-03409-1\_12},
)
@article(Sakho,
 author       = {Joachim Niehren and Momar Sakho},
 year         = {2021},
 title        = {Determinization and Minimization of Automata for Nested Words Revisited},
 journal      = {Algorithms},
 volume       = {14},
 number       = {3},
 pages        = {68},
 doi          = {10.3390/a14030068},
)
@inproceedings(niehrenschemadet,
 author       = {Joachim Niehren and Momar Sakho and Al~Serhali, Antonio},
 year         = {2022},
 title        = {Schema-Based Automata Determinization},
 booktitle    = {Gandalf},
 url          = {https://hal.inria.fr/hal-03536045},
)
@article(DBLP:journals/sigact/OkhotinS14,
 author       = {Alexander Okhotin and Kai Salomaa},
 year         = {2014},
 title        = {Complexity of input-driven pushdown automata},
 journal      = {{SIGACT} News},
 volume       = {45},
 number       = {2},
 pages        = {47--67},
 doi          = {10.1145/2636805.2636821},
)
@inproceedings(schmid_et_al:LIPIcs.ICDT.2021.4,
 author       = {Markus~L. Schmid and Nicole Schweikardt},
 year         = {2021},
 title        = {{A Purely Regular Approach to Non-Regular Core Spanners}},
 editor       = {Ke~Yi and Zhewei Wei},
 booktitle    = {24th International Conference on Database Theory (ICDT 2021)},
 series       = {Leibniz International Proceedings in Informatics (LIPIcs)},
 volume       = {186},
 publisher    = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
 address      = {Dagstuhl, Germany},
 pages        = {4:1--4:19},
 doi          = {10.4230/LIPIcs.ICDT.2021.4},
)
@book(straubing1994finite,
 author       = {H.~Straubing},
 year         = {1994},
 title        = {Finite Automata, Formal Logic, and Circuit Complexity},
 series       = {Progress in Computer Science and Applied Series},
 publisher    = {Birkh{\"a}user},
 doi          = {10.1007/978-1-4612-0289-9},
)
@article(Thatcher67b,
 author       = {J.~W. Thatcher},
 year         = {1967},
 title        = {Characterizing derivation trees of context-free grammars through a generalization of automata theory},
 journal      = {Journal of Computer and System Science},
 volume       = {1},
 pages        = {317--322},
 doi          = {10.1016/S0022-0000(67)80022-9},
)