Find Research outputs

Search results

• 2016

  Descriptional Complexity of Formal Systems

  Jürgensen, H., Karhumäki, J. & Okhotin, A., 11 Jan 2016, In : Theoretical Computer Science. 610, 1 p.

  Research output
• 2011

  One-Nonterminal Conjunctive Grammars over a Unary Alphabet

  Jez, A. & Okhotin, A., 1 Aug 2011, In : Theory of Computing Systems. 49, 2, p. 319-342 24 p.

  Research output

  • Context free grammars
  • Unary
  • Grammar
  • Finiteness
  • Language
  9 Citations (Scopus)
• 2018

  Preface

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

  Research output
• 2014

  Linear grammars with one-sided contexts and their automaton representation

  Barash, M. & Okhotin, A., 1 Jan 2014, LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Springer Nature, p. 190-201 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8392 LNCS).

  Research output

  • Cellular automata
  • Grammar
  • Automata
  • Turing machines
  • Context free grammars
  3 Citations (Scopus)

• Transforming two-way alternating finite automata to one-way nondeterministic automata

  Geffert, V. & Okhotin, A., 1 Jan 2014, Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Proceedings. PART 1 ed. Springer Nature, p. 291-302 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8634 LNCS, no. PART 1).

  Research output

  • Finite automata
  • Finite Automata
  • Automata
  • Necessary
  • Nondeterminism
  5 Citations (Scopus)
• 2019

  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

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

  Expressive power of LL(k) boolean grammars

  Okhotin, A., 9 Sep 2011, In : Theoretical Computer Science. 412, 39, p. 5132-5155 24 p.

  Research output

  Open Access

  • Formal languages
  • Expressive Power
  • Grammar
  • Language
  • Parsing
  4 Citations (Scopus)
• 2019

  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

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

  On the determinization blowup for finite automata recognizing equal-length languages

  Karhumäki, J. & Okhotin, A., 1 Jan 2014, Computing with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday. p. 71-82 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8808).

  Research output

  • Finite automata
  • Finite Automata
  • Image Compression
  • Blow-up
  • Language
• 2015

  Descriptional complexity of unambiguous input-driven pushdown automata

  Okhotin, A. & Salomaa, K., 1 Jan 2015, In : Theoretical Computer Science. 566, C, p. 1-11 11 p.

  Research output

  Open Access

  • Descriptional Complexity
  • Pushdown Automata
  • Automata
  • Complementation
  • Demonstrate
  12 Citations (Scopus)

• Two-sided context specifications in formal grammars

  Barash, M. & Okhotin, A., 2 Aug 2015, In : Theoretical Computer Science. 591, p. 134-153 20 p.

  Research output

  • Context free grammars
  • Grammar
  • Specification
  • Specifications
  • Context
  7 Citations (Scopus)
• 2020

  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
  • Star
  • Binary
  • Language
• 2019

  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

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

• 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

  • Context free languages
  • Edit Distance
  • Formal languages
  • Pushdown Automata
  • Strings
  3 Citations (Scopus)
• 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)
• 2020

  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

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

• 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
• 2018

  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

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

  On language equations with one-sided concatenation

  Baader, F. & Okhotin, A., 25 Nov 2013, In : Fundamenta Informaticae. 126, 1, p. 1-35 35 p.

  Research output

  • Formal languages
  • Concatenation
  • Language
  • Computer science
  • Formal Languages
  5 Citations (Scopus)
• 2019

  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)

• 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)