Andrzej Ehrenfeucht (, born 8 August 1932) is a

Polish-American Polish Americans ( pl, Polonia amerykańska) are Americans who either have total or partial Polish ancestry, or are citizens of the Republic of Poland. There are an estimated 9.15 million self-identified Polish Americans, representing about 2.83% ...

mathematician and computer scientist.

Life

Andrzej Ehrenfeucht formulated the

Ehrenfeucht–Fraïssé game In the mathematical discipline of model theory, the Ehrenfeucht–Fraïssé game (also called back-and-forth games) is a technique based on game semantics for determining whether two structures are elementarily equivalent. The main application of ...

, using the

back-and-forth method In mathematical logic, especially set theory and model theory, the back-and-forth method is a method for showing isomorphism between countably infinite structures satisfying specified conditions. In particular it can be used to prove that * any t ...

given in

Roland Fraïssé Roland Fraïssé (; 12 March 1920 – 30 March 2008) was a French mathematical logician. Fraïssé received his doctoral degree from the University of Paris in 1953. In his thesis, Fraïssé used the back-and-forth method to determine whether t ...

's PhD thesis. Also named for Ehrenfeucht is the

Ehrenfeucht–Mycielski sequence The Ehrenfeucht–Mycielski sequence is a recursively defined sequence of binary digits with pseudorandom properties, defined by . Definition The sequence starts with the single bit 0; each successive digit is formed by finding the longest suffix o ...

. In 1971 Ehrenfeucht was a founding member of the Department of Computer Science at the

University of Colorado at Boulder The University of Colorado Boulder (CU Boulder, CU, or Colorado) is a public research university in Boulder, Colorado. Founded in 1876, five months before Colorado became a state, it is the flagship university of the University of Colorado sy ...

. He currently teaches and does research at the University, where he runs a project, "breaking away", with Patricia Baggett; the project, using hands-on activities, aims at raising high-school students' interest in mathematics and technology. Two of Ehrenfeucht's students,

Eugene Myers Eugene Wimberly "Gene" Myers, Jr. (born December 31, 1953) is an American computer scientist and bioinformatician, who is best known for contributing to the early development of the NCBI's BLAST tool for sequence analysis. Education Myers receiv ...

and

David Haussler David Haussler (born 1953) is an American bioinformatician known for his work leading the team that assembled the first human genome sequence in the race to complete the Human Genome Project and subsequently for comparative genome analysis that d ...

, contributed to the sequencing of the

human genome The human genome is a complete set of nucleic acid sequences for humans, encoded as DNA within the 23 chromosome pairs in cell nuclei and in a small DNA molecule found within individual mitochondria. These are usually treated separately as the ...

. They, with Harold Gabow, Ross McConnell, and Grzegorz Rozenberg, spoke at a 2012 University of Colorado two-day symposium honoring Ehrenfeucht's 80th birthday. Two journal issues have come out in his honor, one at his 65th birthday in

Lecture Notes in Computer Science ''Lecture Notes in Computer Science'' is a series of computer science books published by Springer Science+Business Media since 1973. Overview The series contains proceedings, post-proceedings, monographs, and Festschrifts. In addition, tutorial ...

, and one at his 80th in

Theoretical Computer Science computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the ...

Private life

Ehrenfeucht married

Alfred Tarski Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...

's daughter Ina Tarski. Anita B. Feferman and

Solomon Feferman Solomon Feferman (December 13, 1928 – July 26, 2016) was an American philosopher and mathematician who worked in mathematical logic. Life Solomon Feferman was born in The Bronx in New York City to working-class parents who had immigrated to th ...

, ''Alfred Tarski: Life and Logic'', Cambridge University Press, 2004. , pp. 239–242.

Bibliography

Books

* Andrzej Ehrenfeucht, Tero Harju, Ion Petre, David M. Prescott, Grzegorz Rozenberg, ''Computation in Living Cells: Gene Assembly in Ciliates'', Springer, 2004, * Patricia Baggett, Andrzej Ehrenfeucht, ''Breaking Away from the Math Book: Creative Projects for Grades K-6'', * Andrzej Ehrenfeucht, Tero Harju, Grzegorz Rozenberg, ''The Theory of 2-Structures: A Framework for Decomposition and Transformation of Graphs'', World Scientific, 1999,

Papers

(accessible throug
Wirtualna Biblioteka Nauki
* Chen Chung Chang, Andrzej Ehrenfeucht
"A Characterization of Abelian Groups"
''

Fundamenta Mathematicae ''Fundamenta Mathematicae'' is a peer-reviewed scientific journal of mathematics with a special focus on the foundations of mathematics, concentrating on set theory, mathematical logic, topology and its interactions with algebra, and dynamical sys ...

'', vol. 51, no. 2, 1962, pp. 141-147. * Andrzej Ehrenfeucht
"An Application of Games to the Completeness Problem for Formalized Theories"
''

'', vol. 49, no. 2, 1960, pp. 129-141. * Andrzej Ehrenfeucht
"On Theories Categorical in Power"
''

'', vol. 44, no. 2, 1957, pp. 241-248. * Andrzej Ehrenfeucht, Andrzej Mostowski
"Models of Axiomatic Theories Admitting Automorphisms"
''

'', 1956, vol. 43, no. 1, pp. 50-68.

References

External links

Ehrenfeucht's website
at the University of Colorado

* * {{DEFAULTSORT:Ehrenfeucht, Andrzej 1932 births Living people Scientists from Vilnius People from Wilno Voivodeship (1926–1939) 20th-century American mathematicians American computer scientists Polish emigrants to the United States Polish computer scientists University of Warsaw alumni University of Colorado faculty