Link to google scholar citations.

Recent surveys

• Alexander Okhotin, Kai Salomaa: Complexity of Input-Driven Pushdown Automata, SIGACT News, Vol. 45, No. 2 (2014) 47-67
• Alexandros Palioudakis, Kai Salomaa, Selim G. Akl: Quantifying Nondeterminism in Finite Automata, Annals of the University of Bucharest, Informatica, No. 2 (2015) 89-100
• Timothy Ng, David Rappaport, Kai Salomaa: Descriptional Complexity of Error Detection, to appear, 2016

My research belongs to the general area of theory of computation. My current research interests include:

• descriptional complexity of automata and grammars
• state-complexity and transition complexity of finite automata, algorithms for automata operations and implementation
• cellular automata, membrane computing
• tree automata, nested word automata
• nondeterminism measures for (pushdown) automata, complexity of parsing
• language decompositions, trajectories, synchronization expressions

Formal Languages and Automata Theory Research Group

Teaching in 2024-25

• Discrete Structures II, CISC-203 (onQ), Winter 2025
• Software Specifications CISC/CMPE-223, Fall 2024

Other recent courses

• Discrete mathematics for Computing II, CISC-203, fall 2019
• Computability and Complexity CISC-462, Fall 2018
• Computational Complexity CISC-876, Fall 2018

Publications (in DBLP)

• Publications since 2010 (not up-to-date)
• Publications 2005 - 2009
• Publications 2000 - 2004
• Publications 1995 - 1999
• Earlier publications

Conference Programme Committees

• 16th International Conference on Automata and Formal Languages, AFL, Eger, Hungary, September 5-7, 2023
• 27th International Conference on Implementation and Application of Automata, CIAA, Famagusta, Cyprus, September 19-22, 2023
• 25th International Conference on Descriptional Complexity of Formal Systems, Potsdam, Germany, July 4-6, 2023
• 9th International Conference on Algebraic Informatics, CAI, Aristotetle University of Thessaloniki, Greece (online), October 27-29, 2022
• 12th International Workshop on Non-Classical Models of Automata and Applications, , NCMA, Debrecen, Hungary, August 26-27, 2022
• 24th International Conference on Descriptional Complexity of Formal systems, DCFS, Debrecen, Hungary, August 29-31, 2022
• 26th International Conference on Implementation and Application of Automata, CIAA, June 28 - July 1, 2022, Rouen, France
• Highlights 2022, Highlights of Logic, Games and Automata, June 28 - July 1, 2022, Paris, France
• 25th International Conference on Developments in Language Theory, DLT, August 16-20, 2021, Porto, Portugal
• 25th International Conference on Implementation and Application of Automata, CIAA, July 19-22, 2021, Bremen, Germany
• 23rd International Conference on Descriptional Complexity of Formal Systems, DCFS, Seoul, South Korea (proceedings only event)
• 38th International Symposium on Theoretical Aspects of Computer Science, STACS, Saarbrucken, Germany, March 16-19, 2021.
• 25th International Conference Implementation and Application of Automata, CIAA, Loughborough University, United Kingdom, September 8-11, 2020.
• 12th International Workshop Non-Classical Models of Automata and Applications,, NCMA, Vienna, Austria, August 26-27, 2020.
• 24th International Conference Developments in Language Theory, DLT 2020, Tampa, Florida, May 11-15, 2020.
• 14th International Conference Language and Automata Theory and Applications, LATA 2020, Milan, Italy, March 2-6, 2020.
• 46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020, Limassol, Cyprus, Jan. 20 - 24, 2020.
• 10th IEEE Annual Information Technology, Electronics, and Mobile Communication Conference, IEEE IEMCON 2019, Computer Algorithms & Theory and Parallel Computing track, October 17-19, 2019, UBC Canada
• 24th International Conference on Implementation and Application of Automata, Kosice, Slovakia, July 22-25, 2019
• 21st International Conference on Descriptional Complexity of Formal Systems, Kosice, Slovakia, July 17-19, 2019
• 18th International Conference Unconventional Computation and Natural Computation 2019, Tokyo, Japan, June 3-7, 2019
• 13th International Conference on Language and Automata Theory and Applications LATA 2019, Saint Petersburg, Russia, March 26-29, 2019
• 23rd International Conference Implementation and Application of Automata, July 30 - August 2, 2018, Charlottetown, Canada
• 20th International Conference Descriptional Complexity of Formal Systems, DCFS 2018, Halifax, Canada, July 25-27, 2018
• 19th Descriptional Complexity of Formal Systems, DCFS 2017, Milan, Italy, July 3-5, 2017
• 22nd International Conference Implementation and Application of Automata 27-30 June 2017, Université Paris-Est Marne-la-Vallée
• 13th International Conference Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017
• 21st International Conference on Implementation and Application of Automata, CIAA 2016, Seoul, South Korea, July 19-22, 2016
• 10th International Conference on Language and Automata Theory and Applications, LATA 2016, Prague, Czech Republic, March 14-18, 2016
• 6th International Conference on Algebraic Informatics (CAI 2015), September 1 - 4, 2015, Stuttgart, Germany
• 20th International Conference Implementation and Application of Automata, August 18 - 21, 2015, Umeå, Sweden
• 17th International Workshop on Descriptional Complexity of Formal Systems, DCFS'15, Waterloo, Ontario, Canada - June 25-27 2015
• 16th International Workshop on Descriptional Complexity of Formal Systems, DCFS'14, August 5-8, 2014, Turku, Finland
• 19th International Conference on Implementation and Application of Automata, CIAA'14, July 30-August 2, 2014, Giessen, Germany
• 13th International Conference on Unconventional Computation and Natural Computation, UCNC 2014, July 14-18, London, Ontario, Canada.
• 20th International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2014, July 7-9, Himeji, Japan.
• 14th International Conference on Automata and Formal Languages, AFL 2014, May 27-29, Szeged, Hungary.
• 19th International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2013, September 17-19, Giessen, Germany
• 15th Workshop on Descriptional Complexity of Formal Systems, DCFS 2013, July 22-25, London, Ontario, Canada
• 18th International Conference on Implementation and Application of Automata, CIAA'13, July 16-19, 2013, Halifax, Canada
• 12th International Conference on Unconventional Computation and Natural Computation, UCNC 2013, July 1-5, 2013, Milano, Italy
• 4th International Workshop on Non-Classical Models of Automata and Applications, NCMA'12, August 23-24, 2012, Fribourg, Switzerland
• 16th International Conference on Developments in Language Theory, DLT'12, August 14-17, 2012, National Taiwan University, Taipei, Taiwan
• 14th International Workshop on Descriptional Complexity of Formal Systems, DCFS'12, July 23-25, 2012, Braga, Portugal
• 17th International Conference on Implementation and Application of Automata, CIAA'12, July 17-20, 2012, Porto, Portugal
• Applications of Tree Automata Techniques in Natural Language Processing, ATANLP'12, April 24, 2012, Avignon, France
• International Workshop on Theoretical Computer Science, February 21-24, 2012, Auckland, New Zealand
• 13th International Conference on Automata and Formal Languages, AFL'11, August 17-22, 2011 Debrecen, Hungary
• 13th Workshop on Descriptional Complexity of Formal Systems, DCFS'11, July 25 - 27, 2011, Vicinity of Giessen, Germany
• 3rd International Workshop on Non-Classical Models of Automata and Applications, NCMA'11, July 18 - 19, 2011, Milano, Italy
• 16th International Conference on Implementation and Application of Automata, CIAA'11, Université François Rabelais Tours, Blois, France July 13-16, 2011
• 10th International Conference on Unconventional Computation, UC'11, June 6 - 10, Turku, Finland
• 2nd Workshop on Non-Classical Models of Automata and Applications, NCMA'10, August 23 - 24, 2010, Jena, Germany
• 14th International Conference Developments in Language Theory, DLT'10, August 17 - 20, 2010, London, Canada
• 15th International Conference on Implementation and Application of Automata, CIAA 2010, August 12 - 15, 2010, Winnipeg, Canada
• 12th Workshop on Descriptional Complexity of Formal Systems, DCFS'10, August 8 - 10, 2010, Saskatoon, Canada
• Applications of Tree Automata in Natural Language Processing, ATANLP 2010, July 16, 2010, Uppsala, Sweden
• 9th International Conference on Unconventional Computation, UC'10, June 21 - 25, 2010, Tokyo, Japan
• 4th International Conference on Language and Automata Theory and Applications, LATA 2010, May 24 - 28, 2010, Trier, Germany
• 8th International Conference on Unconventional Computation, UC 2009, September 7 - 11, 2009, Ponta Delgada (Azores), Portugal
• Non-Classical Models of Automata and Applications, NCMA'09, August 31 - September 1, 2009, Wroclaw, Poland
• 4th International Computer Science Symposium in Russia, CSR 2009, August 18 - 23, 2009, Novosibirsk, Russia
• 14th International Conference on Implementation and Application of Automata, CIAA 2009, July 14 - 17, 2009, Sydney, Australia
• 3rd International Conference on Algebraic Informatics, CAI 2009, May 19 - 22, 2009, Thessaloniki, Greece
• 12th International Conference Developments in Language Theory, Kyoto, Japan, September 16 - 19, 2008.
• 7th International Conference on Unconventional Computation, UC 2008, Vienna, Austria, August 25 - 28, 2008.
• 10th International Workshop Descriptional Complexity of Formal Systems, Charlottetown, Prince Edward Island, July 16 - 18, 2008.
• The 12th International Conference on Automata and Formal Languages, Balatonfured, Hungary, May 27-30, 2008.
• 2nd International Conference on Language and Automata Theory and Applications, Tarragona, Spain, March 13 - 19, 2008.
• 12th International Conference on Implementation and Application of Automata, Prague, Czech Republic, July 16 - 18, 2007.
• Workshop Language Theory in Biocomputing at UC'07, Kingston, Canada, August, 2007.
• Theory and Applications of Language Equations, TALE, Turku, Finland, July 2, 2007.
• 1st International Conference on Language and Automata Theory and Applications, LATA 2007, Tarragona, Spain, March 29 - April 4, 2007.
• 11th International Conference on Implementation and Application of Automata, CIAA 2006, Taipei, Taiwan, August 21-23, 2006.
• Tenth International Conference Developments in Language Theory, Santa Barbara, CA, USA, June 26 - 29, 2006.
• 10th International Conference on Implementation and Application of Automata, CIAA 2005, University of Nice, Sophia Antipolis, France, June 27 - 29, 2005.
• DCFS 2005 - Descriptional Complexity of Formal Systems, Como, Italy, June 30 - July 2, 2005.
• 11th International Conference on Automata and Formal Languages, AFL'05, Dobogoko, Hungary, May 17 - 20, 2005.
  • Photos from AFL'05.
• Eigth International Conference on Developments in Language Theory, DLT 2004, Auckland, New Zealand, December 13 - 17, 2004.
• Ninth International Conference on Implementation and Application of Automata, CIAA 2004 , Queen's University, Kingston, July 22-24, 2004.
• Eighth International Conference on Implementation and Application of Automata, CIAA 2003 , Santa Barbara, CA, July 16-18, 2003.
• 5th Workshop Descriptional Complexity of Formal Systems, DCFS - 2003, Budapest, Hungary, July 12-14, 2003.
• Sixth International Conference Developments in Language Theory, DLT 2002, Kyoto, Japan, September 18 - 21, 2002.
• Seventh International Conference on Implementation and Application of Automata, CIAA 2002, Tours, France, July 3 - 6, 2002.
• Third International Conference on Discrete Mathematics and Theoretical Computer Science DMTCS01
• Descriptional Complexity of Automata, Grammars and Related Structures, Third Workshop, DCAGRS2001 (July 20 - 22, 2001, Vienna, Austria)

Hobbies

• Go - Baduk - Weichi
  (Photographs by Alexander Okhotin)