Find Research outputs

Search results

• 2017

  Unambiguous conjunctive grammars over a one-symbol alphabet

  Jez, A. & Okhotin, A., 2017, In: Theoretical Computer Science. 665, p. 13-39

  Research output
  3 Citations (Scopus)
• 2018

  A Tale of Conjunctive Grammars

  Okhotin, A., 1 Sep 2018, Developments in Language Theory - 22nd International Conference, DLT 2018, Proceedings. Hoshi, M. & Seki, S. (eds.). Springer Nature, p. 36-59 24 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11088 LNCS).

  Research output › › peer-review

  • Context free grammars
  • Narrative
  • Grammar
  • Syntactics
  • Context-free Grammar
  2 Citations (Scopus)

• Formal Languages over GF(2)

  Bakinova, E., Basharin, A., Batmanov, I., Lyubort, K., Okhotin, A. & Sazhneva, E., 1 Jan 2018, Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings. Springer Nature, p. 68-79 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10792 LNCS).

  Research output › › peer-review

  • Formal languages
  • Formal Languages
  • Concatenation
  • Computational complexity
  • Union
  9 Citations (Scopus)

• Further closure properties of input-driven pushdown automata

  Okhotin, A. & Salomaa, K., 1 Jan 2018, Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings. Springer Nature, p. 224-236 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10952 LNCS).

  Research output › › peer-review

  • Pushdown Automata
  • Closure Properties
  • Insertion
  • Deletion
  • Square root
  1 Citation (Scopus)

• Linear-space recognition for grammars with contexts

  Barash, M. & Okhotin, A., 6 Apr 2018, In: Theoretical Computer Science. 719, p. 73-85 13 p.

  Research output › peer-review

  • Context free grammars
  • Grammar
  • Syntactics
  • Linear Space
  • Context
  1 Citation (Scopus)

• On the number of nonterminal symbols in unambiguous conjunctive grammars

  Jez, A. & Okhotin, A., 1 Jan 2018, In: Fundamenta Informaticae. 162, 1, p. 43-72 30 p.

  Research output › peer-review

  • Formal languages
  • Grammar
  • Regular Languages
  • Strictly
  • Language

• Preface

  Shallit, J. & Okhotin, A., 1 Apr 2018, In: Information and Computation. 259, p. 161-161 1 p.

  Research output

• Preface

  Kari, J. & Okhotin, A., 1 Jun 2018, In: International Journal of Foundations of Computer Science. 29, 4, p. 457-459 3 p.

  Research output

• State complexity of unambiguous operations on deterministic finite automata

  Jirásková, G. & Okhotin, A., 1 Jan 2018, Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings. Springer Nature, p. 188-199 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10952 LNCS).

  Research output › › peer-review

  • State Complexity
  • Deterministic Finite Automata
  • Concatenation
  • Finite automata
  • Stars
  1 Citation (Scopus)

• Towards Exact State Complexity Bounds for Input-Driven Pushdown Automata

  Jirásková, G. & Okhotin, A., 1 Jan 2018, Developments in Language Theory - 22nd International Conference, DLT 2018, Proceedings. Hoshi, M. & Seki, S. (eds.). Springer Nature, p. 441-452 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11088 LNCS).

  Research output › › peer-review

  • State Complexity
  • Pushdown Automata
  • Restriction
  • Lower bound
  • Concatenation
  1 Citation (Scopus)

• Underlying Principles and Recurring Ideas of Formal Grammars

  Okhotin, A., 1 Jan 2018, Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings. Springer Nature, p. 36-59 24 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10792 LNCS).

  Research output › › peer-review

  • Context free grammars
  • Grammar
  • Context-free Grammar
  • Computational complexity
  • Language
  4 Citations (Scopus)
• 2019

  Edit distance neighbourhoods of input-driven pushdown automata

  Okhotin, A. & Salomaa, K., 19 Jul 2019, In: Theoretical Computer Science. 777, p. 417-430 14 p.

  Research output › peer-review

  • Context free languages
  • Edit Distance
  • Formal languages
  • Pushdown Automata
  • Strings
  3 Citations (Scopus)

• Further closure properties of input-driven pushdown automata

  Okhotin, A. & Salomaa, K., 17 Dec 2019, In: Theoretical Computer Science. 798, p. 65-77

  Research output › peer-review

  • Pushdown Automata
  • Closure Properties
  • Insertion
  • Deletion
  • Square root

• Graph-Walking Automata: From Whence They Come, and Whither They are Bound

  Okhotin, A., 1 Jul 2019, Implementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings. Hospodár, M. & Jirásková, G. (eds.). Springer Nature, p. 10-29 20 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11601 LNCS).

  Research output › › peer-review

  • Finite automata
  • Automata
  • Graph in graph theory
  • Finite Automata
  • Navigation

• Hardest languages for conjunctive and Boolean grammars

  Okhotin, A., 1 Jun 2019, In: Information and Computation. 266, p. 1-18 18 p.

  Research output › peer-review

  • Context free languages
  • Grammar
  • Context-free Languages
  • Language
  • Homomorphic
  1 Citation (Scopus)

• On the expressive power of GF(2)-grammars

  Makarov, V. & Okhotin, A., 1 Jan 2019, SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Královič, R., Pighizzini, G., Nawrocki, J. & Catania, B. (eds.). Springer Nature, p. 310-323 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11376 LNCS).

  Research output › › peer-review

  • Context free grammars
  • Formal languages
  • Concatenation
  • Expressive Power
  • Grammar
  4 Citations (Scopus)

• On the length of shortest strings accepted by two-way finite automata

  Dobronravov, E., Dobronravov, N. & Okhotin, A., 1 Jan 2019, Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings. Hofman, P. & Skrzypczak, M. (eds.). Springer Nature, p. 88-99 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11647 LNCS).

  Research output › › peer-review

  • Finite automata
  • Finite Automata
  • Strings
  • Automata
  • Deterministic Finite Automata

• Preface

  Martín-Vide, C., Shapira, D. & Okhotin, A., 1 Jan 2019, 13th International Conference on Language and Automata Theory and Applications. Vol. 11417 LNCS. p. V (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

  Research output ›

• State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages

  Okhotin, A. & Sazhneva, E., 1 Jul 2019, Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings. Konstantinidis, S., Hospodár, M. & Jirásková, G. (eds.). Springer Nature, p. 248-259 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11612 LNCS).

  Research output › › peer-review

  • State Complexity
  • Formal languages
  • Concatenation
  • Unary
  • Language
  3 Citations (Scopus)

• State Complexity of the Quotient Operation on Input-Driven Pushdown Automata

  Okhotin, A. & Salomaa, K., 1 Sep 2019, In: International Journal of Foundations of Computer Science. 30, 6-7, p. 1217-1235

  Research output › peer-review

  • State Complexity
  • Formal languages
  • Pushdown Automata
  • Quotient
  • Context free languages

• State complexity of unambiguous operations on finite automata

  Jirásková, G. & Okhotin, A., 17 Dec 2019, In: Theoretical Computer Science. 798, p. 52-64

  Research output › peer-review

  • State Complexity
  • Concatenation
  • Finite automata
  • Finite Automata
  • Stars
  3 Citations (Scopus)
• 2020

  Cyclic shift on multi-component grammars

  Okhotin, A. & Sorokin, A., 1 Jan 2020, Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings. Leporati, A., Martín-Vide, C., Shapira, D. & Zandron, C. (eds.). Springer Nature, p. 287-299 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12038 LNCS).

  Research output › › peer-review

  • Context free grammars
  • Grammar
  • Context-free Grammar
  • Rewriting Systems
  • Closed

• Extensions of unification modulo ACUI

  Baader, F., Marantidis, P., Mottet, A. & Okhotin, A., 1 Jun 2020, In: Mathematical Structures in Computer Science. 30, 6, p. 597-626

  Research output › peer-review

  • Unification
  • Substitution reactions
  • Modulo
  • Testing
  • Equational Theory

• Longer Shortest Strings in Two-Way Finite Automata

  Крымский, С. Т. & Okhotin, A., 2020, Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings. Jirásková, G. & Pighizzini, G. (eds.). Springer Nature, p. 104-116 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12442 LNCS).

  Research output › › peer-review

  • Finite automata
  • Finite Automata
  • Strings
  • Language
  • Motion

• On the transformation of ll(k)-linear grammars to ll(1)-linear

  Okhotin, A. & Olkhovsky, I., 1 Jun 2020, Computer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings. Fernau, H. (ed.). Springer Nature, p. 328-340 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12159 LNCS).

  Research output › › peer-review

  • Grammar
  • Blow-up
  • Lower bound

• Reversibility of computations in graph-walking automata

  Kunc, M. & Okhotin, A., Dec 2020, In: Information and Computation. 275, 104631.

  Research output › peer-review

  • Reversibility
  • Automata
  • Finite automata
  • Graph in graph theory
  • Turing machines

• State Complexity of GF(2)-inverse and GF(2)-star on Binary Languages

  Okhotin, A. & Sazhneva, E., 2020, Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings. Jirásková, G. & Pighizzini, G. (eds.). Springer Nature, p. 142-154 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12442 LNCS).

  Research output › › peer-review

  • State Complexity
  • Formal languages
  • Stars
  • Star
  • Binary