Alphabetical List‎ > ‎S‎ > ‎

Imre Simon

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)


Proved a decomposition theorem in terms of the classical wreath product operation (1972)

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