Research output

  1. From regular expressions to deterministic finite automata: 2^{\frac{n}{2}+\sqrt{n}(\log n)^{\Theta(1)}} states are necessary and sufficient

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

  2. Nondeterministic tree-walking automata are not closed under complementation

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

  3. Exact Descriptional Complexity of Determinization of Input-Driven Pushdown Automata

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

View all (12) »

Projects

  1. Создание и развитие международного математического центра мирового уровня «Санкт-Петербургский международный математический институт имени Леонарда Эйлера»

    Project: Grant fulfilment › Total grant fulfilment

  2. Аспекты сложности в теории формальных языков: 2025 г. этап 3

    Project: Grant fulfilment › Grant stage fulfilment

  3. Сложность конечных автоматов

    Project: Grant fulfilment › Total grant fulfilment

View all () »

Activities

  1. From regular expressions to deterministic finite automata: $2^{\frac{n}{2}+\sqrt{n}(\log n)^{\Theta(1)}}$ states are necessary and sufficient

    Activity: Conference talk types › Oral presentation

  2. Nondeterministic tree-walking automata are not closed under complementation

    Activity: Conference talk types › Oral presentation

View all (2) »

ID: 13760615