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