University of Oxford Logo University of OxfordDepartment of Computer Science - Home
Linked in
Linked in
Follow us on twitter
Twitter
On Facebook
Facebook
Instagram
Instagram

Michael Benedikt — Selected Publications

All papers are in ps or gunzipped ps. There are several papers not linked or not listed: for these send e-mail to michael.benedikt@cs.ox.ac.uk

Foundations of Databases

    Papers
  1. "Positive Higher Order Queries" (with Gabriele Puppis and Huy Vu) In PODS 2010.
  2. "The Impact of Virtual Views on Containment" (with Georg Gottlob) In VLDB 2010.
  3. "Complexity of Higher Order Queries" (with Huy Vu) In ICDT 2011.
    4. "HOMES: a higher-order mapping system" (with Huy Vu) VLDB 2011 demo.
  4. "Determining relevance of accesses at runtime" (with Georg Gottlob and Pierre Senellart) In PODS 2011.
  5. "Monadic Datalog Containment" (with Pierre Bourhis and Pierre Senellart) In ICALP 2012.
  6. "Querying Schemas with Access Restrictions" (with Pierre Bourhis and Clemens Ley) In VLDB 2012. A draft version is here.
    Book Chapters
  1. "Databases" (with Pierre Senellart) In E.K. Blum and A.V. Aho, editors, Computer Science, The Harware, Software, and Heart of It pp. 169 --229, Spring-Verlag, 2012

Tree and String Queries

  1. "A Model-Theoretic Approach to Regular String Relations" (with Luc Segoufin, Leonid Libkin and Thomas Schwentick) In LICS 2001.
  2. "String Operations in Query Languages" (with Luc Segoufin, Leonid Libkin and Thomas Schwentick) In PODS 2001.
  3. "Tree Extension Algebras: logics,automata, and query languages" (with Leonid Libkin) In LICS 2002.
  4. "The Complexity of Two Variable Logic over Finite Trees" (with Saguy Benaim, Witold Charatonik, Emanuel Kieronski, Rastislav Lenhardt, Filip Mazowiecki, and James Worrell) In ICALP 2013.

XML

    Papers
  1. "Automated Update Management for XML" (with Glenn Bruns, Julie Gibson, Robin Kuss, and Amy Ng) In Programming Languages for XML (PLAN-X 2002).
  2. "DTD-directed publishing with Attribute Translation Grammars" (with Chee Yong Chan, Wenfei Fan, Rajeev Rastogi,Shihui Zheng, and Aoying Zhou). In VLDB 2002.
  3. "Structural Properties of XPath Fragments" (with Wenfei Fan and Gabi Kuper). In ICDT 2003, journal version in Theoretical Computer Science.
  4. "Capturing types and constraints in Data Exchange" (with Chee Yong Chan, Wenfei Fan, Juliana Freire, and Rajeev Rastogi). In SIGMOD 2003.
  5. "XML Subtree Queries: Specification and Composition" (with Irini Fundulaki) In DPBL 2005.
  6. "Satisfiability of XPath in the presence of DTDs" (with Wenfei Fan and Floris Geerts) In PODS 2005. Journal version in JACM.
  7. "Adding Updates to XQuery: Semantics, Optmization, and Static Analysis" (with Angela Bonifati, Sergio Flesca, and Avinash Vyas) In XIME-P 2005.
  8. "Interpreting Tree-to-Tree Queries" (with Christoph Koch) In ICALP 2006.

    One half of the full version of this paper appears as ``From XQuery to Relational Logics '' , in TODS.

  9. "How big must complete XML query languages be?" (with Clemens Ley) In ICDT 2009.

  10. "Semantics, Types and Effects for XML Updates" (with James Cheney) In DBPL 2009.

  11. "Schema-based Independence Analysis of XML Updates" (with James Cheney) In VLDB 2009.

  12. "Probabilistic XML via Markov Chains" (with Evgeny Kharlamov, Dan Olteanu, and Pierre Senellart) In VLDB 2010.

  13. "Destabilizers and XML Updates" (with James Cheney) In VLDB 2010.

  14. "Higher Order Functions and Structured Datatypes" (with Huy Vu) In WebDB 2012.
  15. "Determinacy and rewriting of Top-Down and MSO transducers" (with Joost Engelfriet and Sebastian Maneth) In MFCS 2013.
    Surveys
  1. "XPath Leashed!" (with Christoph Koch), draft version of a survey on the XPath query language. ACM Computing Surveys, March 2009.
  2. "Managing XML Data: An Abridged Overview" (with Juliana Freire) In CISE.

Stream Processing

  1. "Efficient and Expressive Tree Filters" (with Alan Jeffrey). In FSTTCS 2007.
  2. "Stream Firewalling of XML Constraints" (with Alan Jeffrey and Ruy Ley-Wild). In SIGMOD 2008.

Querying Social Networks

  1. "Challenges in Searching Online Communities" (with Sihem Amer-Yahia and Philip Bohannon) In Data Engineering Bulletin 2008.
  2. "Efficient Network-Aware Search in Collaborative Tagging Sites" (with Sihem Amer-Yahia, Julia Stoyanovich, and Laks Lakshmanan). In VLDB 2008.

Spatial Databases and Constraint Query Languages

    Papers
  1. "Expressive power of constraint query languages" (with Guozhu Dong, Limsoon Wong, and Leonid Libkin, PODS 96). There's a journal version of this in JACM, 45 (1998)
  2. "On the structure of queries in constraint query languages" (with Leonid Libkin) LICS 96.
  3. "Relational queries over Interpreted Structure" (with Leonid Libkin) JACM, 1999.
  4. "Languages for Relational Databases over Interpreted Structures" (with Leonid Libkin) PODS 97.
  5. "Safe Constraint Queries" (with Leonid Libkin) PODS 98. The journal version of this is in SIAM Journal of Computing.
  6. "Exact and Approximate Aggregation in Constraint Databases" (with Leonid Libkin), PODS 99. Actually, I think what I've linked here is the journal version, in JCSS.
  7. "Reachability and Connectivity Queries in Constraint Databases" (with Martin Grohe, Leonid Libkin, and Luc Segoufin) PODS 2000.
  8. "Definability over Linear Constraints" (with H.J. Keisler). In CSL 2000.
  9. "A characterization of first-order topological properties of planar spatial databases" (with C. Loeding, J. Van den Bussche, and T. Wilke). In PODS 2004, with a journal version (joint with Bart Kuijpers) in JACM
    Book Chapters
  1. "Expressive Power: The Finite Case" with Leonid Libkin in Constraint Databases (Kuper,Libkin, and Paradaens eds.)
  2. "Query Safety with Constraints" , with Leonid Libkin in Constraint Databases

Web Programming and Querying

  1. "MAWL: Integrated Web and Telephone Service Creation" (with Dave Atkins, Tom Ball, Tom Baran, Ken Cox, Dave Ladd, Carlos Puchol, Chris Ramming, Ken Rehor, and Curt Tuckey) In Bell Labs Technical Journal, Spring 97.
  2. "Experience with a Domain Specific Language for Form-based Services" (with Dave Atkins, Tom Ball, Glenn Bruns, Ken Rehor, Ken Cox, and Peter Mataga) Usenix Conference on Domain Specific Languages.
  3. "QUASAR: Querying Annotation, Structure, and Reasoning." (with Luying Chen and Evgeny Kharlamov) EDBT 2012 Demonstration paper.
  4. "ProFoUnd: Program-analysis-based Form Understanding." (with Tim Furche, Andreas Savvides, and Pierre Senellart) WWW 2012 Demonstration paper.
  5. "Access patterns and Integrity constraints revisited." (with Vince Barany and Pierre Bourhis) ICDT 2013.
  6. "ROSEAnn: Reconciling Opinions of Semantic Annotators" (with Luying Chen, Giorgio Orsi, and Stefano Ortona ) VLDB 2013 demo.
  7. "Aggregating Semantic Annotators" (with Luying Chen, Giorgio Orsi, and Stefano Ortona) VLDB 2014 paper.
  8. "Generating Low-cost Plans from Proofs" (with Balder ten Cate and Efi Tsamoura) PODS 2014 paper.
  9. "PDQ:Proof-driven Query Answering over Web-based Data" (with Julien Leblay and Efi Tsamoura) VLDB 2014 demonstration paper.

Verification

  1. "Verifiable Properties of Database Transactions" (with Tim Griffin and Leonid Libkin, PODS 96). The journal version appeared in Information and Computation, 147 (1998).
  2. "A Decidable Logic for Describing Linked Data Structures" (with Mooly Sagiv and Tom Reps) ESOP 99.
  3. "Analysis of Recursive State Machines" (with Rajeev Alur, Kousha Etessami, Patrice Godefroid, Tom Reps, and Mihalis Yannakakis). In TOPLAS.
  4. "Model-checking of Unrestricted Hierarchical State Machines" (with Patrice Godefroid and Tom Reps) In ICALP 2001.
  5. "VeriWeb: Automatically Testing Dynamic Web Sites" (with Juliana Freire and Patrice Godefroid) World Wide Web Conference, 2002.
  6. "On Guard: Producing Run-Time Checks from Integrity Constraints" (with Glenn Bruns). In AMAST 2004.
  7. "Verification of Tree Updates for Optimization" (with Angela Bonifati, Sergio Flesca, and Avinash Vyas). In CAV 2005.
  8. "Two variable vs. linear temporal logic in model checking and games" (with Rastislav Lenhardt and James Worrell). In CONCUR 2011.
  9. "Verification of Two Variable Logic revisited" (with Rastislav Lenhardt and James Worrell). In QEST 2012.
  10. "LTL Model checking of interval Markov Chains" (with Rastislav Lenhardt and James Worrell). In TACAS 2013.
  11. "Effective Interpolation for Guarded Logics (with Balder ten Cate and Michael Vanden Boom). In CSL-LICS 2014.

Automata theory

  1. "Regular repair of Specifications" (with Gabriele Puppis and Cristian Riveros). In LICS 2011.
  2. "The cost of traveling between languages" (with Gabriele Puppis and Cristian Riveros). In ICALP 2011.
  3. "Bisimilarity of Pushdown Automata is Non-elementary" (with Stefan Goller, Stefan Kiefer, and Andzrej Murawski). In LICS 2013.

Model Theory

  1. "Expressive power of unary counters" (with H.J. Keisler), ICDT 97.
  2. "Embedded Finite Models, Stability, and the Impact of Order" (with John Baldwin, LICS 98). The journal version of this is in the Transactions of the American Mathematical Society.
  3. "Definability with a Predicate for a Semi-linear Set" (with H.J. Keisler). In CSL 2001, journal version in Journal of Symbolic Logic.
  4. "Towards a Characterization of Order-Invariant Queries over Tame Structures" (with Luc Segoufin), CSL 05.
  5. "Regular tree languages definable in FO" (with Luc Segoufin), STACS 05. What is linked is the extended version, which contains important corrections over the conference version.
  6. "Rewriting Guarded Negation Queries" (with Vince Barany and Balder ten Cate), MFCS 2013.
  7. "Finite Open World Query Answering with Number Restrictions" (with Antoine Amarilli), LICS 2015.
  8. "The Complexity of Boundedness for Guarded Logics" (with Michael Vanden Boom, Thomas Colcombet, and Balder ten Cate), LICS 2015.

Ultrafilters and Applications to Nonstandard Analysis

  1. "Nonstandard Analysis and Special Ultrafilters", in Developments in Nonstandard Mathematics 1994
  2. "Ultrafilters that Extend Measures", Journal of Symbolic Logic, volume 63, 1998
  3. "Hierarchies of Measure-theoretic Ultrafilters", Annals of Pure and Applied Logic, 1999

Some Errata

  1. There is an important error in the STACS 2005 version of Regular tree languages definable in FO -- the algebraic characterization of first order tree languages given there is not the right one. This is corrected in the journal version linked above.
  2. In the PODS 2011 paper Determining relevance of accesses at runtime, there is an error in some of the complexity bounds for limited access containment (in the ``dependent case''). The corrected bounds are in the ICALP 2012 paper Monadic Datalog Containment.
  3. In the 2009 survey paper XPath Leashed there is an upper bound stated for the complexity of satisfiability of two-variable logic on trees that is incorrect. The correct bounds (along with much more) can be found in the ICALP 2013 paper The Complexity of Two Variable Logic over Finite Trees.
michael.benedikt@cs.ox.ac.uk