Find Research outputs

Search results

• 2012

  Non-erasing variants of the Chomsky-Schützenberger theorem

  Okhotin, A., 20 Aug 2012, Developments in Language Theory - 16th International Conference, DLT 2012, Proceedings. p. 121-129 9 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7410 LNCS).

  Research output › › peer-review

  • Context free languages
  • Context-free Languages
  • Homomorphism
  • Language
  • Formal languages
  20 Citations (Scopus)

• Descriptional complexity of input-driven pushdown automata

  Okhotin, A., Piao, X. & Salomaa, K., 8 Oct 2012, Languages Alive: Essays Dedicated to Jurgen Dassow on the Occasion of His 65th Birthday. Bordihn, H., Kutrib, M. & Truthe, B. (eds.). p. 186-206 21 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7300 LNAI).

  Research output › › peer-review

  • Descriptional Complexity
  • Pushdown Automata
  • Automata
  • Costs
  • State Complexity
  7 Citations (Scopus)

• Solving language equations and disequations with applications to disunification in description logics and monadic set constraints

  Baader, F. & Okhotin, A., 21 Mar 2012, Logic for Programming, Artificial Intelligence, and Reasoning - 18th International Conference, LPAR-18, Proceedings. p. 107-121 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7180 LNCS).

  Research output › › peer-review

  • Description Logics
  • Automata
  • Language
  • Color
  • Boolean Operation
  5 Citations (Scopus)
• 2018

  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)

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

  Computational and proof complexity of partial string avoidability

  Itsykson, D., Okhotin, A. & Oparin, V., 1 Aug 2016, 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016. Muscholl, A., Faliszewski, P. & Niedermeier, R. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 51. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 58).

  Research output › › peer-review

  • Computational complexity
  • Polynomials
• 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)

• 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 ›
• 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
  9 Citations (Scopus)
• 2012

  On the expressive power of univariate equations over sets of natural numbers

  Okhotin, A. & Rondogiannis, P., 1 Mar 2012, In: Information and Computation. 212, p. 1-14 14 p.

  Research output › peer-review

  Open Access

  • Expressive Power
  • Natural number
  • Univariate
  • Exponential Growth
  • Additive Basis
  11 Citations (Scopus)

• Language equations with symmetric difference

  Okhotin, A., 28 May 2012, In: Fundamenta Informaticae. 116, 1-4, p. 205-222 18 p.

  Research output › peer-review

  • Language
  • Concatenation
  • Recursively Enumerable Set
  • Solution Existence
  • Expressive Power
  4 Citations (Scopus)
• 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 › peer-review

  Open Access

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

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

  Kunc, M. & Okhotin, A., 31 Aug 2012, In: Theoretical Computer Science. 449, p. 106-118 13 p.

  Research output › peer-review

  Open Access

  • State Complexity
  • Unary
  • Finite automata
  • Finite Automata
  • Stars
  11 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 › peer-review

  Open Access

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

• An extension of context-free grammars with one-sided context specifications

  Barash, M. & Okhotin, A., 1 Jan 2014, In: Information and Computation. 237, p. 268-293 26 p.

  Research output › peer-review

  Open Access
  15 Citations (Scopus)
• 2017

  The Quotient Operation on Input-Driven Pushdown Automata

  Okhotin, A. & Salomaa, K., 2017, In: Lecture Notes in Computer Science. 10316, p. 299-310

  Research output › peer-review
  3 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)
• 2017

  Generalized LR Parsing Algorithm for Grammars with One-Sided Contexts

  Barash, M. & Okhotin, A., 2017, In: Theory of Computing Systems. 61, 2, p. 581-605

  Research output
  8 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 › peer-review

  • Unification
  • Substitution reactions
  • Modulo
  • Testing
  • Equational Theory
• 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 › › peer-review

  • Finite automata
  • Finite Automata
  • Image Compression
  • Blow-up
  • Language
• 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

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

  Equations over sets of integers with addition only

  Jez, A. & Okhotin, A., 2016, In: Journal of Computer and System Sciences. 82, 6, p. 1007-1019

  Research output

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

  Complexity of Equations over Sets of Natural Numbers

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

  Research output › peer-review

  • Natural number
  • Pipe
  • Completeness
  • Grammar
  • System of equations
  22 Citations (Scopus)

• On the state complexity of star of union and star of intersection

  Jirásková, G. & Okhotin, A., 16 Sep 2011, In: Fundamenta Informaticae. 109, 2, p. 161-178 18 p.

  Research output › peer-review

  • State Complexity
  • Stars
  • Star
  • Union
  • Intersection
  12 Citations (Scopus)
• 2020

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

  On the state complexity of operations on two-way finite automata

  Jiraskova, G. & Okhotin, A., 2017, In: Information and Computation. 253, 1, p. 36-63

  Research output
  2 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 › peer-review

  Open Access

  • Pipe
  • Integer
  • Union
  • Testing
  • Subtraction
  6 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
• 2012

  Language equations with complementation: Expressive power

  Okhotin, A. & Yakimova, O., 27 Jan 2012, In: Theoretical Computer Science. 416, p. 71-86 16 p.

  Research output › peer-review

  Open Access

  • Formal languages
  • Complementation
  • Expressive Power
  • Computer science
  • Language
  6 Citations (Scopus)
• 2016

  Input-driven languages are linear conjunctive

  Okhotin, A., 2016, In: Theoretical Computer Science. 618, p. 52-71

  Research output
  10 Citations (Scopus)
• 2014

  Computational completeness of equations over sets of natural numbers

  Jez, A. & Okhotin, A., 1 Jan 2014, In: Information and Computation. 237, p. 56-94 39 p.

  Research output › peer-review

  Open Access

  • Natural number
  • Completeness
  • Arithmetical Hierarchy
  • Decision problem
  • Family
  8 Citations (Scopus)
• 2012

  Unambiguous finite automata over a unary alphabet

  Okhotin, A., 1 Mar 2012, In: Information and Computation. 212, p. 15-36 22 p.

  Research output › peer-review

  Open Access

  • Unary
  • Finite automata
  • Finite Automata
  • G-function
  • Stars
  22 Citations (Scopus)
• 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 › peer-review

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

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

• 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)
• 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 › › peer-review

  • Finite automata
  • Finite Automata
  • Automata
  • Necessary
  • Nondeterminism
  6 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
  • Stars
  • Star
  • Binary
• 2011

  A simple P-complete problem and its language-theoretic representations

  Okhotin, A., 1 Jan 2011, In: Theoretical Computer Science. 412, 1-2, p. 68-82 15 p.

  Research output › peer-review

  Open Access

  • Formal languages
  • Grammar
  • Language
  • Networks (circuits)
  • Formal Languages
  4 Citations (Scopus)
• 2014

  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 › peer-review

  Open Access

  • Context free grammars
  • Specifications
• 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)
• 2018

  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)
• 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 › peer-review

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

• State complexity of union and intersection for two-way nondeterministic finite automata

  Kunc, M. & Okhotin, A., 20 Sep 2011, In: Fundamenta Informaticae. 110, 1-4, p. 231-239 9 p.

  Research output › peer-review

  • State Complexity
  • Finite automata
  • Finite Automata
  • Union
  • Intersection
  6 Citations (Scopus)

• Describing periodicity in two-way deterministic finite automata using transformation semigroups

  Kunc, M. & Okhotin, A., 29 Jul 2011, Developments in Language Theory - 15th International Conference, DLT 2011, Proceedings. p. 324-336 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6795 LNCS).

  Research output › › peer-review

  • Transformation Semigroups
  • Deterministic Finite Automata
  • Finite automata
  • Periodicity
  • Strings
  20 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
• 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 › › peer-review

  • Pushdown Automata
  • Nondeterminism
  • Path
  2 Citations (Scopus)
• 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)