en Kai Salomaa

Kai Salomaa
Kai Salomaa
Born	9 February 1960 (age 64); Turku, Finland
Alma mater	University of Turku
Known for	formal language theory; state complexity;
	Scientific career
Fields	Automata theory
Institutions	Queen's University
Thesis	Alternation and Pushdown Stores in Computations of Tree Automata (1989)
Doctoral advisor	Magnus Steinby; Ronald V. Book;

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.

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