[3]​ Se introdujo en la teoría de autómatas y lenguajes formales durante un seminario en la Berkeley dictado por John Myhill en 1957.

[3]​[5]​ Salomaa fue presidente de la European Association for Theoretical Computer Science desde 1979 hasta 1985.

Salomaa es autor y coautor de 46 libros de texto, incluyendo Automata theory (1969), Formal languages (1973), The Mathematical Theory of L-Systems (1980, con Grzegorz Rozenberg), Jewels of Formal Language Theory (1981), Public-Key cryptography (1990) y DNA computing (1998, con Grzegorz Rozenberg y Gheorge Paun).

Estos libros se han convertido en una referencia estándar en sus respectivas áreas.

Por ejemplo, Formal Languages fue reconocido en 1991 entre los cien libros de matemáticas más citados.