References

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