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.

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

Contributions Gallier's most heavily cited research paper, with his student William F. Dowling, gives a linear time algorithm for Horn-satisfiability. 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.

Gallier is also the author of five books in computational logic, computational geometry, low-dimensional topology, and discrete mathematics.

Selected publications Research papers

Books