Kai Salomaa Explained

Kai Salomaa
Birth Date:9 February 1960
Birth Place:Turku, Finland
Field:Automata theory
Work Institution:Queen's University
Alma Mater:University of Turku
Doctoral Advisor:
Thesis Title:Alternation and Pushdown Stores in Computations of Tree Automata
Thesis Year:1989

Kai Tapani Salomaa (born 9 February 1960) is a Finnish Canadian theoretical computer scientist, known for his numerous contributions to the state complexity of finite automata.[1] [2] [3] [4] [5] His highly cited 1994 joint paper with Yu and Zhuang[6] laid the foundations of the area.He has published over 100 papers in scientific journals on various subjects in formal language theory. Salomaa is a full professor at Queen's University (Kingston, Ontario).

Biography

Salomaa did his undergraduate studies at the University of Turku, where he has earned his Ph.D. degree in 1989; his dissertation was jointly supervised by Ronald V. Book and Magnus Steinby. In the 1990s, Salomaa worked at the University of Western Ontario. Since 1999, he holds a professor position at Queen's University. His father, Arto Salomaa, is also a distinguished computer scientist with numerous contributions to the fields of automata theory and formal languages.

Notes and References

  1. Book: Salomaa. Kai. Yu. Sheng. Automata Implementation. NFA to DFA transformation for finite languages. Lecture Notes in Computer Science. 1260. 1997. 149–158. 0302-9743. 10.1007/3-540-63174-7_12. 978-3-540-63174-3.
  2. Salomaa. Arto. Salomaa. Kai. Yu. Sheng. State complexity of combined operations. Theoretical Computer Science. 383. 2–3. 2007. 140–152. 0304-3975. 10.1016/j.tcs.2007.04.015. free.
  3. Domaratzki. Michael. Salomaa. Kai. Lower bounds for the transition complexity of NFAs. Journal of Computer and System Sciences. 74. 7. 2008. 1116–1130. 0022-0000. 10.1016/j.jcss.2008.02.007.
  4. Book: Salomaa. Kai. Language and Automata Theory and Applications. State Complexity of Nested Word Automata. Lecture Notes in Computer Science. 5457. 2009. 59–70. 0302-9743. 10.1007/978-3-642-00982-2_5. 978-3-642-00981-5.
  5. Okhotin. Alexander. Salomaa. Kai. Complexity of input-driven pushdown automata. ACM SIGACT News. 45. 2. 2014. 47–67. 0163-5700. 10.1145/2636805.2636821. 16837177.
  6. Yu. Sheng. Zhuang. Qingyu. Salomaa. Kai. The state complexities of some basic operations on regular languages. Theoretical Computer Science. 125. 2. 1994. 315–328. 0304-3975. 10.1016/0304-3975(92)00011-F.