University of Oxford Branding

OUCL

news

research

teaching

people

calendar

resources

login

OXFORD UNIVERSITY  COMPUTING LABORATORY

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@comlab.ox.ac.uk

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 langauges" (with Leonid Libkin) In LICS 2002.

XML

Papers
  1. "Interpreting Tree-to-Tree Queries" (with Christoph Koch) In ICALP 2006.

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

  2. "XML Subtree Queries: Specification and Composition" (with Irini Fundulaki) In DPBL 2005.
  3. "Satisfiability of XPath in the presence of DTDs" (with Wenfei Fan and Floris Geerts) In PODS 2005.
  4. "Adding Updates to XQuery: Semantics, Optmization, and Static Analysis" (with Angela Bonifati, Sergio Flesca, and Avinash Vyas) In XIME-P 2005.
  5. "Automated Update Management for XML" (with Glenn Bruns, Julie Gibson, Robin Kuss, and Amy Ng) In Programming Languages for XML (PLAN-X 2002).
  6. "Structural Properties of XPath Fragments" (with Wenfei Fan and Gabi Kuper). In Theoretical Computer Science.
  7. "DTD-directed publishing with Attribute Translation Grammars" (with Chee Yong Chan, Wenfei Fan, Rajeev Rastogi,Shihui Zheng, and Aoying Zhou). In VLDB 2002.
  8. "Capturing types and constraints in Data Exchange" (with Chee Yong Chan, Wenfei Fan, Juliana Freire, and Rajeev Rastogi). In SIGMOD 2003.
Surveys
  1. "XPath Leashed!" (with Christoph Koch), draft version of a survey on the XPath query language. To Appear in 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. "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
  2. "Definability over Linear Constraints" (with H.J. Keisler). In CSL 2000.
  3. "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)
  4. "On the structure of queries in constraint query languages" (with Leonid Libkin) LICS 96.
  5. "Relational queries over Interpreted Structure" (with Leonid Libkin) JACM, 1999.
  6. "Languages for Relational Databases over Interpreted Structures" (with Leonid Libkin) PODS 97.
  7. "Safe Constraint Queries" (with Leonid Libkin) PODS 98. The journal version of this is in SIAM Journal of Computing.
  8. "Exact and Approximate Aggregation in Constraint Databases" (with Leonid Libkin), PODS 99. Actually, I think what I've linked here is the journal version, which should appear in JCSS.
  9. "Reachability and Connectivity Queries in Constraint Databases" (with Martin Grohe, Leonid Libkin, and Luc Segoufin) PODS 2000.
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

  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.

Verification

  1. "Verification of Tree Updates for Optimization" (with Angela Bonifati, Sergio Flesca, and Avinash Vyas). In CAV 2005.
  2. "On Guard: Producing Run-Time Checks from Integrity Constraints" (with Glenn Bruns). In AMAST 2004.
  3. "Analysis of Recursive State Machines" (with Rajeev Alur, Kousha Etessami, Patrice Godefroid, Tom Reps, and Mihalis Yannakakis). To appear in TOPLAS.
  4. "VeriWeb: Automatically Testing Dynamic Web Sites" (with Juliana Freire and Patrice Godefroid) 11th international World Wide Web Conference.
  5. "Verifiable Properties of Database Transactions" (with Tim Griffin and Leonid Libkin, PODS 96). The journal version appeared in Information and Computation, 147 (1998).
  6. "Model-checking of Unrestricted Hierarchical State Machines" (with Patrice Godefroid and Tom Reps) In ICALP 2001.
  7. "A Decidable Logic for Describing Linked Data Structures" (with Mooly Sagiv and Tom Reps) ESOP 99.

Model Theory

  1. "Towards a Characterization of Order-Invariant Queries over Tame Structures" (with Luc Segoufin), CSL 05.
  2. "Regular tree languages definable in FO" (with Luc Segoufin), STACS 05. What is linked is the extended version.
  3. "Expressive power of unary counters" (with H.J. Keisler), ICDT 97.
  4. "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.
  5. "Definability with a Predicate for a Semi-linear Set" (with H.J. Keisler). Journal of Symbolic Logic.

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
benedikt@research.bell-labs.com
Random Image
Random Image
Random Image