Find Research Outputs

Search results

• 2014

  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface

  Okhotin, A., Jürgensen, H. & Karhumäki, J., 1 Jan 2014, 16th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2014. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8614 LNCS).

  Research output
• 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
• 2016

  Approximate unification in the description logic FL0

  Baader, F., Marantidis, P. & Okhotin, A., 2016, In : Lecture Notes in Computer Science. 10021, p. 49-63

  Research output
  3 Citations (Scopus)
• 2015

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

  Parsing by matrix multiplication generalized to Boolean grammars

  Okhotin, A., 9 Jan 2014, In : Theoretical Computer Science. 516, p. 101-120 20 p.

  Research output

  Open Access

  • Parsing
  • Boolean Matrix
  • Matrix multiplication
  • Grammar
  • Context-free Grammar
  23 Citations (Scopus)
• 2018

  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

  • Context free grammars
  • Grammar
  • Context-free Grammar
  • Computational complexity
  • Language
  4 Citations (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

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

  Conjunctive categorial grammars

  Kuznetsov, S. & Okhotin, A., 2017, Proceedings of the 15th Meeting on the Mathematics of Language.

  Research output ›
• 2011

  Descriptional complexity of unambiguous nested word automata

  Okhotin, A. & Salomaa, K., 8 Jun 2011, Language and Automata Theory and Applications - 5th International Conference, LATA 2011, Proceedings. p. 414-426 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6638 LNCS).

  Research output › › peer-review

  • Descriptional Complexity
  • Automata
  • State Complexity
  • Complementation
  • Pushdown Automata
  5 Citations (Scopus)
• 2013

  Reversibility of computations in graph-walking automata

  Kunc, M. & Okhotin, A., 15 Oct 2013, Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings. p. 595-606 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8087 LNCS).

  Research output › › peer-review

  • Reversibility
  • Finite automata
  • Automata
  • Turing machines
  • Tapes
  10 Citations (Scopus)
• 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 › › peer-review

  • Cellular automata
  • Grammar
  • Automata
  • Turing machines
  • Context free grammars
  3 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 › › peer-review

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

  State complexity of operations on two-way deterministic finite automata over a unary alphabet

  Kunc, M. & Okhotin, A., 11 Aug 2011, Descriptional Complexity of Formal Systems - 13th International Workshop, DCFS 2011, Proceedings. p. 222-234 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6808 LNCS).

  Research output › › peer-review

  • State Complexity
  • Deterministic Finite Automata
  • Concatenation
  • Unary
  • Finite automata
  3 Citations (Scopus)
• 2015

  Descriptional Complexity of Formal Systems

  Shallit, J. & Okhotin, A., 1 Jan 2015, Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, Proceedings. Okhotin, A. & Shallit, J. (eds.). Springer Nature, (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9118).

  Research output › › peer-review
• 2020

  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

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

• 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

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

  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
  4 Citations (Scopus)
• 2017

  Edit distance neighbourhoods of input-driven pushdown automata

  Okhotin, A. & Salomaa, K., 2017, Computer Science – Theory and Applications: International Computer Science Symposium in Russia. p. 260-272 (Lecture Notes in Computer Science; vol. 10304).

  Research output
  6 Citations (Scopus)
• 2012

  Representing Hyper-arithmetical Sets by Equations over Sets of Integers

  Jez, A. & Okhotin, A., 1 Aug 2012, In : Theory of Computing Systems. 51, 2, p. 196-228 33 p.

  Research output

  Open Access

  • Pipe
  • Integer
  • Union
  • Testing
  • Subtraction
  6 Citations (Scopus)
• 2014

  Input-driven pushdown automata with limited nondeterminism (Invited Paper)

  Okhotin, A. & Salomaa, K., 1 Jan 2014, Developments in Language Theory - 18th International Conference, DLT 2014, Proceedings. Springer Nature, p. 84-102 19 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8633 LNCS).

  Research output

  • Pushdown Automata
  • Nondeterminism
  • Path
  2 Citations (Scopus)

• Grammars with two-sided contexts

  Barash, M. & Okhotin, A., 21 May 2014, In : Electronic Proceedings in Theoretical Computer Science, EPTCS. 151, p. 94-108 15 p.

  Research output

  Open Access

  • Context free grammars
  • Specifications
• 2019

  Hardest languages for conjunctive and Boolean grammars

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

  Research output

  • Context free languages
  • Grammar
  • Context-free Languages
  • Language
  • Homomorphic
• 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)
• 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

• Least and greatest solutions of equations over sets of integers

  Jez, A. & Okhotin, A., 2016, In : Theoretical Computer Science. 619, p. 68-86

  Research output
• 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)
• 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)
• 2015

  Linear grammars with one-sided contexts and their automaton representation

  Barash, M. & Okhotin, A., 1 Apr 2015, In : RAIRO - Theoretical Informatics and Applications. 49, 2, p. 153-158 6 p.

  Research output

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

  Homomorphisms preserving deterministic context-free languages

  Lehtinen, T. & Okhotin, A., 1 Nov 2013, In : International Journal of Foundations of Computer Science. 24, 7, p. 1049-1066 18 p.

  Research output

  • Context free languages
• 2019

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

  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
  8 Citations (Scopus)
• 2011

  Comparing linear conjunctive languages to subfamilies of the context-free languages

  Okhotin, A., 26 Jan 2011, SOFSEM 2011: Theory and Practice of Computer Science - 37th Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. p. 431-443 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6543 LNCS).

  Research output › › peer-review

  • Context free languages
  • Context-free Languages
  • Real-time
  • Cellular automata
  • Language
  11 Citations (Scopus)