Find Research outputs — Saint Petersburg State University

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

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

20 Citations (Scopus)

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

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

9 Citations (Scopus)

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)

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

5 Citations (Scopus)

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

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

Open Access

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

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

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)

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

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)

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

7 Citations (Scopus)

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

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

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

1 Citation (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

11 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

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

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

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

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

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

2017

State complexity of operations on input-driven pushdown automata

Okhotin, A. & Salomaa, K., 2017, In: Journal of Computer and System Sciences. 86, p. 207-228

Research output

13 Citations (Scopus)

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)

2014

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)

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

Open Access

12 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

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

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

2017

Conjunctive categorial grammars

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

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

3 Citations (Scopus)

2011

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

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

4 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

22 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

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

2 Citations (Scopus)

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

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

4 Citations (Scopus)

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

3 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