Publications

Journal Articles


1. Kanellakis, P.C., Ramaswamy, S., Vengroff, D.E., Vitter, J.S.
``Indexing for Data Models with Constraints and Classes''
Accepted in October 1994 by the Journal of Computer and System Sciences, special issue edited by C. Beeri. To appear.

Note: an extended abstract appeared in the proceedings of the
12th ACM PODS Symposium on the Principles of Database Systems, pp. 233-243, Washington DC USA, June 1993.

2. Abiteboul, S., Kanellakis, P.C., Ramaswamy, S., Waller, E.
``Method Schemas''
Accepted in August 1994 by the Journal of Computer and System Sciences. To appear.

Note: an extended abstract appeared in the proceedings of the
9th ACM PODS Symposium on the Principles of Database Systems, Nashville Tennessee USA, pp. 16-28, March 1990. Extended abstract reprinted as Chapter 6 in book collection [35] below.

3. Kanellakis, P.C., Shvartsman, A.A.
``Efficient Parallel Algorithms on Restartable Fail-stop Processors''
Accepted in August 1994 by the Journal of Algorithms. To appear.

Note: an extended abstract appeared in the proceedings of the
10th ACM PODC Symposium on the Principles of Distributed Computing, Monteal Quebec Canada, pp. 23-37, August 1991.

4. Hillebrand, G., Kanellakis, P.C., Mairson, H.G., Vardi, M.Y.
``Undecidable Boundedness Problems for Datalog Programs''
Journal of Logic Programming vol. 25, no. 2, pp. 163-190, November 1995

Note: an extended abstract appeared in the proceedings of the
10th ACM PODS Symposium on the Principles of Database Systems , Denver Colorado USA, pp. 1-13, June 1991.

5. Kanellakis, P.C., Kuper, G., Revesz, P.Z.
``Constraint Query Languages''
Journal of Computer and System Sciences , special issue edited by Y.Sagiv, vol. 51, no. 1, pp. 26-52, August 1995

Note: an extended abstract appeared in the proceedings of the
9th ACM PODS Symposium on the Principles of Database Systems , Nashville Tennessee USA, pp. 299-314, March 1990.

6. Kanellakis, P.C., Michailidis, D., Shvartsman, A.A.
``Controlling Memory Access Concurrency in Efficient Fault Tolerant Parallel Algorithms''
Nordic Journal of Computing, no. 2, pp. 146-180, May 1995

Note: an extended abstract appeared in the proceedings of the
7th Inter. Workshop on Distributed Algorithms , Springer-Verlag LNCS 725, pp. 99-114, Lausanne, Switzerland, September 1993

Note: full version submitted to the
Journal of Parallel and Distributed Computing.

7. Kanellakis, P.C., Shvartsman, A.A.
``Efficient Parallel Algorithms can be made Robust''
Distributed Computing, vol. 5, pp. 201-217, 1992

Note: an extended abstract appeared in the proceedings of the
8th ACM PODC Symposium on the Principles of Distributed Computing , pp. 211-222, Edmonton Canada, August 1989.


8. Abiteboul, S., Kanellakis, P.C.
``The Two Facets of Object-Oriented Data Models''
IEEE Data Engineering Bulletin, special issue edited by R. Agrawal, vol. 14, no. 2, pp. 3-8, June 1991

9. Buchsbaum, A., Kanellakis, P.C., Vitter, J.S.
``A Data Structure for Arc Insertion and Regular Path Finding''
Annals of Mathematics and AI, special issue edited by S. Naqvi and D. Tsur, vol. 3, no. 2-4, pp. 187-211, March 1991

Note: an extended abstract appeared in the proceedings of the
1st ACM-SIAM Symposium on Discrete Algorithms, San Francisco California USA, pp. 22-2, January 1990.

10. Abiteboul, S., Kanellakis, P.C., Grahne, G.
``On the Representation and Querying of Sets of Possible Worlds''
Theoretical Computer Science, special issue edited by G. Gardarin, vol. 78, pp. 159-187, January 1991

Note: an extended abstract appeared in the proceedings of the
ACM SIGMOD Symposium on the Management of Data, pp. 10-19, San Francisco California USA, May 1987.

11. Beeri, C., Kanellakis, P.C., Bancilhon, F., Ramakrishnan, R.
``Bounds on the Propagation of Selection into Logic Programs''.
Journal of Computer and System Sciences, special issue edited by M.Y. Vardi, vol. 41, no. 2, pp. 157-180, October 1990

Note: an extended abstract appeared in the proceedings of the
6th ACM PODS Symposium on the Principles of Database Systems, pp. 214-227, San Diego California USA, March 1987.

12. Kanellakis, P.C., Smolka, S.A.
``CCS Expressions, Finite State Processes and Three Problems of Equivalence''
Information and Computation, vol. 86, no. 1, pp. 43-68, May 1990

Note: an extended abstract appeared in the proceedings of the
2nd ACM PODC Symposium on the Principles of Distributed Computing , pp. 228-240, Montreal Canada, August 1983.

13. Cosmadakis, S.S., Kanellakis, P.C., Vardi, M.Y.
``Polynomial-Time Implication Problems for Unary Inclusion Dependencies''
JACM, vol. 37, no. 1, pp. 15-47, January 1990

Note: an extended abstract appeared in the proceedings of the
15th ACM STOC Symposium on the Theory of Computing, pp. 264-277, Boston Massachusetts USA, April 1983.

14. Kanellakis, P.C., Revesz, P.
``On the Relationship of Congruence Closure and Unification''
Journal of Symbolic Computation, special issue edited by C. Kirchner, vol. 7, no. 3-4, pp. 427-444, March-April 1989

Note: an extended abstract appeared in the proceedings of the
1st DBPL Workshop on Database Programming Languages, F. Bancilhon and P. Buneman editors, Roscoff France, September 1987.

15. Dwork, C., Kanellakis, P.C., Stockmeyer, L.
``Parallel Algorithms for Term Matching''
SIAM Journal of Computing, vol. 17, no. 4, pp. 711-731, August 1988

Note: an extended abstract appeared in the proceedings of the
8th CADE Conference on Automated Deduction, Springer-Verlag Lecture Notes in Computer Science 230, pp. 416-430, Oxford England, July 1986.

16. Kanellakis, P.C., Smolka, S.A.
``On the Analysis of Cooperation and Antagonism in Networks of Communicating Processes''
Algorithmica, special issue edited by J.S. Vitter, no. 3, pp. 421-450, August 1988

Note: an extended abstract appeared in the proceedings of the
4th ACM PODC Symposium on the Principles of Distributed Computing, pp. 23-39, Minaki Canada, August 1985.

17. Cosmadakis, S.S., Kanellakis, P.C., Spyratos, N.
``Partition Semantics for Relations''
Journal of Computer and System Sciences, special issue edited by J.D. Ullman, vol. 33, no. 2, pp. 203-233, October 1986

Note: an extended abstract appeared in the proceedings of the
4th ACM PODS Symposium on the Principles of Database Systems, pp. 261-275, Portland Oregon USA, March 1985.

18. Kanellakis, P.C., Papadimitriou, C.H.
``The Complexity of Distributed Concurrency Control''
SIAM Journal of Computing, vol. 14, no. 1, pp. 52-75, February 1985

Note: an extended abstract appeared in the proceedings of the
22nd IEEE FOCS Symposium on the Foundations of Computer Science, pp. 185-197, Nashville Tennessee, October 1981.

19. Dwork, C., Kanellakis, P.C., Mitchell, J.C.
``On the Sequential Nature of Unification''
Journal of Logic Programming, vol. 1, no. 1, pp. 35--50, June 1984

20. Papadimitriou, C.H., Kanellakis, P.C.
``On Concurrency Control by Multiple Versions''
ACM Transactions on Database Systems, vol. 9, no. 1, pp. 89-99, March 1984

Note: an extended abstract appeared in the proceedings of the
1st ACM PODS Symposium on the Principles of Database Systems, pp. 76-83, LA California USA, March 1982.

21. Kanellakis, P.C., Papadimitriou, C.H.
``Is Distributed Locking Harder?''
Journal of Computer and System Sciences, special issue edited by A.V. Aho, vol. 28, no. 1, pp. 103-120, February 1984

Note: an extended abstract appeared in the proceedings of the
1st ACM PODS Symposium on the Principles of Database Systems, pp. 76-83, LA California USA, March 1982.

22. Kanellakis, P.C.
``On the Computational Complexity of Cardinality Constraints in Relational Databases''
Information Processing Letters, vol. 11, no. 2, pp. 98-101, November 1980

23. Kanellakis, P.C., Papadimitriou, C.H.
``Local Search for the Asymmetric Traveling Salesman Problem''
Operations Research, vol. 27, no. 3, pp. 533-549, July 1980

Note: an extended abstract appeared in the proceedings of the
ORSA TIMS, LA California USA, 1978.

24. Papadimitriou, C.H., Kanellakis, P.C.
``Flowshop Scheduling with Limited Temporary Storage''
Journal of the ACM, vol. 27, no. 3, pp. 533-549, July 1980

Note: an extended abstract appeared in the proceedings of the
16th Allerton Conference on Communication, Control and Computing , pp. 214-224, Allerton Illinois USA, October 1978.

Book Chapters


25. Kanellakis, P.C., Shvartsman, A.A.
``Fault-Tolerance and Efficiency in Massively Parallel Algorithms''
Chapter 2.2 in Foundations of Dependable Computing: Paradigms for Dependable Applications,
G. Koob, C. Lau editors, Kluwer Academic Publishers, pp. 125-154, 1994

26. Hillebrand, G., Kanellakis, P.C., Ramaswamy, S.
``Functional Programming Formalisms for OODB Methods''
Chapter 2.3 in Advances in Object-Oriented Databases,
Asuman Dogac, M. Tamerozsu, Alexandros Biliris, Timos Sellis editors, Springer-Verlag, Series F: Computer and Systems Sciences, vol. 130, pp. 73-98, 1994.

Note: NATO ASI Series, Workshop on OODBs, Kusadasi, Turkey, August 1993.

27. Kanellakis, P.C., Lecluse, C., Richard, P.
``Introduction to the (O_2) Data Model''
Chapter 3 in Building an Object-Oriented Database System: the story of O_2,
F. Bancilhon, C. Delobel, P.C. Kanellakis editors, Morgan-Kaufmann, pp. 61-76, 1992

Note: this is formal definition of the data model as implemented in the O_2 system.

28. Kanellakis, P.C., Mairson H.G., Mitchell J.C.
``Unification and ML Type Reconstruction''
Chapter 13 in Computational Logic, Essays in Honor of Alan J. Robinson,
J-L. Lassez and G. Plotkin editors, MIT Press, pp. 444-478, 1991

Note: part of this paper appeared as extended abstract:
``Polymorphic Unification and ML Typing'', by Kanellakis, P.C., Mitchell, J.C., in the proceedings of the
16th ACM POPL Symposium on the Principles of Programming Languages , pp. 105-115, Austin Texas USA, January 1989.

29. Kanellakis, P.C.
```Elements of Relational Database Theory''
Chapter 17 in The Handbook of Theoretical Computer Science,
Volume B, A.R. Meyer, M. Nivat, M.S. Paterson, D. Perrin and J. van Leeuwen editors, North Holland, pp. 1075-1144, 1990

30. Goldman, K.J., Goldman, S.A., Kanellakis, P.C., Zdonik, S.B.
``ISIS: Interface for a Semantic Information System''
Chapter 8.1 in Readings on Object-Oriented Databases,
S.B. Zdonik and D. Maier editors, Morgan Kaufmann, pp. 522-536, 1989

Note: reprinted from the proceedings of the
ACM SIGMOD Symposium on the Management of Data, pp. 328-342, Austin Texas USA, May 1985.

31. Kanellakis, P.C.
``Logic Programming and Parallel Complexity''
Chapter 14 in Foundations of Deductive Databases and Logic Programming,
J. Minker editor, pp. 547-586, Morgan Kaufmann, 1988

Note: an extended abstract appeared in the proceedings of the
1st ICDT International Conference on Database Theory, Springer-Verlag Lecture Notes in Computer Science 243, pp. 1-30, Rome Italy, September 1986.

32. Cosmadakis, S.S., Kanellakis, P.C.
``Functional and Inclusion Dependencies: A Graph Theoretic Approach''
Chapter 7 in The Theory of Databases, Advances in Computing Research vol. III,
P.C. Kanellakis and F.C. Preparata editors, pp. 163-184, JAI Press, 1986

Note: an extended abstract appeared in the proceedings of the
3rd ACM PODS Symposium on the Principles of Database Systems, pp. 29-37, Waterloo Canada, April 1984.

33. Smolka, S.A., Kanellakis, P.C.
``Recent Results in the Static Analysis of Communicating Finite State Processes''
Chapter 10 in Current Advances in Distributed Computing and Communications,
Y. Yemini editor, pp. 208-234, Computer Science Press, 1986

Conference Abstracts

This list does not include papers that were later published as journal articles or book chapters; such papers are mentioned next to the corresponding journal article or book chapter listing. For some of the conference publications below, full versions have been submitted for journal or book publication and are currently in review. This is noted below the corresponding entries.

34. Goldin, D.Q., Kanellakis, P.C.
``On Similarity Queries for Time-Series Data: Constraint Specification and Implementation''
1st International Conference on the Principles and Practice of Contraint Programming, LNCS 976, pp. 137-153, Cassis France, September 1995

35. Ramaswamy, S., Kanellakis, P.C.
``OODB Indexing by Class-Division''
ACM SIGMOD Symposium on the Management of Data, San Jose CA USA, pp. 139-150, May 1995

36. Kanellakis, P.C., Michailidis, D., Shvartsman, A.A.
``Concurrency = Fault-Tolerance in Parallel Computation''
Invited paper, 5th International Conference on Concurrency Theory, LNCS 836, Uppsala Sweden, pp. 242-266, August 1994

37. Kanellakis, P.C., Hillebrand, G., Mairson, H.G.
``An Analysis of Core-ML: Expressive Power and Type Inference''
Invited paper, International Colloquium on Automata, Languages and Programming, LNCS 820, Jerusalem Israel, pp. 83-105, July 1994

38. Kanellakis, P.C., Goldin, D.Q.
``Constraint Programming and Database Query Languages''
Invited paper, Symposium on Theoretical Aspects of Computer Software, LNCS 789, pp. 96-120, Sendai Japan, April 1994

Note: full version invited to the 1st issue of Constraints Journal, E. Freuder editor. Currently under revision.

39. Hillebrand, G., Kanellakis, P.C.
``Functional Database Query Languages as Typed Lambda Calculi of Fixed Order''
13th ACM PODS Symposium on the Principles of Database Systems, pp. 222-231, June 1994

Note: full version invited to JCSS special issue on 13th PODS.

40. Hillebrand, G., Kanellakis, P.C., Mairson, H.G.
``Database Query Languages Embedded in the Typed Lambda Calculus''
8th IEEE LICS Symposium on Logic in Computer Science, pp. 332-343, Montreal Canada, June 1993

Note: full version invited to Information and Computation special issue on 8th LICS. Accepted subject to minor revision.

Note: Accepted subject to revisions to the Journal of the ACM. Currently under revision.

41. Abiteboul S., Kanellakis P.C.
``Object Identity as a Query Language Primitive''
ACM SIGMOD Symposium on the Management of Data, pp. 159-173, Portland Oregon USA, June 1989.

Note: full version is available as Brown Univ. Tech. Rep. CS-89-26.
Accepted subject to revisions to the Journal of the ACM. Currently under revision.

42. Kanellakis, P.C., Abiteboul, S.
``A Logical Query Language with Object Identity and Strong Typing''
Invited paper, 6th International Conference on Logic Programming, MIT Press, pp. 675-692, Lisbon Portugal, June 1989

43. Cosmadakis, S.S., Gaifman H., Kanellakis, P.C., Vardi, M.Y.
``Decidable Optimization Problems for Database Logic Programs''
20th ACM STOC Symposium on the Theory of Computing, pp. 477-490, Chicago Illinois USA, May 1988

44. Cosmadakis, S.S., Kanellakis, P.C.
``Parallel Evaluation of Recursive Rule Queries''
5th ACM PODS Symposium on the Principles of Database Systems, pp. 280-293, Boston Massachusetts, March 1986

45. Cosmadakis, S.S., Kanellakis, P.C.
``Equational Theories and Database Constraints''
17th ACM STOC Symposium on the Theory of Computing, pp. 273-285, Providence Rhode Island USA, May 1985

46. Cosmadakis, S.S., Kanellakis, P.C.
``Two Applications of Equational Theories to Database Theory''
1st International Conference on Rewriting Techniques and Applications, Springer-Verlag Lecture Notes in Computer Science 202, pp. 107-124, Dijon France, May 1985

47. Yannakakis, M., Kanellakis, P.C., Cosmadakis, S.S., Papadimitriou, C.H.
``Cutting and Partitioning a Graph after a Fixed Pattern''
10th ICALP International Colloquium on Automata, Languages and Programming,
Springer-Verlag Lecture Notes in Computer Science 154, pp. 712-722, Barcelona Spain, July 1983

48. Karatzas, I., Protonotarios, E.N., Kanellakis, P.C.
``Easy-to-Test Criteria for Weak Stochastic Stability of Dynamical Systems''
John Hopkins Conference on Information Sciences and Systems, single page abstract only, p. 535, Baltimore Maryland USA, 1978

Miscellaneous Manuscripts


49. Three SIGACT News columns on Database Theory:
(1) vol. 20, no. 4 pp. 17-23, 1989
(2) vol. 21, no. 3, pp. 9-18, 1990
(3) vol. 25, no. 4, 1994

50. Shvartsman A.A., Kanellakis, P.C.
``Fault-Tolerant and Efficient Parallel Computation''
Monograph manuscript in preparation, to be published by Kluwer, 1996

51. Kanellakis, P.C.
``Database Theory''
Manuscript in preparation, Chapter in Handbook of Computer Science, CRC Press, 1996

52. Afrati, F., Goldin, D., Kanellakis, P.C.
``Efficient Parallelism for Structured Data: Directed Reachability in S-P Dags''
Brown Univ. Tech. Rep. CS-88-07, January 1988

53. Kanellakis, P.C. ``An Election Problem in a Network: Formulation and Communication Complexity Analysis''
Unpublished manuscript, MIT, May 1978.