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