Jean Henri Gallier (born 1949) is a researcher in

computational logic Computational logic is the use of logic to perform or reason about computation. It bears a similar relationship to computer science and engineering as mathematical logic bears to mathematics and as philosophical logic bears to philosophy. It is a ...

at the

University of Pennsylvania The University of Pennsylvania (Penn or UPenn) is a Private university, private Ivy League research university in Philadelphia, Pennsylvania, United States. One of nine colonial colleges, it was chartered in 1755 through the efforts of f ...

, 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 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, annexed by France under King Louis X ...

, 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 regulation and licensure in engineering, professional engineering discipline that deals with the design, construction, and maintenance of the physical and naturally built environment, including public works such as roads ...

at the

École Nationale des Ponts et Chaussées École nationale des ponts et chaussées (; ; abbr. ENPC), also nicknamed Ponts (), formerly known as École des Ponts ParisTech (), is a grande école in the field of science, engineering and technology, of the Polytechnic Institute of Paris, a ...

in 1972. He then moved to the

University of California, Los Angeles The University of California, Los Angeles (UCLA) is a public university, public Land-grant university, land-grant research university in Los Angeles, California, United States. Its academic roots were established in 1881 as a normal school the ...

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 an American researcher in formal languages in computing, automata, compiler theory and computer science. She is an Emeritus Professor of Computer Science at the University of Calif ...

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, United States. Tracing its roots back to 1891 as an ...

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

algorithm for

Horn-satisfiability In formal logic, Horn-satisfiability, or HORNSAT, is the problem of deciding whether a given conjunction of propositional Horn clauses is satisfiable or not. Horn-satisfiability and Horn clauses are named after Alfred Horn. A Horn clause is a clau ...

. 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) asks whether there exists an Interpretation (logic), interpretation that Satisf ...

problem: its input is a Boolean formula in

conjunctive normal form In Boolean algebra, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. In au ...

with at most one positive literal 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''). Truth values are used in ...

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 Prolog is a logic programming language that has its origins in artificial intelligence, automated theorem proving, and computational linguistics. Prolog has its roots in first-order logic, a formal logic. Unlike many other programming language ...

programming language. Gallier is also the author of five books in computational logic, computational geometry,

low-dimensional topology In mathematics, low-dimensional topology is the branch of topology that studies manifolds, or more generally topological spaces, of four or fewer dimensions. Representative topics are the theory of 3-manifolds and 4-manifolds, knot theory, ...

, 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 University of Pennsylvania Department of Computer and Information Science faculty