Summer semester 2006

Foundations of Tree Query

Wednessdays, 16 - 18 h
room 035, Neuphilologicum

Overview

3. 5. Introduction
10. 5. Algebras of trees
[1]
17. 5. Trees as relational structures
[2,3,4]
24. 5. Trees as relational structures (2)
31. 5. First-order logic as a query language
[5,6,7]
7. 6. Pentecost break
14. 6. First-order logic plus binary transitive closure
[9]
21. 6. Monadic second-order logic
[3]
28. 6. Transitive closure logics
[10]
5. 7. Propositional dynamic logic (1)
[11,12]
12. 7. Propositional dynamic logic (2)
[11,12]
19. 7. Core XPath (1)
[7,8,13,14]
26. 7. Conclusion

References

  1. Burris, Stanley , Sankappanavar, H.P.: A Course in Universal Algebra; Springer 1981
  2. Ebbinghaus, Heinz-Dieter; Flum, Jörg; Thomas, Wolfgang: Mathematical Logic; 2nd ed., Springer 1994
  3. Rogers, James: A Descriptive Approach to Language-Theoretic Complexity; CSLI Publications 1998
  4. Backofen, Rolf; Rogers, James; Vijay-Shanker, K.: A First-Order Axiomatization of the Theory of Finite Trees; Journal of Logic, Language, and Information 4:5-39
  5. Steven Bird, Yi Chen, Susan Davidson, Haejoong Lee, and Yifeng Zheng: Designing and Evaluating an XPath Dialect for Linguistic Queries; in Proceedings 22nd International Conference on Data Engineering (ICDE), pp 52-61, 2006.
  6. Stephan Kepser: Finite Structure Query - A Tool for Querying Syntactically Annotated Corpora; in EACL 2003, pp 179-186, 2003.
  7. Maarten Marx: First order paths in ordered trees; in Proceedings ICDT 2005, pp 114-128, 2005.
  8. W3C XPath 2.0 reference
  9. Stephan Kepser: Properties of Binary Transitive Closure Logic over Trees; in Formal Grammar 2006.
  10. Hans-Jörg Tiede and Stephan Kepser: Monadic Second-Order Logic over Trees and Deterministic Transitive Closure Logics; in 13th Workshop on Logic, Language, Information, and Computation, Grigori Mints (ed.), 2006.
  11. L. Afanasiev, P. Blackburn, I. Dimitriou, B. Gaiffe, E. Goris, M. Marrx, and M. de Rijke: PLD for Ordered Trees; Journal of Applied Non-Classical Logics.
    12. Marcus Kracht: Tools and Techniques for Modal Logic; Elsevier 1999.
  12. Maarten Marx: XCPath, the first order complete XPath dialect; in Proceedings PODS 2004.
  13. Maarten Marx: XPath with conditional axis relations; in Proceedings EDBT 2004.
Stephan Kepser
Last modified: Wed Jul 26 15:13:54 CEST 2006