Publications

Last updated: May 2006


Below is the list of my papers. When there exist both conference and journal versions of a paper, the former is on the list only if the titles are different.
Here are links to web pages of my co-authors: Marcelo Arenas, Pablo Barcelo, Michael Benedikt, Guozhu Dong, Ron Fagin, Wenfei Fan, Tim Griffin, Martin Grohe, Lauri Hella, Frank Neven, Juha Nurmonen, Thomas Schwentick,Luc SegoufinLimsoon Wong; they are probably doing much better job maintaining their web pages. Click here to email me
  1. Logical definability and query languages over ranked and unranked trees.
  2. Michael Benedikt, Leonid Libkin, and Frank Neven.
    ACM Transactions on Computational Logic (TOCL), to appear.
    (Note: preliminary version in LICS'02 and LICS'03.)
  3. Data exchange and incomplete information.
  4. Leonid Libkin.
    In Proceedings of the 25nd Symposium on Principles of Database Systems (PODS'06), pages .....
  5. On redundancy vs dependency preservation in normalization: an information-theoretic study of 3NF.
  6. Solmaz Kolahi and Leonid Libkin.
    In Proceedings of the 25nd Symposium on Principles of Database Systems (PODS'06), pages .....
  7. Logics over unranked trees: an overview.
  8. Leonid Libkin.
    Logical Methods in Computer Science, 2 (2006).
    (Note: a preliminary version was an invited paper at International Colloquium on Automata, Languages and Programming (ICALP'05), pages 35-50.)
  9. An information-theoretic approach to normal forms for relational and XML data.
  10. Marcelo Arenas and Leonid Libkin.
    Journal of the ACM, 52 (2005), 246-283.
    (Note: preliminary version in PODS'03, pages 15-26.)
  11. Temporal logics over unranked trees.
  12. Pablo Barcelo and Leonid Libkin.
    In Proceedings of the IEEE Symposium on Logic in Computer Science (LICS'05), pages 31-40.
  13. XML data exchange: consistency and query answering.
  14. Marcelo Arenas and Leonid Libkin.
    In Proceedings of the 24nd Symposium on Principles of Database Systems (PODS'05), pages 13-24.
  15. Locality of queries and transformations (invited paper).
  16. Leonid Libkin.
    In Proceedings of the 12th Workshop on Logic, Language, Information and Computation (WoLLIC'05), pages 109-120.
  17. Consistency of XML specifications.
  18. Marcelo Arenas, Wenfei Fan, and Leonid Libkin.
    In Inconsistency Tolerance, Springer LNCS vol. 3300, 2005, pages 15-41.
  19. Game-based notions of locality over finite models.
  20. Marcelo Arenas, Pablo Barcelo, and Leonid Libkin.
    In Proceedings of Conference for Computer Science Logic (CSL'04), Springer LNCS vol. 3210, pages 175-189.
  21. Locally consistent transformations and query answering in data exchange.
  22. Marcelo Arenas, Pablo Barcelo, Ronald Fagin, and Leonid Libkin.
    In Proceedings of the 23nd Symposium on Principles of Database Systems (PODS'04), pages 229-240.
  23. A normal form for XML documents.
  24. Marcelo Arenas and Leonid Libkin.
    ACM Transactions on Database Systems (TODS), 29 (2004), 195-232.
    (Note: preliminary version in PODS'02, pages 85-96.)
  25. Definable relations and first-order query languages over strings.
  26. Michael Benedikt, Leonid Libkin, Thomas Schwentick, and Luc Segoufin.
    Journal of the ACM, 50 (2003), 694-751.
  27. Embedded Finite Models and Constraint Databases.
  28. Leonid Libkin.
    To appear in a Springer volume based on the "Philadelphia Tutorials" on finite model theory.
  29. Logical definability and query languages over unranked trees.
  30. Leonid Libkin and Frank Neven.
    In Proceedings of the IEEE Symposium on Logic in Computer Science (LICS'03), pages 178--187.
  31. Expressive power of SQL.
  32. Leonid Libkin.
    Theoretical Computer Science, 296 (2003), 379-404.
    A shorter version was an invited paper at ICDT'01: 8th International Conference on Database Theory (Springer LNCS 1973, pages 1-21).
  33. Reachability and connectivity queries in constraint databases.
  34. Michael Benedikt, Martin Grohe, Leonid Libkin and Luc Segoufin.
    Journal of Computer and System Sciences, 66 (2003), 169-206.
    (Note: preliminary version in PODS'00, pages 104-115.)
  35. Variable independence for first-order definable constraints.
  36. Leonid Libkin.
    ACM Transactions on Computational Logic (TOCL), 4 (2003), 431-451.
    (Note: preliminary version in ICALP'00, pages 260-271.)
  37. Incremental recomputation in local languages.
  38. Guozhu Dong, Leonid Libkin, Limsoon Wong.
    Information and Computation, 181 (2003), 88-98.
  39. A collapse result for constraint queries over structures of small degree.
  40. Leonid Libkin.
    Information Processing Letters, 86 (2003), 277-281.
  41. On XML integrity constraints in the presence of DTDs.
  42. Wenfei Fan and Leonid Libkin.
    Journal of the ACM, 49 (2002), 368-406.
    (Note: preliminary version in PODS'01, pages 114-125.)
  43. Tree extension algebras: logics, automata, and query languages.
  44. Michael Benedikt and Leonid Libkin.
    In Proceedings of the IEEE Symposium on Logic in Computer Science (LICS'02), pages 203-212.
  45. On verifying consistency of XML specifications.
  46. Marcelo Arenas, Wenfei Fan and Leonid Libkin.
    In Proceedings of the 21th Symposium on Principles of Database Systems (PODS'02), pages 259-270.
  47. What's hard about XML Schema constraints?
  48. Marcelo Arenas, Wenfei Fan and Leonid Libkin.
    In Proceedings of Database and Expert Systems Applications (DEXA'02), Springer LNCS 2453, pages 269-278.
  49. Aggregate operators in constraint query languages.
  50. Michael Benedikt and Leonid Libkin.
    Journal of Computer and System Sciences, 64 (2002), 628-654.
    (Note: preliminary version in PODS'99, pages 102-113.)
  51. Lower bounds for invariant queries in logics with counting.
  52. Leonid Libkin and Limsoon Wong.
    Theoretical Computer Science, 288 (2002), 153-180.
  53. Logics with aggregate operators.
  54. Lauri Hella, Leonid Libkin, Juha Nurmonen, Limsoon Wong.
    Journal of the ACM, 48 (2001), 880-907.
    (Note: preliminary version in LICS'99, pages 35-44.)
  55. A model-theoretic approach to regular string relations.
  56. Michael Benedikt, Leonid Libkin, Thomas Schwentick and Luc Segoufin.
    In Proceedings of the IEEE Symposium on Logic in Computer Science (LICS'01), pages 431-440.
  57. String operations in query languages.
  58. Michael Benedikt, Leonid Libkin, Thomas Schwentick and Luc Segoufin.
    In Proceedings of the 20th Symposium on Principles of Database Systems (PODS'01), pages 183-194.
  59. On the orthographic dimension of definable sets.
  60. Stavros Cosmadakis, Gabriel Kuper and Leonid Libkin.
    Information Processing Letters, 79 (2001), 141-145.
  61. Logics capturing local properties.
  62. Leonid Libkin.
    ACM Transactions on Computational Logic (TOCL), 2 (2001), 135-153. 
    (Note: preliminary version in STACS'00, pages 217-229.)
  63. Relational queries over interpreted structures.
  64. Michael Benedikt and Leonid Libkin.
    Journal of the ACM, 47 (2000), 644-680.
  65. Variable independence, quantifier elimination, and constraint representations.
  66. Leonid Libkin.
    In Proceedings of the 27th International Colloquium on Automata, Languages and Programming (ICALP'00), pages 260-271.
  67. Logics with counting and local properties.
  68. Leonid Libkin.
    ACM Transactions on Computational Logic (TOCL), 1 (2000), 33-59.
  69. Safe constraint queries.
  70. Michael Benedikt and Leonid Libkin.
    SIAM Journal on Computing, 29 (2000), 1652-1682.
    (Note: preliminary version in PODS'98, pages 99-108.)
  71. Local properties of query languages.
  72. Guozhu Dong, Leonid Libkin and Limsoon Wong.
    Theoretical Computer Science, 239 (2000), 277-308.
    (Note: preliminary version in ICDT'97, pages 140-154.)
  73. Introduction.
  74. Gabriel Kuper, Leonid Libkin and Jan Paredaens.
    In Constraint Databases, Springer-Verlag, 2000, pages 1-16.
  75. Expressive power: the finite case.
  76. Michael Benedikt and Leonid Libkin.
    In Constraint Databases, Springer-Verlag, 2000, pages 55-87.
  77. Query safety with constraints.
  78. Michael Benedikt and Leonid Libkin.
    In Constraint Databases, Springer-Verlag, 2000, pages 109-129.
  79. Aggregate languages for constraint databases.
  80. Jan Chomicki and Leonid Libkin.
    In Constraint Databases, Springer-Verlag, 2000, pages 131-154.
  81. Counting and locality over finite structures: a survey.
  82. Leonid Libkin and Juha Nurmonen.
    In Generalized Quantifiers and Computation, Springer LNCS 1754, pages 18-50.
  83. Maintaining the transitive closure of graphs in SQL.
  84. Guozhu Dong, Leonid Libkin, Jianwen Su and Limsoon Wong.
    Int. Journal of Information Technology, 5 (1999), 46-78.
  85. Notions of locality and their logical characterizations over finite models.
  86. Lauri Hella, Leonid Libkin and Juha Nurmonen.
    Journal of Symbolic Logic, 64 (1999), 1751-1773.
  87. Query languages with arithmetic and constraint databases.
  88. Leonid Libkin.
    SIGACT News, (Database Theory Column), December 1999, pages 41-50.
  89. Some remarks on variable independence, closure, and orthographic dimension in constraint databases.
  90. Leonid Libkin.
    SIGMOD Record, 28 (1999), pages 24-28.
  91. What you can and cannot say in SQL, or proving folk theorems in database theory (abstract of invited talk).
  92. Leonid Libkin.
    In Proceedings of 15emes Journes Bases de Donnes Avances (BDA'99), p. 425.
  93. On the power of incremental evaluation in SQL-like languages.
  94. Leonid Libkin and Limsoon Wong.
    In Proceedings of Database Programming Languages (DBPL'99).
  95. Logics with counting, auxiliary relations, and lower bounds for invariant queries.
  96. Leonid Libkin.
    In Proceedings of IEEE Symposium on Logic in Computer Science (LICS'99), pages 316-325.
  97. Exact and approximate aggregation in constraint query languages.
  98. Michael Benedikt and Leonid Libkin.
    In Proceedings of the 18th Symposium on Principles of Database Systems (PODS'99), pages 102-113.
  99. Verifiable properties of database transactions.
  100. Michael Benedikt, Timothy Griffin and Leonid Libkin.
    Information and Computation, 147 (1998), 57-88.
    (Note: Preliminary version in PODS'96, pages 117-127.)
  101. On counting logics and local properties.
  102. Leonid Libkin.
    In Proceedings of IEEE Symposium on Logic in Computer Science (LICS'98), pages 501-512.
  103. Relational expressive power of constraint query languages.
  104. Michael Benedikt, Guozhu Dong, Leonid Libkin and Limsoon Wong.
    Journal of the ACM, 45 (1998), 1-34.
    (Note: Preliminary version in PODS'96, pages 5-16.)
  105. Unary quantifiers, transitive closure, and relations of large degree.
  106. Leonid Libkin and Limsoon Wong.
    In Proceedings of the 15th Symposium on Theoretical Aspects of Computer Science (STACS'98), Springer LNCS 1373, pp. 183-193.
  107. A semantics-based approach to design of query languages for databases with partial information.
  108. Leonid Libkin.
    In Semantics in Databases, Springer LNCS 1358, pp. 170-208.
  109. Models of approximation in databases.
  110. Leonid Libkin.
    Theoretical Computer Science, 190 (1998), 167-210.
  111. On the power of aggregation in relational query languages.
  112. Leonid Libkin and Limsoon Wong.
    In Database Programming Languages (DBPL'97), Springer LNCS 1369, pages 260-280.
  113. Incremental recomputation of recursive queries with nested sets and aggregate functions.
  114. Leonid Libkin and Limsoon Wong.
    In Database Programming Languages (DBPL'97), Springer LNCS 1369, pages 222-238.
  115. Query languages for bags and aggregate functions.
  116. Leonid Libkin and Limsoon Wong.
    Journal of Computer and System Sciences, 55 (2) (1997), 241-272.
  117. On the forms of locality over finite models.
  118. Leonid Libkin.
    In Proceedings of IEEE Symposium on Logic in Computer Science (LICS'97), pages 204-215.
  119. An improved algorithm for incremental recomputation of active relational expressions.
  120. Timothy Griffin, Leonid Libkin and Howard Trickey.
    IEEE Transactions on Knowledge and Data Engineering, 9 (3) (1997), 508-511.
  121. Languages for relational databases over interpreted structures.
  122. Michael Benedikt and Leonid Libkin.
    In Proceedings of the 16th Symposium on Principles of Database Systems (PODS'97), pages 87-98.
  123. Tractable iteration mechanisms for bag languages.
  124. Latha Colby and Leonid Libkin.
    In Proceedings of the 6th International Conference on Database Theory (ICDT'97), Springer LNCS 1186, pp. 461-475.
  125. Query languages for bags: expressive power and complexity.
  126. Stephane Grumbach, Leonid Libkin, Tova Milo and Limsoon Wong.
    SIGACT News, (Database Theory Column), June 1996, pages 30-37.
  127. On the structure of queries in constraint query languages.
  128. Michael Benedikt and Leonid Libkin.
    In Proceedings of IEEE Symposium on Logic in Computer Science (LICS'96), pages 25-34.
  129. A query language for multidimensional arrays: design, implementation and optimization techniques.
  130. Leonid Libkin, Rona Machlin and Limsoon Wong.
    In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD'96), pages 228-239.
  131. Algorithms for deferred view maintenance.
  132. Latha Colby, Timothy Griffin, Leonid Libkin, Inderpal Mumick and Howard Trickey.
    In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD'96), pages 469-480.
    (Note: reprtinted in Materialized Views, The MIT Press, 1999.)
  133. Query language primitives for programming with incomplete databases.
  134. Leonid Libkin.
    In Proceedings of DBPL'95.
  135. On impossibility of decremental recomputation of recursive queries in relational calculus and SQL.
  136. Guozhu Dong, Leonid Libkin and Limsoon Wong.
    In Proceedings of DBPL'95.
  137. Semantic representations and query languages for or-sets.
  138. Leonid Libkin and Limsoon Wong.
    Journal of Computer and System Sciences, 52 (1) (1996), 125-142. (Note: Preliminary version in PODS'93, pp. 37-48.)
  139. On representation and querying incomplete information in databases with bags.
  140. Leonid Libkin and Limsoon Wong.
    Information Processing Letters, 56 (4) (1995), 209-214.
  141. Trees as semilattices.
  142. Leonid Libkin and Vladimir Gurvich.
    Discrete Mathematics, 145 (1995), 321-327.
  143. Approximation in databases.
  144. Leonid Libkin.
    In Proceedings of the International Conference on Database Theory (ICDT'95), Springer LNCS 893, pp. 411-424.
  145. Normalizing incomplete databases.
  146. Leonid Libkin.
    In Proceedings of the 14th Symposium on Principles of Database Systems (PODS'95), pp. 219-230.
  147. Incremental maintenance of views with duplicates.
  148. Timothy Griffin and Leonid Libkin.
    In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD'95), pp. 328-339. (Note: reprtinted in Materialized Views, The MIT Press, 1999.)
  149. Interfacing HOL90 with a functional database query language.
  150. Elsa Gunter and Leonid Libkin.
    In Proceedings of the International Workshop on Higher Order Logic Theorem Proving and its Applications, 1995, Springer LNCS 971, pp. 328-339.
  151. Direct decompositions of atomistic algebraic lattices.
  152. Leonid Libkin.
    Algebra Universalis, 33 (1995), 127-135.
  153. n-distributivity, dimension and Caratheodory's theorem.
  154. Leonid Libkin.
    Algebra Universalis, 34 (1995), 72-95.
  155. Conservativity of nested relational calculi with internal generic functions.
  156. Leonid Libkin and Limsoon Wong.
    Information Processing Letters, 49 (1994), 273-280.
  157. Comprehension syntax.
  158. Peter Buneman, Leonid Libkin, Dan Suciu, Val Tannen and Limsoon Wong.
    SIGMOD Record, 23 (1994), 87-96.
  159. Some properties of query languages for bags.
  160. Leonid Libkin and Limsoon Wong.
    In Proceedings of the Workshop on Database Programming Languages, Springer Verlag, 1994, pp. 97--114.
  161. Aggregate functions, conservative extension and linear order.
  162. Leonid Libkin and Limsoon Wong.
    In Proceedings of the Workshop on Database Programming Languages, Springer Verlag, 1994, pp. 282--294.
  163. New techniques for studying set languages, bag languages, and aggregate functions.
  164. Leonid Libkin and Limsoon Wong.
    In Proceedings of the 13th Symposium on Principles of Database Systems (PODS'94), pp. 155--166.
  165. OR-SML: A functional database programming language with support for disjunctive information.
  166. Elsa Gunter and Leonid Libkin.
    In Proceedings of the International Conference on Database and Expert Systems Applications, Springer LNCS 856, pp. 641-650.
  167. The lattice of subsemilattices of a semilattice.
  168. Leonid Libkin and Ilya Muchnik.
    Algebra Universalis, 31 (1994), 252--255.
  169. Aspects of Partial Information in Databases (PhD Thesis).
  170. Leonid Libkin. University of Pennsylvania, 1994.
  171. Direct product decompositions of lattices, closures and relation schemes.
  172. Leonid Libkin.
    Discrete Mathematics,
    112 (1993), 119-138.
  173. A remark about algebraicity in complete partial orders.
  174. Leonid Libkin.
    Journal of Pure and Applied Algebra, 86 (1993), 75-77.
  175. On the interaction between closure operations and choice functions with applications to relational databases.
  176. Janos Demetrovics, Gusztav Hencsey, Leonid Libkin and Ilya Muchnik.
    Acta Cybernetica, 10 (3) (1992), 129-139.
  177. Normal form relation schemes: a new characterization.
  178. Janos Demetrovics, Gusztav Hencsey, Leonid Libkin and Ilya Muchnik.
    Acta Cybernetica, 10 (3) (1992), 141-153.
  179. Functional dependencies in relational databases: a lattice point of view.
  180. Janos Demetrovics, Leonid Libkin and Ilya Muchnik.
    Discrete Applied Mathematics, 40 (1992), 155-185. (Note: Preliminary version in MFDBS'89.)
  181. An elementary proof that upper and lower powerdomain constructions commute.
  182. Leonid Libkin.
    Bulletin of the EATCS, 48 (1992), 175-177.
  183. Decomposition of domains.
  184. Achim Jung, Leonid Libkin and Hermann Puhlmann.
    In Proceedings of the Conference on Mathematical Foundations of Programming Semantics (MFPS'91), Springer LNCS 598, pp. 235-258.
  185. Quasiconvex analysis on semilattices and absolutely determined matrices.
  186. Vladimir Gurvich and Leonid Libkin.
    Soviet Mathematics Doklady, 44 (1) (1992), 20-25.
  187. Parallel axiom in convexity lattices.
  188. Leonid Libkin.
    Periodica Mathematica Hungarica, 24 (1) (1992), 1-12.
  189. Separatory sublattices and subsemilattices.
  190. Leonid Libkin and Ilya Muchnik.
    Studia Scientiarum Mathematicarum Hungarica, 27 (1992), 471-477.
  191. A relational algebra for complex objects based on partial information.
  192. Leonid Libkin.
    In Proceedings of the Conference on Mathematical Fundamentals of Database Systems (MFDBS'91), Springer LNCS 495, pp. 29-43.
  193. On relational database schemes having unique minimal key.
  194. Joachim Biskup, Janos Demetrovics, Leonid Libkin and Ilya Muchnik.
    Journal of Information Processing and Cybernetics, 27 (4) (1991), 217-225.
  195. Separability in lattices.
  196. Leonid Libkin.
    In Ordered Sets and Lattices (Russian), Saratov, 1991, pp. 78-88.
  197. Absolutely determined matrices.
  198. Vladimir Gurvich and Leonid Libkin.
    Mathematical Social Science, 20 (1) (1990), 1-18.
  199. Investigations on Armstrong relations, dependency inference and excluded functional dependencies.
  200. Georg Gottlob and Leonid Libkin.
    Acta Cybernetica, 9 (4) (1990), 385-402.
  201. Quasilinear monotone systems.
  202. Leonid Libkin, Ilya Muchnik and Leonid Schvartzer.
    Automation and Remote Control, 50 (9) (1989), 1249-1259.
  203. Quasilinear set-functions and absolute definite matrices.
  204. Vladimir Gurvich and Leonid Libkin.
    Automation and Remote Control, 50 (12) (1989), 1706-1709.
  205. Halfspaces and hyperplanes in convexity lattices.
  206. Leonid Libkin and Ilya Muchnik.
    Institute of Mathematics, Budapest, Hungary, 1989.
  207. Functional dependencies and the semilattice of closed classes.
  208. Janos Demetrovics, Leonid Libkin and Ilya Muchnik.
    In Proceedings of the Conference on Mathematical Fundamentals of Database Systems (MFDBS'89), Springer LNCS 364, pp. 136-147.
  209. Recognition of choice functions.
  210. Leonid Libkin.
    Automation and Remote Control, 49 (10) (1988), 1355-1358.
  211. Minimal sets of choice functions generating the basic classes.
  212. Leonid Libkin.
    Automation and Remote Control, 49 (12) (1988), 1662-1665.
  213. Separatory subsemilattices and their properties.
  214. Leonid Libkin and Ilya Muchnik.
    MTA SZTAKI Kozlemenyek, 39 (1988), 83-92.
  215. Separation theorems for lattices.
  216. Leonid Libkin.
    MTA SZTAKI Kozlemenyek, 39 (1988), 93-100.
  217. On a subsemilattice-lattice of a semilattice.
  218. Leonid Libkin and Ilya Muchnik.
    MTA SZTAKI Kozlemenyek, 39 (1988), 101-110.
  219. Pseudocriteria induced by set-functions.
  220. Leonid Libkin and Ilya Muchnik.
    In Proceedings of the Conference on Decision-Making (Russian), Moscow, 1988, pp. 124-125.
  221. Algebraic methods for construction and analysis of the choice function classes.
  222. Leonid Libkin.
    In Fuzzy Sets and Individual Choice (Russian), Moscow, 1987, pp. 46-53.