Research

Последнее изменение: 29/10/2014 00:00:00

Current Research Interests

  • Combinatorial complexity of formal languages
    • Classification theorems, asymptotic formulas, and approximation algorithms for calculating complexity functions, growth rates etc.
    • Keywords: formal languages, combinatorial complexity, growth rate, finite automata
  • Combinatorics of infinite words, partial words, and circular words
    • Periodicity properties, avoidability relations, complexity functions, probabilistic issues
    • Keywords: infinite words, partial words, circular words, periodicity, interaction of periods, avoidability, complexity, expectation, random graph
  • Combinatorics of power-free, pattern-free, and Abelian power-free words and languages
    • Structural theorems, avoidability, complexity and probabilistic issues
    • Keywords: power-free words, avoidability, complexity, expectation
  • String algorithms
    • generating repetition-free words, searching and counting repetitions
    • Keywords: random repetition-free words, palindromes, Zimin words
  • Syntactic and relatively free monoids
    • Structural theorems, word problem decidability
    • Keywords: syntactic monoid, word problem, context equivalence