Jean Gallier


Jean Henri Gallier (born 1949) is a researcher in computational logic at the University of Pennsylvania, where he holds appointments in the Computer and Information Science Department and the Department of Mathematics.


Gallier was born January 5, 1949 in Nancy, France, and holds dual French and American citizenship. He earned his baccalauréat at the Lycée de Sèvres in 1966, and a degree in civil engineering at the École Nationale des Ponts et Chaussées in 1972.[1] He then moved to the University of California, Los Angeles for his graduate studies, earning a Ph.D. in computer science in 1978 under the joint supervision of Sheila Greibach and Emily Perlinski Friedman. His dissertation was entitled Semantics and Correctness of Classes of Deterministic and Nondeterministic Recursive Programs.[1][2] After postdoctoral study at the University of California, Santa Barbara, he joined the University of Pennsylvania Department of Computer and Information Science in 1978. At Pennsylvania, he was promoted to full professor in 1990, gained a secondary appointment to the Department of Mathematics in 1994, and directed the French Institute of Culture and Technology from 2001 to 2004.[1]


Gallier's most heavily cited research paper, with his student William F. Dowling, gives a linear time algorithm for Horn-satisfiability.[DG84] This is a variant of the Boolean satisfiability problem: its input is a Boolean formula in conjunctive normal form with at most one positive literal per clause, and the goal is to assign truth values to the variables of the formula to make the whole formula true. Solving Horn-satisfiability problems is the central computational paradigm in the Prolog programming language.[3]

Gallier is also the author of five books in computational logic,[G86]computational geometry,[G99][G00]low-dimensional topology,[GX13] and discrete mathematics.[G11]

Selected publicationsEdit

Research papersEdit

Dowling, William F.; Gallier, Jean H. (1984), "Linear-time algorithms for testing the satisfiability of propositional Horn formulae", Journal of Logic Programming, 1 (3): 267–284, doi:10.1016/0743-1066(84)90014-1, MR 0770156.


Gallier, Jean H. (1986), Logic for Computer Science: Foundations of Automatic Theorem Proving, Wiley. 2nd ed., Dover Publications, 2015.[4]
Gallier, Jean (1999), Curves and Surfaces in Geometric Modeling: Theory and Algorithms, The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling, San Francisco, CA: Morgan Kaufmann, ISBN 1-55860-599-1.[5]
Gallier, Jean (2000), Geometric Methods and Applications: For Computer Science and Engineering, Texts in Applied Mathematics, vol. 38, New York: Springer-Verlag, doi:10.1007/978-1-4613-0137-0, ISBN 0-387-95044-3. 2nd ed., 2011, ISBN 978-1-4419-9960-3.[6][7][8]
Gallier, Jean (2011), Discrete Mathematics, Universitext, New York: Springer-Verlag, doi:10.1007/978-1-4419-8047-2, ISBN 978-1-4419-8046-5, MR 2777371.[9]
Gallier, Jean; Xu, Dianna (2013), A Guide to the Classification Theorem for Compact Surfaces, Geometry and Computing, vol. 9, Heidelberg: Springer, doi:10.1007/978-3-642-34364-3, ISBN 978-3-642-34363-6.[10][11]


  1. ^ a b c Curriculum vitae, retrieved 2017-03-26.
  2. ^ Jean Gallier at the Mathematics Genealogy Project
  3. ^ Dechter, Rina (2003), Constraint Processing, The Morgan Kaufmann Series in Artificial Intelligence, San Francisco, CA: Morgan Kaufmann, p. 307, ISBN 9781558608900.
  4. ^ Pfenning, Frank (1989), "Review: Jean H. Gallier, Logic for Computer Science. Foundations of Automatic Theorem Proving" (PDF), Journal of Symbolic Logic, 54 (1): 288–289, doi:10.2307/2275035, JSTOR 2275035.
  5. ^ Kallay, Michael (2001), Review of Curves and surfaces in geometric modeling, MR1823812.
  6. ^ Jüttler, Bert (2001), Review of Geometric methods and applications, MR1792535. Updated for 2nd ed., 2012, MR2663906.
  7. ^ Williams, Hugh (November 2002), "Geometric Methods and Applications for Computer Science and Engineering", The Mathematical Gazette, 86 (507): 564, doi:10.2307/3621198, JSTOR 3621198.
  8. ^ Hunacek, Mark (2011), Review of Geometric methods and applications, Mathematical Association of America.
  9. ^ Pinter, Gabriella (2012), Review of Discrete Mathematics, Mathematical Association of America.
  10. ^ Löh, Clara, Review of A guide to the classification theorem for compact surfaces, MR3026641.
  11. ^ Wood, Bill (2014), Review of A Guide to the Classification Theorem for Compact Surfaces, Mathematical Association of America.

External linksEdit