Publications of Vaughan Pratt

Note: Most of these papers since 1985 are available in PDF and/or Postscript via http://boole.stanford.edu/abstracts.html.

Pratt, V.R. Linear process algebra, ICDCIT'11 Proc. 7th Int. Conf. on Distributed Computing and Internet Technology, 92-111 (Feb. 2011), Springer-Verlag, Berlin, Heidelberg.

Pratt, V.R. Communes via Yoneda, from an Elementary Perspective, Fundamenta Informaticae 103, 203–218, DOI 10.3233/FI-2010-325, IOS Press, 2010.

Pratt, V.R., Factoring Heron, The College Mathematics Journal, 40:15-16, 2009.

Thrun, S. et al, Stanley: The Robot that Won the DARPA Grand Challenge, Journal of Field Robotics 23(9), 661-692 (2006), Wiley Periodicals Inc.

Pratt, V.R., Transition and Cancellation in Concurrency and Branching Time, Math. Structures in Comp. Sci., 13:4, 485-529, August 2003.

Pratt, V.R., Comonoids in chu: A large cartesian closed sibling of topological spaces, Proc. Workshop on Coalgebraic Methods in CS (CMCS'03), Elsevier ENTCS 82:1, 1-12, July 2003.

Pratt, V.R., Chu spaces as a semantic bridge between linear logic and mathematics, Invited paper, special issue on Linear Logic, ed. M. Okada, TCS 294:3, 439-471, February 2003.

Pratt, V.R., Event-state duality: the enriched case, Keynote paper, Proc. CONCUR'02, Springer-Verlag LNCS 2421, 41-56, Brno, Czech Republic, August 2002.

Pavlovic, D. and Pratt, V.R., The Continuum as a Final Coalgebra, Invited paper, special issue on Coalgebraic Methods in Computer Science, TCS 280(1-2):105-122, May 2002.

Pratt, V.R., Software Geography: Its Physical and Economic Aspects, Keynote paper, Proc. SOFSEM'01, Springer-Verlag LNCS 2234, Piestany, Slovakia, November 2001.

Pratt, V.R., Orthocurrence as both Interaction and Observation, Invited paper, Proc. Workshop on Spatial and Temporal Reasoning (ed. R. Rodriguez and F. Anger), IJCAI'01, Seattle, August 2001.

Pratt, V.R., Higher Dimensional Automata Revisited, Invited paper, special issue on Higher Dimensional Automata, ed. E. Goubault, MSCS 10:4, 525-548, August 2000.

DeFouw, G. and Pratt, V.R., The Matchbox PC: A Small Wearable Platform, Third International Symposium on Wearable Computing, 172--175, San Francisco, October 1999.

Devarajan, H., Hughes, D., Plotkin, G.D., and Pratt, V.R., Full completeness of the multiplicative linear logic of Chu spaces, Proceedings 14th Annual IEEE Symposium on Logic in Computer Science (LICS'99, Ed. G. Longo), Trento, Italy, July 1999.

Pratt, V.R., Chu Spaces, Notes for School on Category Theory and Applications, University of Coimbra, Portugal, July 13-17, 1999.

Pavlovic, D. and Pratt, V.R., On Coalgebra of Real Numbers, Proceedings Workshop on Coalgebraic Methods in Computer Science (CMCS'99), Amsterdam, March 1999.

Pratt, V.R., Chu Spaces from the Representational Viewpoint, Invited paper, volume of Annals of Pure and Applied Logic honoring R. Parikh, 96:319-313, 1999.

Pratt, V.R., Proc. 13th Annual IEEE Symposium on Logic in Computer Science (editor), Brunswick, NJ, July, 1998.

Pratt, V.R., Types as Processes, via Chu spaces, Invited paper, Proceedings EXPRESS'97: Fourth Workshop on Expressiveness in Concurrency, Electronic Notes in Theoretical Computer Science, Santa Margherita, Italy, September 1997, ENTCS.

Pratt, V.R., Towards Full Completeness for the Linear Logic of Chu Spaces, Proceedings, 13th Annual Conference on Mathematical Foundations of Programming Semantics, Pittsburgh, March 1997.

Plotkin, G.D. and Pratt, V.R,, Teams can see pomsets, Workshop on Partial Order Methods in Verification (Eds. Peled, Pratt, Holzmann), Amer. Math. Soc., DIMACS series Vol. 29, 1997.

Peled, D.A, Pratt, V.R., and Holzmann, G.J. (editors), Partial Order Methods in Verification, Amer. Math. Soc., DIMACS series Vol. 29, 1997.

Pratt, V.R., Broadening the Denotational Semantics of Linear Logic, Invited paper, Proceedings Linear Logic'96, Tokyo, April 1996. To appear in J. Theoretical Computer Science.

Pratt, V.R. and J. Tiuryn, Satisfiability of Inequalities in a Poset, Fundamenta Informaticae, 28:1,2 (Nov. 1996), 165-182.

Pratt, V.R. Chu Spaces and Their Interpretation as Concurrent Objects, Invited paper, Computer Science Today: Recent Trends and Developments (ed. J. van Leeuwen), 392-405, Springer-Verlag LNCS 1000 (Commemorative Volume), 1995.

Pratt, V.R., The Stone Gamut: A Coordinatization of Mathematics, Proc. LICS'95, 444-454, San Diego, CA, June 1995.

Pratt, V.R., Anatomy of the Pentium Bug, Invited Paper, Proc. TAPSOFT'95, LNCS 915, 97-107, Aarhus, Denmark, May 1995.

Pratt, V.R., Rational Mechanics and Natural Mathematics, Invited paper, Proc. TAPSOFT'95, LNCS 915, 108-122, Aarhus, Denmark, May 1995.

Coe, T., Mathisen, T., Moler, C., and Pratt, V., Computational Aspects of the Pentium Affair, IEEE J. Computational Sci. and Eng., 2:1, 18-30, Spring 1995.

Pratt, V.R., Chu Spaces: Automata with Quantum Aspects, Proc. Workshop on Physics and Computation (PhysComp'94), 186-195, Dallas, Nov. 1994.

Pratt, V.R., Time and Information in Sequential and Concurrent Computation, Proc. Theory and Practice of Parallel Programming (TPPP'94), 1-24, Sendai, Japan, Nov. 1994.

Gupta, V. and V.R. Pratt, Gates Accept Concurrent Behavior, Proc. of 34th Ann. IEEE Symp. on Foundations of Computer Science, 62-71, November 1993.

Pratt, V.R., The Second Calculus of Binary Relations, Proc. 18th International Symposium on Mathematical Foundations of Computer Science, Gdansk, Poland, Springer-Verlag, 142-155, September 1993.

Pratt, V.R., A Roadmap of Some Two-Dimensional Logics, Proc. Workshop on Logic and Information Flow (ed. J. van Eijck and A. Visser), 149-162, MIT Press, 1993.

Pratt, V.R., Linear Logic for Generalized Quantum Mechanics, Proc. of Workshop on Physics and Computation (PhysComp'92), 166-180, IEEE, Dallas, Oct, 1992.

Pratt, V.R., The Duality of Time and Information, Proc. Conf. on Concurrency (CONCUR'92), LNCS 630, 237-253, Springer-Verlag, Stonybrook, NY, August, 1992,

Pratt, V.R., Origins of the Calculus of Binary Relations, Proc. IEEE Symp. on Logic in Computer Science, 248-254, Santa Cruz, CA, June, 1992.

Pratt, V.R., Arithmetic + Logic + Geometry = Concurrency, Proc. Symposium Latin American Theoretical Informatics, LNCS 583, 430-447, Sao Paulo, Brazil, April 1992.

Pratt, V.R., Dynamic Algebras: Examples, Constructions, Applications, Studia Logica, 50:3/4, 571-605, 1992.

Pratt, V.R., Event Spaces and Their Linear Logic, Proc. Second International Conference on Algebraic Methodology And Software Technology, 1-23, Iowa City, Iowa, May, 1991.

Avrahami, G. and Pratt, V.R., Sub-Pixel Edge Detection in Character Digitization, Proc. Raster Imaging and Digitization Technology, Boston, 1991. In Raster Imaging and Digital Typography II, ed. Robert A. Morris and Jacques Andre, 54-64, Cambridge University Press, 1991

Pratt, V.R., Modeling Concurrency with Geometry, Proc. 18th Ann. ACM Symposium on Principles of Programming Languages, 311-322, January, 1991. Also Report No. STAN-CS-90-1342, CS Dept., Stanford, Nov. 1990.

Pratt, V.R., Action Logic and Pure Induction, Invited paper, Logics in AI: European Workshop JELIA '90, ed. J. van Eijck, LNCS 478, 97-120, Springer-Verlag, Amsterdam, NL, Sep, 1990. Also Report No. STAN-CS-90-1343, CS Dept., Stanford, Nov. 1990.

Pratt, V.R., Dynamic algebras as a well-behaved fragment of relation algebras, Proc. Algebra and Computer Science, ed. Bergman, Maddux, and Pigozzi, LNCS 425, 77-110, Springer-Verlag, 1990. Also Report No. STAN-CS-90-1309, CS Dept., Stanford, 1990.

Casley, R.T., Crew, R.F., Meseguer, J., and Pratt, V.R., Temporal Structures, Proc. Category Theory and Computer Science 1989, ed. D. Pitt et al, LNCS 389, 21-51, Springer-Verlag, 1989. Revised journal version in Mathematical Structures in Computer Science, Volume 1:2, 179-213, July 1991.

Pratt, V.R., Enriched Categories and the Floyd-Warshall Connection, Proc. First International Conference on Algebraic Methodology And Software Technology, 177-180, Iowa City, Iowa, May, 1989.

Pratt, V.R., The future of information technology: A US perspective, Workshop on Research Priorities in Communications and Information Technology, Vol. II, (eds. S.E. Garrett-Jones, B. Lamond, and T. Thomas), Department of Industry, Technology and Commerce, Australian Govt. Publishing Service, Canberra, 1988.

Pratt, V.R., Direct Least Squares Fitting of Algebraic Surfaces, Computer Graphics 21, 4, 145-152, (SIGGRAPH 87), July 1987.

Lien, S.-L., Shantz, M., and Pratt, V.R., Adaptive Forward Differencing for Rendering Curves and Surfaces, Computer Graphics 21, 4, 111-118, (SIGGRAPH 87), July 1987.

Gaifman, H., and Pratt, V.R., Partial Order Models of Concurrency and the Computation of Functions, Proc. IEEE Symp. on Logic in Computer Science, Ithaca, NY, 72-85, June, 1987.

Pratt, V.R., Modeling Concurrency with Partial Orders, IJPP, 15:1, 33-71, 1986.

Pratt, V.R., Some Constructions for Order-Theoretic Models of Concurrency, Proc. Conf. on Logics of Programs, 269-283, Springer-Verlag Lecture Notes in Computer Science LNCS 193, Brooklyn, 1985.

Pratt, V.R., Techniques for Conic Splines, Computer Graphics 19, 3, 151-159 (SIGGRAPH 85), July 1985.

Pratt, V.R., Two-Way Channel with Disconnect, in section 3.1.3 of Denvir, T., W. Harwood, M. Jackson, and M. Ray, The Analysis of Concurrent Systems, 110-111, LNCS 207, Springer-Verlag, 1985.

Pratt, V.R., The Pomset Model of Parallel Processes: Unifying the Temporal and the Spatial, Proc. CMU/SERC Workshop on Analysis of Concurrency, 180-196, Springer-Verlag Lecture Notes in Computer Science LNCS 196, Pittsburgh, 1984.

Pratt, V.R., Standards and Performance Issues in the Workstation Market, Computer Graphics and Applications, 4:4, 71-76, April, 1984.

Pratt, V.R., Five Paradigm Shifts in Programming Language Design and their Realization in the Programming Language Viron, Proc. 10th Ann. ACM Symposium on Principles of Programming Languages, January, 1983.

Pratt, V.R., On the Composition of Processes, Proc. 9th Ann. ACM Symposium on Principles of Programming Languages, January, 1982.

Pratt, V.R., A Decidable Mu-Calculus, Proc. 22nd IEEE Conference on Foundations of Computer Science, 421-427, October, 1981.

Pratt, V.R., Using Graphs to Understand PDL, Proc. IBM Conf. on Logics of Programs, 387-396, LNCS 131, Springer-Verlag, May, 1981.

Rodeh, M., V.R. Pratt, and S. Even, Linear Algorithm for Data Compression via String Matching, JACM, 28:1, 16-24, 1981.

Pratt, V.R., Program Logic Without Binding is Decidable, Proc. 8th Ann. ACM Symposium on Principles of Programming Languages, 159-163, January, 1981.

Pratt, V.R., Application of Modal Logic to Programming, Studia Logica, 34, 2/3, 257-274, 1980.

Pratt, V.R., Six Lectures on Dynamic Logic, Foundations of Computer Science III, Part 2, 53-82, Mathematical Centre Tracts 109, Amsterdam, 1980.

Pratt, V.R., Dynamic Algebras and the Nature of Induction, Proc. 12th ACM Symposium on Theory of Computing, 22-28, May 1980.

Pratt, V.R., A Near-Optimal Method for Reasoning About Actions, JCSS, 20:2, 231-254, April, 1980.

Pratt, V.R., On Specifying Verifiers, Proc. 7th Ann. ACM Symposium on Principles of Programming Languages, January, 1980.

Pratt, V.R., Models of Program Logics, Proc. 20th IEEE Conference on Foundations of Computer Science, 115-122, October, 1979.

Pratt, V. R., Axioms or Algorithms, Proc. 6th Symposium on Mathematical Foundations of Computer Science, 160-169, Sept., 1979.

Pratt, V.R., LISP - A Mathematician's View, Byte magazine, 162-168, August, 1979.

Pratt, V.R., Shellsort and Sorting Networks, Garland Publishing, Inc., New York, 1979. (Ph.D. Thesis, Computer Science Dept, Stanford University, December 1971.)

Pratt, V.R., Dynamic Logic, Proc. 6th International Congress on Logic, Philosophy, and Methodology of Science, August 1979.

Pratt, V.R., Process Logic, Proc. 6th Ann. ACM Symp. on Principles of Programming Languages, Jan. 1979, 93-100.

Pratt, V.R., LISP, in Encyclopedia of Computer Sciences and Technology, 10, (eds. Belzer, J., A. Holzmann and A. Kent), Marcel Dekker, New York, 1978, 78-116.

Pratt, V.R., A Practical Decision Method for Propositional Dynamic Logic, Proc. 10th Ann. ACM Symp. on Theory of Computing, Calif., May 1978, 326-337.

Harel, D., and V.R. Pratt, Nondeterminism in Logics of Programs, Proc. 5th Annual ACM Symposium on Principles of Programming Languages, January 1978, 203-213.

Litvintchouk, S.D., and V.R. Pratt, A Proof Checker for Dynamic Logic, 5th International Joint Conference on Artificial Intelligence, August 1977, 552-558.

Knuth, D.E., J.H. Morris, and V.R. Pratt, Fast Pattern Matching in Strings, SIAM Journal on Computing, 6, 2, 1977, 323-350.

Harel, D., A.R. Meyer, and V.R. Pratt, Computability and Completeness in Logics of Programs, Proc. 9th Annual ACM Symposium on Theory of Computation, 1977, 261-268.

Pratt, V.R., The Competence/Performance Dichotomy in Programming, Proc. 4th Annual ACM Symposium on Principles of Programming Languages, 1976, 194-200.

Pratt, V.R., Semantical Considerations on Floyd-Hoare Logic, Proc. 17th Annual IEEE Symposium on Foundations of Computer Science, 1976, 109-121.

Rivest, R.L., and V.R. Pratt, The Mutual Exclusion Problem for Unreliable Processes, Proc. 17th Annual IEEE Symposium on Foundations of Computer Science, 1-8, 1976.

Pratt, V.R., and L.J. Stockmeyer, A Characterization of the Power of Vector Machines, JCSS, 12, 2, 1976, 198-221.

Pratt, V.R., The Effect of Basis on the Size of Boolean Expressions, Proc. 16th Annual IEEE Symposium on Foundations of Computer Science, 1975, 119-121.

Pratt, V.R., The Power of Negative Thinking in Multiplying Boolean Matrices, SIAM Journal on Computing, 4:3, 326-330, 1975.

Pratt, V.R., LINGOL - A Progress Report, Proc. 4th International Joint Conference on Artificial Intelligence, 422-428, Tbilisi, USSR, 1975.

Pratt, V.R., Every Prime has a Succinct Certificate, SIAM Journal on Computing, 4:3, 214-220, 1975.

Pratt, V.R., M.O. Rabin, and L.J. Stockmeyer, A Characterization of the Power of Vector Machines, Proc. 6th Annual ACM Symposium on Theory of Computation, 122-134, 1974.

Pratt, V.R., The Power of Negative Thinking in Multiplying Boolean Matrices, Proc. 6th Annual ACM Symposium on Theory of Computation, 80-83, 1974.

Blum, M., R. Floyd, V.R. Pratt, R.L. Rivest, and R.E. Tarjan, Time Bounds for Selection, JCSS 7:4, 448-461, 1973.

Pratt, V.R., and F.F. Yao, On Lower Bounds for Computing the ith Largest Element, Proc. 14th Annual IEEE Symposium on Switching and Automata Theory, 70-81, Oct. 1973.

Pratt, V.R., Top Down Operator Precedence, Proc. ACM Symposium on Principles of Programming Languages, 41-51, Oct. 1973.

Pratt, V.R., A Least Upper Bound on Conventional Shellsort, in Combinatorial Algorithms, (ed. Rustin, R.), 31-38, Algorithmics Press, N.Y., 1973.

Pratt, V.R., A Linguistics Oriented Programming Language, 3rd International Joint Conference on Artificial Intelligence, 372-382, 1973.

Pratt, V.R., Computing Permutations with Double-Ended Queues, Parallel Stacks and Parallel Queues, Proc. 5th Annual ACM Symposium on Theory of Computation, 268-277, 1973.

Pratt, V.R., An n log n Algorithm to Distribute n Records Optimally in a Sequential Access File, in Complexity of Computer Computations, (ed. Miller, R., and J. Thatcher), 111-118, Plenum Press, N.Y., 1972.

Pratt, V.R., Translation of English into Logical Expressions, MS Thesis, Basser Computing Dept, Sydney University, August 1969.