Alexander Okhotin: curriculum vitæ

the 23rd of November, A. D. 2017

Education and degrees

September 1996-June 2001.
Moscow State University named after M. V. Lomonosov, Faculty of Computational Mathematics and Cybernetics, Diploma with honours in applied mathematics and computer science.
December 2002.
Moscow State University named after M. V. Lomonosov, Candidate of science in discrete mathematics and mathematical cybernetics. Supervised by Dr. Vladimir A. Zakharov. Thesis title: "Complexity issues in the analysis of conjunctive grammars".
October 2001-October 2004.
Queen's University (Kingston, Ontario, Canada), School of Computing, Ph. D. in computer science. Supervised by Dr. Kai Salomaa. Thesis title: "Boolean grammars: expressive power and parsing algorithms".
April 2009.
University of Turku (Finland), Department of Mathematics, Docent (habilitation) in mathematical foundations of computer science.

Positions held

January 2001-September 2001.
Keldysh Institute for Applied Mathematics of Russian Academy of Sciences (Moscow, Russia), research assistant in parallel programming, part-time.
October 2001-October 2004.
Queen's University (Kingston, Ontario, Canada), School of Computing, teaching assistant and research assistant.
November 2004-March 2006.
University of Turku (Turku, Finland), Department of Mathematics, postdoctoral researcher.
April 2006-July 2006.
Rovira i Virgili University (Tarragona, Spain), Department of Romance Philology, Juan de la Cierva researcher.
August 2006-July 2011.
Academy of Finland; University of Turku (Turku, Finland), Department of Mathematics, Academy Research Fellow (akatemiatutkija).
January 2012-December 2014.
University of Turku (Turku, Finland), Department of Mathematics; Turku Collegium for Science and Medicine, Collegium researcher.
January 2015-December 2015.
University of Turku (Turku, Finland), Department of Mathematics and Statistics, senior researcher.
March 2016-August 2016.
University of Turku (Turku, Finland), Department of Mathematics and Statistics, researcher funded by the Finnish Cultural Foundation.
September 2016-present.
St. Petersburg State University (Russia), educational programme in Mathematics, (full) professor.

Research interests

Logical theory of formal grammars; parsing algorithms; complexity questions in finite automata; language equations.

Students supervised

Artur Jeż, Ph. D.
(April 2007-September 2010) Institute of Computer Science, Wrocław, Poland), supervised jointly with Prof. Krzysztof Loryś. Thesis title: "Conjunctive grammars and equations over sets of natural numbers", defended on 14 September 2010, with distinction. Polish Prime Minister's Award for an Outstanding Ph. D. thesis (2011).
Tommi J. M. Lehtinen, Ph. D.
(September 2007-March 2013) Department of Mathematics, University of Turku, Finland. Thesis title: "Numbers and languages", defended on 15 March 2013.
Mikhail Barash, Ph. D.
(September 2011-September 2015) Department of Mathematics and Statistics, University of Turku, Finland. Supervised jointly with Prof. Tero Harju. Thesis title: "Defining contexts in context-free grammars", defended on 25 September 2015.

Refereed journal papers

  1. "Conjunctive grammars", Journal of Automata, Languages and Combinatorics, 6:4 (2001), 519-535.
  2. "Top-down parsing of conjunctive languages", Grammars, 5:1 (2002), 21-40.
  3. "LR parsing for conjunctive grammars", Grammars, 5:2 (2002), 81-124.
  4. "Kon'yunktivnye grammatiki i sistemy yazykovykh uravnenii", in Russian, Programmirovanie, 28:5 (2002), 3-11.
  5. (with K. Salomaa and M. Domaratzki) "One-visit caterpillar tree automata", Fundamenta Informaticae, 52:4 (2002), 361-375.
  6. "On the closure properties of linear conjunctive languages", Theoretical Computer Science, 299:1-3 (2003), 663-685.
  7. "A recognition and parsing algorithm for arbitrary conjunctive grammars", Theoretical Computer Science, 302:1-3 (2003), 365-399.
  8. "The hardest linear conjunctive language", Information Processing Letters, 86:5 (2003), 247-253.
  9. "Efficient automaton-based recognition for linear conjunctive languages", International Journal of Foundations of Computer Science, 14:6 (2003), 1103-1116.
  10. "O slozhnosti zadachi generatsii strok", in Russian, Diskretnaya Matematika, 15:4 (2003), 84-99.
  11. (with M. Domaratzki) "Representing recursively enumerable languages by iterated deletion", Theoretical Computer Science, 314:3 (2004), 451-457.
  12. "On the equivalence of linear conjunctive grammars to trellis automata", RAIRO Informatique Théorique et Applications, 38:1 (2004), 69-88.
  13. "On the number of nonterminals in linear conjunctive grammars", Theoretical Computer Science, 320:2-3 (2004), 419-448.
  14. "Boolean grammars", Information and Computation, 194:1 (2004), 19-48.
  15. "State complexity of linear conjunctive languages", Journal of Automata, Languages and Combinatorics, 9:2-3 (2004), 365-381.
  16. (with K. Salomaa) "Contextual grammars with uniform sets of trajectories", Fundamenta Informaticae, 64:1-4 (2005), 341-351.
  17. "The dual of concatenation", Theoretical Computer Science, 345:2-3 (2005), 425-447.
  18. "A characterization of the arithmetical hierarchy by language equations", International Journal of Foundations of Computer Science, 16:5 (2005), 985-998.
  19. "Unresolved systems of language equations: expressive power and decision problems", Theoretical Computer Science, 349:3 (2005), 283-308.
  20. "Computational universality in one-variable language equations", Fundamenta Informaticae, 74:4 (2006), 563-578.
  21. (with J. Karhumäki and M. Kunc) "Computing by commuting", Theoretical Computer Science, 356:1-2 (2006), 200-211.
  22. "Generalized LR parsing algorithm for Boolean grammars", International Journal of Foundations of Computer Science, 17:3 (2006), 629-664.
  23. (with O. Yakimova) "Language equations with complementation: decision problems", Theoretical Computer Science, 376:1-2 (2007), 112-126.
  24. "Recursive descent parsing for Boolean grammars", Acta Informatica, 44:3-4 (2007), 167-189.
  25. "Notes on dual concatenation", International Journal of Foundations of Computer Science, 18:6 (2007), 1361-1370.
  26. (with M. Domaratzki and J. Shallit) "Enumeration of context-free languages and related structures", Journal of Automata, Languages and Combinatorics, 12:1-2 (2007), 79-95.
  27. (with G. Jirásková) "State complexity of cyclic shift", RAIRO Informatique Théorique et Applications, 42:2 (2008), 335-360.
  28. "Unambiguous Boolean grammars", Information and Computation, 206:9-10 (2008), 1234-1247.
  29. "Homomorphisms preserving linear conjunctive languages", Journal of Automata, Languages and Combinatorics, 13:3-4 (2008), 299-305.
  30. (with M. Domaratzki) "State complexity of power", Theoretical Computer Science, 410:24-25 (2009), 2377-2392.
  31. (with A. Jeż) "Conjunctive grammars over a unary alphabet: undecidability and unbounded growth", Theory of Computing Systems, 46:1 (2010), 27-58.
  32. (with J. Karhumäki and M. Kunc) "Computational power of two stacks with restricted communication", Information and Computation, 208 (2010), 1060-1089.
  33. "Decision problems for language equations", Journal of Computer and System Sciences, 76:3-4 (2010), 251-266.
  34. (with O. H. Ibarra and J. Karhumäki) "On stateless multihead automata: hierarchies and the emptiness problem", Theoretical Computer Science, 411:3 (2010), 581-593.
  35. "On the state complexity of scattered substrings and superstrings", Fundamenta Informaticae, 99:3 (2010), 325-338.
  36. (with C. Reitwießner) "Conjunctive grammars with restricted disjunction", Theoretical Computer Science, 411:26-28 (2010), 2559-2571.
  37. (with T. Lehtinen) "Boolean grammars and gsm mappings", International Journal of Foundations of Computer Science, 21:5 (2010), 799-815.
  38. (with A. Jeż) "Univariate equations over sets of natural numbers", Fundamenta Informaticae, 104:4 (2010), 329-348.
  39. (with G. Jirásková) "Nondeterministic state complexity of positional addition", Journal of Automata, Languages and Combinatorics, 15:1-2 (2010), 121-133.
  40. (with T. Lehtinen) "On equations over sets of numbers and their limitations", International Journal of Foundations of Computer Science, 22:2 (2011), 377-393.
  41. "A simple P-complete problem and its language-theoretic representations", Theoretical Computer Science, 412:1-2 (2011), 68-82.
  42. (with A. Jeż) "Complexity of equations over sets of natural numbers", Theory of Computing Systems, 48:2 (2011), 319-342.
  43. (with G. Jirásková) "On the state complexity of star of union and star of intersection", Fundamenta Informaticae, 109:2 (2011), 161-178.
  44. (with A. Jeż) "One-nonterminal conjunctive grammars over a unary alphabet", Theory of Computing Systems, 49:2 (2011), 319-342.
  45. "Expressive power of LL(k) Boolean grammars", Theoretical Computer Science, 412:39 (2011), 5132-5155.
  46. (with M. Kunc) "State complexity of union and intersection for two-way nondeterministic finite automata", Fundamenta Informaticae, 110:1-4 (2011), 231-239.
  47. (with A. Jeż) "Representing hyper-arithmetical sets by equations over sets of integers", Theory of Computing Systems, 51:2 (2012), 196-228.
  48. (with O. Yakimova) "Language equations with complementation: Expressive power", Theoretical Computer Science, 416 (2012), 71-86.
  49. (with P. Rondogiannis) "On the expressive power of univariate equations over sets of natural numbers", Information and Computation, 212 (2012), 1-14.
  50. "Unambiguous finite automata over a unary alphabet", Information and Computation, 212 (2012), 15-36.
  51. "Language equations with symmetric difference", Fundamenta Informaticae, 116:1-4 (2012), 205-222.
  52. (with M. Kunc) "State complexity of operations on two-way finite automata over a unary alphabet", Theoretical Computer Science, 449 (2012), 106-118.
  53. (with C. Reitwießner) "Parsing Boolean grammars over a one-letter alphabet using online convolution", Theoretical Computer Science, 457 (2012), 149-157.
  54. (with F. Baader) "On language equations with one-sided concatenation", Fundamenta Informaticae, 126:1 (2013), 1-35.
  55. "Conjunctive and Boolean grammars: the true general case of the context-free grammars", Computer Science Review, 9 (2013), 27-59.
  56. (with T. Lehtinen) "Homomorphisms preserving deterministic context-free languages", International Journal of Foundations of Computer Science, 24:7 (2013), 1049-1066.
  57. "Parsing by matrix multiplication generalized to Boolean grammars", Theoretical Computer Science, 516 (2014), 101-120.
  58. (with A. Jeż) "Computational completeness of equations over sets of natural numbers", Information and Computation, 237 (2014), 56-94.
  59. (with M. Barash) "An extension of context-free grammars with one-sided context specifications", Information and Computation, 237 (2014), 268-293.
  60. (with K. Salomaa) "Descriptional complexity of unambiguous input-driven pushdown automata", Theoretical Computer Science, 566 (2015), 1-11.
  61. "Improved normal form for grammars with one-sided contexts", Theoretical Computer Science, 588 (2015), 52-72.
  62. (with M. Barash) "Two-sided context specifications in formal grammars", Theoretical Computer Science, 591 (2015), 134-153.
  63. (with M. Barash) "Linear grammars with one-sided contexts and their automaton representation", RAIRO Informatique Théorique et Applications, 49:2 (2015), 153-178.
  64. "On language equations with concatenation and various sets of Boolean operations", RAIRO Informatique Théorique et Applications, 49:3 (2015), 205-232.
  65. "Input-driven languages are linear conjunctive", Theoretical Computer Science, 618 (2016), 52-71.
  66. (with A. Jeż) "Least and greatest solutions of equations over sets of integers", Theoretical Computer Science, 619 (2016), 68-86.
  67. (with A. Jeż) "Equations over sets of integers with addition only", Journal of Computer and System Sciences, 82:6 (2016), 1007-1019.
  68. (with M. Barash) "Generalized LR parsing algorithm for grammars with one-sided contexts", Theory of Computing Systems, 61:2 (2017), 581-605.
  69. (with G. Jirásková) "On the state complexity of operations on two-way finite automata", Information and Computation, 253:1 (2017), 36-63.
  70. (with A. Jeż) "Unambiguous conjunctive grammars over a one-symbol alphabet", Theoretical Computer Science, 665 (2017), 13-39.
  71. (with K. Salomaa) "State complexity of operations on input-driven pushdown automata", Journal of Computer and System Sciences, 86 (2017), 207-228.
  72. (with M. Barash) "Linear-space recognition for grammars with contexts", Theoretical Computer Science, to appear.

Handbook chapters

  1. (with M. Kunc) "Language equations", in: J.-É. Pin (Ed.), Automata: from Mathematics to Applications, to appear.

Papers in refereed conference proceedings

  1. "Conjunctive grammars", Pre-proceedings of DCAGRS 2000 (London, Ontario, Canada, 27-29 July 2000).
  2. "Efficient automaton-based recognition for linear conjunctive languages", Implementation and Application of Automata (CIAA 2002, Tours, France, 3-5 July 2002), LNCS 2608, 169-181.
  3. "Whale Calf, a parser generator for conjunctive grammars", Implementation and Application of Automata (CIAA 2002, Tours, France, 3-5 July 2002), LNCS 2608, 213-220.
  4. "State complexity of linear conjunctive languages", Pre-proceedings of DCFS 2002 (London, Ontario, Canada, 21-24 August 2002), 256-270.
  5. "Automaton representation of linear conjunctive languages", Developments in Language Theory (Proceedings of DLT 2002, Kyoto, Japan, 18-21 September 2002), LNCS 2450, 393-404.
  6. "Decision problems for language equations with Boolean operations", Automata, Languages and Programming (ICALP 2003, Eindhoven, The Netherlands, 30 June-4 July 2003), LNCS 2719, 239-251.
  7. "Boolean grammars", Developments in Language Theory (DLT 2003, Szeged, Hungary, 7-11 July 2003), LNCS 2710, 398-410.
  8. "On the number of nonterminals in linear conjunctive grammars", Proceedings of DCFS 2003 (Budapest, Hungary, 12-14 July 2003), MTA SZTAKI, Budapest, 2003, 274-283.
  9. "A characterization of the arithmetical hierarchy by language equations", Pre-proceedings of DCFS 2004 (London, Ontario, Canada, 26-28 July 2004), 225-237.
  10. "The dual of concatenation", Mathematical Foundations of Computer Science (MFCS 2004, Prague, Czech Republic, 22-27 August 2004), LNCS 3153, 698-710.
  11. "On computational universality in language equations", Machines, Computations and Universality (MCU 2004, St.Petersburg, Russia, 21-24 September 2004), LNCS 3354, 292-303.
  12. "On the existence of a Boolean grammar for a simple programming language", Automata and Formal Languages (Proceedings of AFL 2005, 17-20 May 2005, Dobogókö, Hungary).
  13. (with M. Domaratzki and J. Shallit) "Enumeration of context-free languages and related structures", Proceedings of DCFS 2005 (Como, Italy, 30 June-2 July 2005), 85-96.
  14. (with G. Jirásková) "State complexity of cyclic shift", Proceedings of DCFS 2005 (Como, Italy, 30 June-2 July 2005), 182-193.
  15. "LR parsing for Boolean grammars", Developments in Language Theory (DLT 2005, Palermo, Italy, 4-8 July 2005), LNCS 3572, 362-373.
  16. (with J. Karhumäki and M. Kunc) "Computing by commuting", Workshop on Semigroups and Automata (Lisbon, Portugal, 16 July 2005), 69-77.
  17. "Strict language inequalities and their decision problems", Mathematical Foundations of Computer Science (MFCS 2005, Gdańsk, Poland, 29 August-2 September 2005), LNCS 3618, 708-719.
  18. "Language equations with symmetric difference", Computer Science in Russia (CSR 2006, St. Petersburg, Russia, 8-12 June 2006), LNCS 3967, 292-303.
  19. (with O. Yakimova) "Language equations with complementation", Developments in Language Theory (DLT 2006, Santa Barbara, USA, 26-29 June 2006), LNCS 4036, 420-432.
  20. (with J. Karhumäki and M. Kunc) "Communication of two stacks and rewriting", Automata, Languages and Programming (ICALP 2006, Venice, Italy, 9-16 July 2006), LNCS 4052, 468-479.
  21. (with F. Baader) "Complexity of language equations with one-sided concatenation and all Boolean operations", 20th International Workshop on Unification (UNIF 2006, Seattle, USA, 11 August 2006), 59-73.
  22. "Unambiguous Boolean grammars", Pre-proceedings of LATA 2007 (Tarragona, Spain, 29 March-4 April 2007), 473-484.
  23. (with A. Jeż) "Language equations with positional addition", Theory and Applications of Language Equations (TALE 2007, Turku, Finland, 2 July 2007), TUCS GP 44, 54-66.
  24. "Expressive power of LL(k) Boolean grammars", Fundamentals of Computation Theory (FCT 2007, Budapest, Hungary, 27-30 August 2007), LNCS 4639, 446-457.
  25. (with A. Jeż) "Conjunctive grammars over a unary alphabet: undecidability and unbounded growth", Computer Science in Russia (CSR 2007, Ekaterinburg, Russia, 3-7 September 2007), LNCS 4649, 168-181.
  26. "A simple P-complete problem and its representations by language equations", Machines, Computations and Universality (MCU 2007, Orléans, France, 10-14 September 2007), LNCS 4664, 267-278.
  27. (with A. Jeż) "Complexity of solutions of equations over sets of natural numbers", 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2008, Bordeaux, France, 21-23 February 2008), Dagstuhl Seminar Proceedings 08001, 373-383.
  28. (with O. H. Ibarra and J. Karhumäki) "On stateless multihead automata: hierarchies and the emptiness problem", LATIN 2008: Theoretical Informatics (Búzios, Brazil, April 7-11 2008), LNCS 4957, 94-105.
  29. (with T. Lehtinen) "Boolean grammars and gsm mappings", Automata and Formal Languages (AFL 2008, Balatonfüred, Hungary, 27-30 May 2008), 269-280.
  30. (with A. Jeż) "On the computational completeness of equations over sets of natural numbers", Automata, Languages and Programming (ICALP 2008, Reykjavík, Iceland, July 6-13 2008), part II, LNCS 5126, 63-74.
  31. (with P. Rondogiannis) "On the expressive power of univariate equations over sets of natural numbers", IFIP Intl. Conf. on Theoretical Computer Science (TCS 2008, Milan, Italy, 8-10 September 2008), IFIP vol. 273, 215-227.
  32. (with G. Jirásková) "On the state complexity of operations on two-way finite automata", Developments in Language Theory (DLT 2008, Kyoto, Japan, 16-19 September 2008), LNCS 5257, 443-454.
  33. (with C. Reitwießner) "Conjunctive grammars with restricted disjunction", SOFSEM 2009: Theory and Practice of Computer Science (Spindlerův Mlýn, Czech Republic, 24-30 January 2009), LNCS 5404, 425-436.
  34. (with A. Jeż) "Equations over sets of natural numbers with addition only", 26th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2009, Freiburg, Germany, 26-28 February 2009), Dagstuhl Seminar Proceedings 09001, 577-588.
  35. (with T. Lehtinen) "On equations over sets of numbers and their limitations", Developments in Language Theory (DLT 2009, Stuttgart, Germany, 30 June-3 July 2009), LNCS 5583, 360-371.
  36. (with G. Jirásková) "Nondeterministic state complexity of positional addition", Pre-proceedings of DCFS 2009 (Magdeburg, Germany, 6-9 July 2009), 199-210.
  37. (with A. Jeż) "One-nonterminal conjunctive grammars over a unary alphabet", Computer Science in Russia (CSR 2009, Novosibirsk, Russia, 18-23 August 2009), LNCS 5675, 191-202.
  38. (with A. Jeż) "On equations over sets of integers", 27th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2010, Nancy, France, 4-6 March 2010), 477-488.
  39. "Fast parsing for Boolean grammars: a generalization of Valiant's algorithm", Developments in Language Theory (DLT 2010, London, Ontario, Canada, 17-20 August 2010), LNCS 6224, 340-351.
  40. (with T. Lehtinen) "On language equations XXK=XXL and XM=N over a unary alphabet", Developments in Language Theory (DLT 2010, London, Ontario, Canada, 17-20 August 2010), LNCS 6224, 291-302.
  41. "Unambiguous finite automata over a unary alphabet", Mathematical Foundations of Computer Science (MFCS 2010, Brno, Czech Republic, 23-27 August 2010), LNCS 6281, 556-567.
  42. (with A. Jeż) "Least and greatest solutions of equations over sets of integers", Mathematical Foundations of Computer Science (MFCS 2010, Brno, Czech Republic, 23-27 August 2010), LNCS 6281, 441-452.
  43. "Comparing linear conjunctive languages to subfamilies of the context-free languages", SOFSEM 2011: Theory and Practice of Computer Science (Nový Smokovec, Slovakia, 22-28 January 2011), LNCS 6543, 431-443.
  44. (with K. Salomaa) "Descriptional complexity of unambiguous nested word automata", Language and Automata Theory and Applications (LATA 2011, Tarragona, Spain, 26-31 May 2011), LNCS 6638, 414-426.
  45. (with M. Kunc) "Describing periodicity in two-way deterministic finite automata using transformation semigroups", Developments in Language Theory (DLT 2011, Milan, Italy, 19-22 July 2011), LNCS 6795, 324-336.
  46. (with M. Kunc) "State complexity of operations on two-way deterministic finite automata over a unary alphabet", Descriptional Complexity of Formal Systems (DCFS 2011, Limburg, Germany, 25-27 July 2011), LNCS 6808, 222-234.
  47. (with K. Salomaa) "State complexity of operations on input-driven pushdown automata", Mathematical Foundations of Computer Science (MFCS 2011, Warsaw, Poland, 22-26 August 2011), LNCS 6907, 485-496.
  48. (with M. Barash) "Defining contexts in context-free grammars", Language and Automata Theory and Applications (LATA 2012, A Coruña, Spain, 5-9 March 2012), LNCS 7183, 106-118.
  49. (with F. Baader) "Solving language equations and disequations with applications to disunification in description logics and monadic set constraints", Logic for Programming, Artificial Intelligence and Reasoning (LPAR 2012, Mérida, Venezuela, 10-15 March 2012), LNCS 7180, 107-121.
  50. (with A. Jeż) "On the number of nonterminal symbols in unambiguous conjunctive grammars", Descriptional Complexity of Formal Systems (DCFS 2012, Braga, Portugal, 23-25 July 2012), LNCS 7386, 183-195.
  51. (with T. Lehtinen) "Homomorphisms preserving deterministic context-free languages", Developments in Language Theory (DLT 2012, Taipei, Taiwan, 14-17 August 2012), LNCS 7410, 154-165.
  52. "Non-erasing variants of the Chomsky-Schützenberger theorem", Developments in Language Theory (DLT 2012, Taipei, Taiwan, 14-17 August 2012), LNCS 7410, 121-129.
  53. (with A. Jeż) "Unambiguous conjunctive grammars over a one-letter alphabet", Developments in Language Theory (DLT 2013, Paris, France, 18-21 June 2013), LNCS 7907, 277-288.
  54. "Improved normal form for grammars with one-sided contexts", Descriptional Complexity of Formal Systems (DCFS 2013, London, Ontario, Canada, 22-25 July 2013), LNCS 8031, 205-216.
  55. (with V. Geffert) "One-way simulation of two-way finite automata over small alphabets", NCMA 2013 (Umeå, Sweden, 13-14 August 2013), books@ocg.at 294, 151-162.
  56. (with M. Kunc) "Reversibility of computations in graph-walking automata", Mathematical Foundations of Computer Science (MFCS 2013, Klosterneuburg, Austria, 26-30 August 2013), LNCS 8087, 595-606.
  57. (with M. Barash) "Linear grammars with one-sided contexts and their automaton representation", LATIN 2014: Theoretical Informatics (Montevideo, Uruguay, 31 March-4 April 2014), LNCS 8392, 190-201.
  58. (with M. Barash) "Grammars with two-sided contexts", Automata and Formal Languages (AFL 2014, Szeged, Hungary, 27-29 May 2014), EPTCS 151, 94-108.
  59. (with V. Geffert) "Transforming two-way alternating finite automata to one-way nondeterministic automata", Mathematical Foundations of Computer Science (MFCS 2014, Budapest, Hungary, 25-29 August 2014), Part I, LNCS 8634, 291-302.
  60. (with M. Barash) "Generalized LR parsing for grammars with contexts", Computer Science in Russia (CSR 2015, Listvyanka, Lake Baikal, Russia, 13-17 July 2015), LNCS 9139, 67-79.
  61. "The hardest language for conjunctive grammars", Computer Science in Russia (CSR 2016, St. Petersburg, Russia, 9-13 June 2016), LNCS 9691, 340-351.
  62. (with F. Baader and P. Marantidis) "Approximately solving set equations", 30th International Workshop on Unification (UNIF 2016, Porto, Portugal, 26 June 2016), informal proceedings, 37-42.
  63. (with D. Itsykson and V. Oparin) "Computational and proof complexity of partial string avoidability", 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016, Krakow, Poland, 22-26 August 2016), LIPIcs 58, 51:1-51:13.
  64. (with F. Baader and P. Marantidis) "Approximate unification in the description logic FL0", Logics in Artificial Intelligence - 15th European Conference (JELIA 2016, Larnaca, Cyprus, 9-11 November 2016), LNAI 10021, 49-63.
  65. (with K. Salomaa) "Edit distance neighbourhoods of input-driven pushdown automata", Computer Science in Russia (CSR 2017, Kazan, Russia, 8-12 June 2017), LNCS 10304, 260-272.
  66. (with K. Salomaa) "The quotient operation on input-driven pushdown automata", Descriptional Complexity of Formal Systems (DCFS 2017, Milan, Italy, 3-5 July 2017), LNCS 10316, 299-310.
  67. (with S. Kuznetsov) "Conjunctive categorial grammars", Proceedings of the 15th Meeting on the Mathematics of Language (MOL 2017, London, UK, 13-14 July 2017), ACL, 141-151.

Invited conference papers

  1. "Seven families of language equations", AutoMathA 2007, Palermo, Italy, 18-22 June 2007.
  2. "Equations over sets of natural numbers", Finnish Mathematics Days 2008, Helsinki, Finland, 3-4 January 2008.
  3. "Formal grammars: a mathematical model of syntax", Spring School-A Week of Doctoral Studies (TDPO 2011, High Tatras, Slovakia, 16-20 May 2011), 3-9.
  4. "Parsing algorithms for formal grammars", Spring School-A Week of Doctoral Studies (TDPO 2011, High Tatras, Slovakia, 16-20 May 2011), 63-72.
  5. "Operations in formal grammars", 16th Mons Theoretical Computer Science Days (JM 2016, Liège, Belgium, 5-9 September 2016).

Contributions to other people's invited talks

  1. (for K. Salomaa) "Input-driven pushdown automata: nondeterminism and unambiguity", NCMA 2013 (Umeå, Sweden, 13-14 August 2013), books@ocg.at 294, 31-33.
  2. (for K. Salomaa) "Input-driven pushdown automata with limited nondeterminism", Developments in Language Theory (DLT 2014, Ekaterinburg, Russia, 26-29 August 2014), LNCS 8633, 84-102.

Contributions to refereed collections of papers

  1. (with X. Piao and K. Salomaa) "Descriptional complexity of input-driven pushdown automata", In: H. Bordihn, M. Kutrib, B. Truthe (Eds.), Languages Alive: Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday, LNCS 7300, 2012, 186-206.
  2. (with J. Karhumäki) "On the determinization blowup for finite automata recognizing equal-length languages", In: C. Calude, R. Freivalds, I. Kazuo (Eds.), Computing with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday, LNCS 8808, 2014, 71-82.

Non-refereed conference papers

  1. "O rasshirenii formalizma kontekstno-svobodnykh grammatik operatsiei peresecheniya" (On augmenting the formalism of context-free grammars with an intersection operation), in Russian, Trudy IV Mezhdunarodnoi konferentsii "Diskretnye modeli v teorii upravlyayushchikh sistem" (Proceedings of the Fourth International conference "Discrete models in the theory of control systems", June 2000), 106-109.
  2. "O P-polnote zadachi prinadlezhnosti dlya kon'yunktivnykh grammatik" (On P-completeness of the membership problem for conjunctive grammars), in Russian, Diskretnaya matematika i matematicheskaya kibernetika: trudy mezhdunarodnoi shkoly-seminara, Ratmino, 2001 (Proceedings of the International School-Seminar on Discrete Mathematics and Mathematical Cybernetics).
  3. "On systems of language equations with Boolean operations", (Algebraic Systems, Formal Languages and Conventional and Unconventional Computation Theory, Kyoto, Japan, September 24-26, 2002), 165-176.
  4. "Sistemy yazykovykh uravnenii i zamknutye klassy funktsii algebry logiki" (Systems of language equations and closed classes of logic algebra functions), in Russian, Trudy V Mezhdunarodnoi konferentsii "Diskretnye modeli v teorii upravlyayushchikh sistem" (Proceedings of the Fifth International conference "Discrete models in the theory of control systems", May 2003), 56-64.
  5. "Yazykovye uravneniya i modeli vychislenii" ("Language equations and models of computation"), in Russian, Diskretnye modeli v teorii upravlyayushchikh sistem: VI Mezhdunarodnaya konferentsiya (Proceedings of the VI international conference on discrete models in control systems theory, December 7-11, 2004), 129-134.
  6. "Yazykovye uravneniya: popytka klassifikatsii" ("Language equations: an attempt of classification"), in Russian, XIV Mezhdunarodnaya konferentsiya "Problemy teoreticheskoi kibernetiki" (XIV International Conference "Problems of Theoretical Cybernetics", Penza, Russia, May 23-28, 2005).
  7. (with J. Karhumäki and M. Kunc) "O neupravlyaemoi perezapisi slov" ("On uncontrolled word rewriting"), in Russian, Diskretnye modeli v teorii upravlyayushchikh sistem: VII Mezhdunarodnaya konferentsiya (Proceedings of the VII international conference on discrete models in control systems theory, March 4-6, 2006).
  8. "Representing a P-complete problem by small trellis automata", Workshop on the Complexity of Simple Programs (Cork, Ireland, December 6-7, 2008), Cork University Press, 2008.
  9. (with C. Reitwießner) "Parsing unary Boolean grammars using online convolution", Advances and Applications of Automata on Words and Trees (Dagstuhl seminar 10501, 12-17 December 2010).
  10. "Language equations: a story of computational completeness", Advances and Applications of Automata on Words and Trees (Dagstuhl seminar 10501, 12-17 December 2010).
  11. "Formal grammars: reappraising the foundations", First Russian-Finnish Symposium on Discrete Mathematics (St. Petersburg, Russia, 21-24 September 2011).

Other non-refereed publications

  1. "An overview of conjunctive grammars", in: Paun, Rozenberg, Salomaa (Eds.), Current Trends in Theoretical Computer Science: The Challenge of the New Century, Vol. 2, World Scientific, 2004, 545-566.
  2. "Nine open problems for conjunctive and Boolean grammars", Bulletin of the EATCS, 91 (2007), 96-119.
  3. (with K. Salomaa) "Complexity of input-driven pushdown automata", SIGACT News, 45:2 (2014), 47-67.

Manuscripts submitted for publication

  1. "Describing the syntax of programming languages using conjunctive and Boolean grammars", February 2016.
  2. "Hardest languages for conjunctive and Boolean grammars", May 2017.
  3. (with A. Jeż) "On the number of nonterminal symbols in unambiguous conjunctive grammars", October 2017.
  4. (with K. Salomaa) "State complexity of the quotient operation on input-driven pushdown automata", November 2017.

Non-scientific articles

  1. (with M. Domaratzki and K. Salomaa) "Report on CIAA 2004", Bulletin of the EATCS, 84 (2004), 231-234.

Volumes and special issues edited

  1. (with M. Domaratzki, K. Salomaa and S. Yu) Implementation and Application of Automata (Proceedings of CIAA 2004, Kingston, Ontario, Canada, 22-24 July 2004), LNCS 3317, Springer-Verlag, 2004.
  2. (with M. Kunc) Theory and Applications of Language Equations (Proceedings of TALE 2007, Turku, Finland, 2 July 2007), TUCS General Publications vol. 44, Turku Centre for Computer Science, Finland, 2007.
  3. (with T. Harju, G. Rozenberg and A. Salomaa) "A bird's eye's view of theory", Theoretical Computer Science, 410:30-32 (2009), special issue in honour of Juhani Karhumäki.
  4. (with H. Jürgensen and J. Karhumäki) Descriptional Complexity of Formal Systems (Proceedings of DCFS 2014, Turku, Finland, 5-8 August 2014), LNCS 8614, Springer-Verlag, 2014.
  5. (with H. Jürgensen and J. Karhumäki) "Descriptional complexity of formal systems", Theoretical Computer Science, 610:A (2016), special issue for DCFS 2014.
  6. (with J. Shallit) Descriptional Complexity of Formal Systems (Proceedings of DCFS 2015, Waterloo, Canada, 25-27 June 2015), LNCS 9118, Springer-Verlag, 2015.
  7. (with J. Shallit) "Descriptional complexity of formal systems", Information and Computation, to appear, special issue for DCFS 2015.
  8. (with J. Kari) SI for SOFSEM 2016, International Journal of Foundations of Computer Science, in progress.

Courses taught

January-May 2001.
"Introduction to theoretical computer science", Moscow State University named after M. V. Lomonosov, Advanced Education and Science Centre (Kolmogorov College), Moscow, Russia.
March 2006.
"Languages", International Ph.D. School in Formal Languages and Applications, Research Group on Mathematical Linguistics, Rovira i Virgili University, Tarragona, Spain.
January-April 2009.
"Formal grammars", University of Turku, Finland. 56+28 hours.
October 2009.
"Formal languages and parsing", Steklov Institute of Mathematics of Russian Academy of Sciences, St. Petersburg, Russia. Mini-course, 20 hours.
November 2009.
"Formal grammars", University of Wrocław, Poland. Mini-course, 18 hours.
May-June 2012.
"Formal grammars", University of Košice, Slovakia. Mini-course, 16 hours.
January-April 2013.
"Formal grammars", University of Turku, Finland. 56+28 hours.
September 2014.
"Formal grammars", St. Petersburg Academic University, 30 hours.
September-December 2016.
"Theoretical computer science 1" (Discrete mathematics and algorithms), St. Petersburg State University. 45+14 hours.
September-December 2016.
"Theoretical computer science 3" (automata, formal grammars, computational complexity), St. Petersburg State University. 32 hours.
January 2017.
"Theoretical computer science" (for high school students), Sirius Education Centre, Sochi, Russia. Mini-course, 10 hours.
February-March 2017.
"Theoretical computer science 2" (algorithms), St. Petersburg State University. 24 hours.
November-December 2017.
"Theoretical computer science 1, second part" (Algorithms), St. Petersburg State University. 24+14 hours.
September-December 2017.
"Theoretical computer science 3" (automata, formal grammars, computational complexity), St. Petersburg State University. 32 hours.

Software projects

March 1999-ca. 2002.
Dolphin, a lexical analyzer generator. Available at http://users.utu.fi/aleokh/dolphin/.
April 1999-ca. 2002.
(with V. Prus) Whale, a parser generator. Available at http://users.utu.fi/aleokh/whale/.
August 1999-present.
Whale Calf, a parser generator for conjunctive grammars. Available at http://users.utu.fi/aleokh/whalecalf/.

Other scientific activities

Personal Information

Contact Information




File translated from TEX by TTHgold, version 4.00.
On 23 Nov 2017, 15:33.