Imre Simon, Hungarian-born Jewish Brazilian computer scientist (Budapest 14 August 1943 – São Paulo 13 August 2009) Authored 20 papers and 7 books Introduced the algebraic structure known as tropical semiring to computer science Laid the basis of multiplicities theory of tropical semiring Introduced formal study in theoretical computer science Characterized algebraically the class of piecewise testable elegants or Simon theorem (1972-5)
Introduced factorization forests (1990) Defined nondeterministic complexity of a finite automation (1990) Improved Knuth-Morris-Pratt string searching algorithm that became Simon algorithm (1994) With J. Brzozowski solved the problem of the effective characterization of the locally testable languages independently of McNaughton (1973) Defined a system of finite-index congruences to classify languages in the family Characterized two natural hierarchies i.e. piecewise testable languages and the locally testable languages Developed an efficient algorithm for distinguishing 2 words by their subwords (2003) Eponym of Simon congruence |
Alphabetical List > S >