Find Research Outputs

Search concepts
Selected filters

    Publication Year

    2019
    2018
    2017
    2016
    2015
    2014
    2013
    2012
    2011
    2010

    Author

    Александр Сергеевич Охотин
2015
4 Citations (Scopus)
Cellular automata
Grammar
Automata
Context free grammars
Turing machines
2012
10 Citations (Scopus)
Open Access
Expressive Power
Natural number
Univariate
Exponential Growth
Additive Basis
2015
6 Citations (Scopus)

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-free Grammar
Context free languages
Boolean Operation
Formal languages
Concatenation
Context free grammars
2010
12 Citations (Scopus)

On stateless multihead automata: Hierarchies and the emptiness problem

Ibarra, O. H., Karhumäki, J. & Okhotin, A., 6 Jan 2010, In : Theoretical Computer Science. 411, 3, p. 581-593 13 p.

Research output

Open Access
Finite automata
Automata
Finite Automata
Hierarchy
Cell
2011
6 Citations (Scopus)
State Complexity
Finite Automata
Finite automata
Union
Intersection
2012
6 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

Descriptional Complexity
Pushdown Automata
Automata
State Complexity
Blow-up
2011
5 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 output

Descriptional Complexity
Automata
State Complexity
Pushdown Automata
Complementation
2012
11 Citations (Scopus)
Open Access
State Complexity
Unary
Finite Automata
Finite automata
Stars
2010
1 Citation (Scopus)

Computational power of two stacks with restricted communication

Karhumäki, J., Kunc, M. & Okhotin, A., 1 Sep 2010, In : Information and Computation. 208, 9, p. 1060-1089 30 p.

Research output

Open Access
Suffix
Prefix
Rewriting Systems
Communication
Expressive Power
2015
12 Citations (Scopus)
Open Access
Descriptional Complexity
Pushdown Automata
Automata
Complementation
Homomorphisms
2011
3 Citations (Scopus)

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

State Complexity
Deterministic Finite Automata
Concatenation
Unary
Finite automata
2010

Univariate equations over sets of natural numbers

Jez, A. & Okhotin, A., 1 Dec 2010, In : Fundamenta Informaticae. 104, 4, p. 329-348 20 p.

Research output

Natural number
Univariate
Undecidability
Decision problem
Universality
2011
3 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
Formal languages
Expressive Power
Grammar
Closure Properties
Formal Languages
4 Citations (Scopus)
Open Access
Formal languages
Grammar
Networks (circuits)
Formal Languages
Automata
2019
Context free languages
Grammar
Context-free Languages
Homomorphic
Operator
2010
10 Citations (Scopus)

On language equations XXK∈=∈XXL and XM∈=∈N over a unary alphabet

Lehtinen, T. & Okhotin, A., 4 Nov 2010, Developments in Language Theory - 14th International Conference, DLT 2010, Proceedings. p. 291-302 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6224 LNCS).

Research output

Unary
Levenberg-Marquardt
Universality
Unknown
Language
2012
6 Citations (Scopus)
Open Access
Pipe
Integer
Testing
Union
Expressive Power
2014
2 Citations (Scopus)

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 output

Pushdown Automata
Nondeterminism
Path
2018

Preface

Kari, J. & Okhotin, A., 1 Jun 2018, In : International Journal of Foundations of Computer Science. 29, 4, p. 457-459 3 p.

Research output

2019
State Complexity
Pushdown Automata
Formal languages
Quotient
Context free languages
2013
Context free languages
2015
2 Citations (Scopus)

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

Context free grammars
Parsing
Grammar
Context-free Grammar
Operator
2016
1 Citation (Scopus)

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

Finite Automata
Finite automata
Strings
Automata
Deterministic Finite Automata
2018
2 Citations (Scopus)

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

Context free grammars
Syntactics
Grammar
Context-free Grammar
Operator
2019
2 Citations (Scopus)

Edit distance neighbourhoods of input-driven pushdown automata

Okhotin, A. & Salomaa, K., 19 Jul 2019, In : Theoretical Computer Science. 777, p. 417-430 14 p.

Research output

Context free languages
Pushdown Automata
Edit Distance
Formal languages
Strings
2018
1 Citation (Scopus)

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

Pushdown Automata
Closure Properties
Square root
Deletion
Insertion
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

Context free grammars
Syntactics
Linear Space
Grammar
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, 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

Context free grammars
Grammar
Computational complexity
Context-free Grammar
Homomorphic
2017
2 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 outputpeer-review

Polynomials
2017
3 Citations (Scopus)
2 Citations (Scopus)
2014
4 Citations (Scopus)

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

Finite Automata
Finite automata
Automata
Necessary
Nondeterminism
2019
Pushdown Automata
Closure Properties
Square root
Deletion
Insertion
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 output

Finite Automata
Finite automata
Blow-up
Image Compression
Image compression
2019
State Complexity
Concatenation
Finite Automata
Finite automata
Stars
2018
Formal languages
Grammar
Regular Languages
Strictly
Equivalence
2012
19 Citations (Scopus)

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

Context free languages
Context-free Languages
Homomorphism
Theorem
Formal languages
20 Citations (Scopus)
Open Access
Unary
Finite Automata
Finite automata
G-function
Stars
2011
12 Citations (Scopus)

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

Context free languages
Context-free Languages
Cellular automata
Real-time
Grammar
2018

Preface

Shallit, J. & Okhotin, A., 1 Apr 2018, In : Information and Computation. 259, 1 p.

Research output

2015
4 Citations (Scopus)
Grammar
Normal Form
Specifications
Context free grammars
Operator
2014
Open Access
Context free grammars
Specifications
2012
4 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

Concatenation
Solution Existence
Recursively Enumerable Set
Expressive Power
Unique Solution
2013
37 Citations (Scopus)
Context free grammars
Context-free Grammar
Grammar
Parsing
Computational complexity