Find Research Outputs

Search concepts
Selected filters

Publication Year

  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011

Author

  • Александр Сергеевич Охотин
2012

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 outputpeer-review

6 Citations (Scopus)
2011
6 Citations (Scopus)
2015
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

9 Citations (Scopus)
2014
Open Access
8 Citations (Scopus)
2015
4 Citations (Scopus)
2014
Open Access

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, 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 outputpeer-review

4 Citations (Scopus)
2012
Open Access
21 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

21 Citations (Scopus)
2013

Unambiguous conjunctive grammars over a one-letter alphabet

Jez, A. & Okhotin, A., 19 Sep 2013, Developments in Language Theory - 17th International Conference, DLT 2013, Proceedings. p. 277-288 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7907 LNCS).

Research outputpeer-review

2 Citations (Scopus)
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 outputpeer-review

19 Citations (Scopus)
2011

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 outputpeer-review

18 Citations (Scopus)

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 outputpeer-review

5 Citations (Scopus)
2019

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

2015
Open Access
12 Citations (Scopus)
2011
Open Access
4 Citations (Scopus)

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
3 Citations (Scopus)
2012
Open Access
11 Citations (Scopus)
2019
2017
3 Citations (Scopus)
2 Citations (Scopus)
2015

Descriptional Complexity of Formal Systems: 17th International Workshop, DCFS 2015 Waterloo, ON, Canada, June 25-27, 2015 Proceedings

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

Research output

2018

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

1 Citation (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, 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 outputpeer-review

1 Citation (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, 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 outputpeer-review

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, 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 outputpeer-review

2 Citations (Scopus)
2012
Open Access
6 Citations (Scopus)
2019
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, 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 outputpeer-review

2 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 outputpeer-review

12 Citations (Scopus)
2018
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 outputpeer-review

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. Vol. 8808. p. 71-82 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

Research outputpeer-review

Open Access
14 Citations (Scopus)
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, 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

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, 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

2012

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 outputpeer-review

5 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

5 Citations (Scopus)
2019
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

Open Access
6 Citations (Scopus)

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

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

6 Citations (Scopus)
2017

Conjunctive categorial grammars

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

Research output

2015
4 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, 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 outputpeer-review

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, 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 outputpeer-review

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, 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 outputpeer-review

5 Citations (Scopus)