Jean Henri Gallier (born 1949) is a researcher in computational logic at the

University of Pennsylvania The University of Pennsylvania (also known as Penn or UPenn) is a private research university in Philadelphia. It is the fourth-oldest institution of higher education in the United States and is ranked among the highest-regarded universitie ...

, 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 Nancy ; Lorraine Franconian: ''Nanzisch'' is the Prefectures in France, prefecture of the northeastern Departments of France, French department of Meurthe-et-Moselle. It was the capital of the Duchy of Lorraine, which was Lorraine and Barrois, an ...

, and holds dual French and American citizenship. He earned his

baccalauréat The ''baccalauréat'' (; ), often known in France colloquially as the ''bac'', is a French national academic qualification that students can obtain at the completion of their secondary education (at the end of the ''lycée'') by meeting certain ...

at the Lycée de Sèvres in 1966, and a degree in

civil engineering Civil engineering is a professional engineering discipline that deals with the design, construction, and maintenance of the physical and naturally built environment, including public works such as roads, bridges, canals, dams, airports, sewage ...

at the École Nationale des Ponts et Chaussées in 1972. He then moved to the

University of California, Los Angeles The University of California, Los Angeles (UCLA) is a public land-grant research university in Los Angeles, California. UCLA's academic roots were established in 1881 as a teachers college then known as the southern branch of the California St ...

for his graduate studies, earning a Ph.D. in computer science in 1978 under the joint supervision of

Sheila Greibach Sheila Adele Greibach (born 6 October 1939 in New York City) is a researcher in formal languages in computing, automata, compiler theory and computer science. She is an Emeritus Professor of Computer Science at the University of California, Los ...

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 The University of California, Santa Barbara (UC Santa Barbara or UCSB) is a Public university, public Land-grant university, land-grant research university in Santa Barbara County, California, Santa Barbara, California with 23,196 undergraduate ...

, 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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

algorithm for Horn-satisfiability. This is a variant of the

Boolean satisfiability In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...

problem: its input is a Boolean formula in conjunctive normal form with at most one positive

literal Literal may refer to: * Interpretation of legal concepts: ** Strict constructionism ** The plain meaning rule (a.k.a. "literal rule") * Literal (mathematical logic), certain logical roles taken by propositions * Literal (computer programmin ...

per clause, and the goal is to assign

truth value In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values (''true'' or '' false''). Computing In some progr ...

s 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 Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...

, low-dimensional topology, and

discrete mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...

Selected publications

Research papers

Books

References

External links

Home page
* {{DEFAULTSORT:Gallier, Jean Henri Living people American computer scientists French computer scientists 20th-century American mathematicians 21st-century American mathematicians French mathematicians Mathematical logicians Researchers in geometric algorithms Theoretical computer scientists École des Ponts ParisTech alumni University of California, Los Angeles alumni University of Pennsylvania faculty Mathematicians at the University of Pennsylvania 1949 births