Publications
Last updated: February 1997
Below is the list of my papers. Most papers written before May 1994
are available from
here or from
here . I haven't made papers written after 1994 available here, but my
co-authors,
Michael Benedikt,
Guozhu Dong,
Tim Griffin and
Limsoon Wong,
are probably doing much better job maintaining their web pages.
If you want to get
some of my papers, and those web pages are of no help, please
email me.
- Leonid Libkin.
On the forms of locality over finite models.
In Proceedings of IEEE Symposium on Logic in
Computer Science (LICS'97),
to appear.
- Michael Benedikt and Leonid Libkin.
Languages for relational databases over interpreted structures.
In Proceedings of the
16th Symposium on Principles of Database Systems (PODS'97),
to appear.
- Leonid Libkin.
Models of approximation in databases.
Theoretical Computer Science,
to appear.
- Leonid Libkin and Limsoon Wong.
Query languages for bags and aggregate functions.
Journal of Computer and System Sciences,
to appear.
-
An improved algorithm for incremental recomputation of
active relational expressions.
Timothy Griffin, Leonid Libkin and Howard Trickey.
IEEE Transactions on Knowledge and Data Engineering,
to appear.
-
Local properties of query languages.
Guozhu Dong, Leonid Libkin and Limsoon Wong.
In Proceedings of the 6th International Conference on Database
Theory (ICDT'97),
Springer LNCS 1186, pp. 140-154.
-
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.
-
Relational expressive power of constraint query languages.
Michael Benedikt, Guozhu Dong, Leonid Libkin and Limsoon Wong.
In Proceedings of the
15th Symposium on Principles of Database Systems (PODS'96),
pages 5-16.
-
Verifiable properties of database transactions.
Michael Benedikt, Timothy Griffin and Leonid Libkin.
In Proceedings of the
15th Symposium on Principles of Database Systems (PODS'96),
pages 117-127.
-
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.
-
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.
-
A semantics-based approach to design of query languages for
databases with partial information.
Leonid Libkin.
In Proceedings of the
Workshop
on Semantics in Databases,
Prague, 1995, pp. 63-80.
-
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.
-
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.
-
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.