Michael Benedikt --- Selected Publications

• Tree and String Queries
• XML
• Spatial databases, constraint query languages
• Web Programming
• Verification
• Miscellaneous Finite and Infinite Model Theory
• Ultrafilters and Nonstandard Analysis

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

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

   A draft of the full version of this paper, ``From XQuery to Relational Logics and Back'' , can be found here.

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.

1. "XPath Leashed!" (with Christoph Koch), draft version of a survey on the XPath query language. Submitted for publication in 2006.
2. "Managing XML Data: An Abridged Overview" (with Juliana Freire) In CISE.

Spatial Databases and Constraint Query Languages

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.
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.

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 languages definable in FO" (with Luc Segoufin), STACS 05.
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