Find Research outputs — Saint Petersburg State University

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

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

7 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

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

22 Citations (Scopus)

2020

Reversibility of computations in graph-walking automata

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

Research output

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

3 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

12 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

6 Citations (Scopus)

2012

Defining contexts in context-free grammars

Barash, M. & Okhotin, A., 12 Mar 2012, Language and Automata Theory and Applications - 6th International Conference, LATA 2012, Proceedings. p. 106-118 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7183 LNCS).

Research output

5 Citations (Scopus)

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

Open Access

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

Open Access

23 Citations (Scopus)

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)

The hardest language for conjunctive grammars

Okhotin, A., 2016, In : Lecture Notes in Computer Science. 9691, p. 340-351

Research output

1 Citation (Scopus)

2013

Conjunctive and boolean grammars: The true general case of the context-free grammars

Okhotin, A., 1 Aug 2013, In : Computer Science Review. 9, p. 27-59 33 p.

Research output

40 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

Open Access

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

20 Citations (Scopus)

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

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

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

Open Access

22 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

Open Access

8 Citations (Scopus)

2019

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

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

4 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

11 Citations (Scopus)

2015

Generalized LR parsing for grammars with contexts

Barash, M. & Okhotin, A., 1 Jan 2015, Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings. Beklemishev, L. D., Musatov, D. V. & Musatov, D. V. (eds.). Springer Nature, p. 67-79 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9139).

Research output

2 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 output

2 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

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

Open Access

4 Citations (Scopus)

2012

Language equations with symmetric difference

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

Research output

4 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

2 Citations (Scopus)

2019

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

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

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

Open Access

15 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

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)

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 output

20 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

Open Access

11 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

5 Citations (Scopus)

2015

Improved normal form for grammars with one-sided contexts

Okhotin, A., 11 Jul 2015, In : Theoretical Computer Science. 588, p. 52-72 21 p.

Research output

4 Citations (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

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

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

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

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

3 Citations (Scopus)

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

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

12 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

6 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

5 Citations (Scopus)

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

2015

On language equations with concatenation and various sets of boolean operations

Okhotin, A., 1 Jul 2015, In : RAIRO - Theoretical Informatics and Applications. 49, 3, p. 205-232 28 p.

Research output

2016

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

Filters for Research output

Search results