Research output

  1. State Complexity of Boolean Operations on Graph-Walking Automata

    Research output: Contribution to journal › Article › peer-review

  2. Improved bounds on the length of shortest strings accepted by two-way finite automata

    Research output: Contribution to journal › Article › peer-review

  3. 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

View all (15) »

Projects

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

    Project: Grant fulfilment › Grant stage fulfilment

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

    Project: Grant fulfilment › Total grant fulfilment

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

    Project: Grant fulfilment › Grant stage 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