Alexander Okhotin

ORCID

Publication Activity (10 Years)

Years Active: 2001-2024
Publications (10 Years): 84

Top Venues

Publications

Ekaterina N. Shemetova, Alexander Okhotin, Semyon V. Grigorev
Rational Index of Languages Defined by Grammars with Bounded Dimension of Parse Trees. Theory Comput. Syst. 68 (3) (2024)
Alexander Okhotin, Maria Radionova, Elizaveta Sazhneva
GF(2)-operations on basic families of formal languages. Theor. Comput. Sci. 995 (2024)
Stepan L. Kuznetsov, Alexander Okhotin
Conjunctive categorial grammars and Lambek grammars with additives. CoRR (2024)
Ilya Olkhovsky, Alexander Okhotin
On the Transformation of LL(k)-linear to LL(1)-linear Grammars. Theory Comput. Syst. 67 (2) (2023)
Ilya Olkhovsky, Alexander Okhotin
Correction to: On the Transformation of LL(k)-linear to LL(1)-linear Grammars. Theory Comput. Syst. 67 (2) (2023)
Mikhail Mrykhin, Alexander Okhotin
On hardest languages for one-dimensional cellular automata. Inf. Comput. 295 (Part B) (2023)
Olga Martynova, Alexander Okhotin
Homomorphisms and inverse homomorphisms on graph-walking automata. Theor. Comput. Sci. 979 (2023)
Mikhail Mrykhin, Alexander Okhotin
The hardest language for grammars with context operators. Theor. Comput. Sci. 958 (2023)
Semyon Petrov, Fedor Petrov, Alexander Okhotin
On the rank of the communication matrix for deterministic two-way finite automata. CoRR (2023)
Maria Radionova, Alexander Okhotin
Sweeping Permutation Automata. NCMA (2023)
Alex Rose, Alexander Okhotin
Probabilistic Input-Driven Pushdown Automata. MFCS (2023)
Olga Martynova, Alexander Okhotin
Non-closure under complementation for unambiguous linear grammars. Inf. Comput. 292 (2023)
Olga Martynova, Alexander Okhotin
State complexity of transforming graph-walking automata to halting, returning and reversible. Inf. Comput. 291 (2023)
Margarita Mikhelson, Alexander Okhotin
Parallel Enumeration of Parse Trees. MFCS (2023)
Olga Martynova, Alexander Okhotin
Lower Bound. DCFS (2023)
Alexander Okhotin, Elizaveta Sazhneva
State Complexity of GF(2)-Inverse and GF(2)-Star on Binary Languages. J. Autom. Lang. Comb. 28 (1-3) (2023)
Mikhail Mrykhin, Alexander Okhotin
The Hardest LL(k) Language. Int. J. Found. Comput. Sci. 34 (2&3) (2023)
Semyon Petrov, Alexander Okhotin
On the transformation of two-way finite automata to unambiguous finite automata. Inf. Comput. 295 (Part B) (2023)
Olga Martynova, Alexander Okhotin
A Time to Cast Away Stones. CIAA (2023)
Ekaterina N. Shemetova, Alexander Okhotin, Semyon V. Grigorev
Rational Index of Languages with Bounded Dimension of Parse Trees. DLT (2022)
Mizuhito Ogawa, Alexander Okhotin
On the Determinization of Event-Clock Input-Driven Pushdown Automata. CSR (2022)
Olga Martynova, Alexander Okhotin
Homomorphisms on Graph-Walking Automata. CIAA (2022)
Olga Martynova, Alexander Okhotin
The maximum length of shortest accepted strings for direction-determinate two-way finite automata. CoRR (2022)
Ekaterina Bakinova, Artem Basharin, Igor Batmanov, Konstantin Lyubort, Alexander Okhotin, Elizaveta Sazhneva
Formal languages over GF(2). Inf. Comput. 283 (2022)
Alexander Okhotin, Elizaveta Sazhneva
State complexity of GF(2)-operations on unary languages. Inf. Comput. 284 (2022)
Olga Martynova, Alexander Okhotin
Non-closure under complementation for unambiguous linear grammars. CoRR (2022)
Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin
Computational and Proof Complexity of Partial String Avoidability. ACM Trans. Comput. Theory 13 (1) (2021)
Mikhail Mrykhin, Alexander Okhotin
The Hardest LL(k) Language. DLT (2021)
Alexander Okhotin, Victor L. Selivanov
Input-Driven Pushdown Automata on Well-Nested Infinite Strings. CSR (2021)
Olga Martynova, Alexander Okhotin
Homomorphisms on graph-walking automata. CoRR (2021)
Mizuhito Ogawa, Alexander Okhotin
On the determinization of event-clock input-driven pushdown automata. CoRR (2021)
Egor Dobronravov, Nikita Dobronravov, Alexander Okhotin
On the Length of Shortest Strings Accepted by Two-way Finite Automata. Fundam. Informaticae 180 (4) (2021)
Mikhail Mrykhin, Alexander Okhotin
On Hardest Languages for One-Dimensional Cellular Automata. LATA (2021)
Olga Martynova, Alexander Okhotin
State Complexity of Union and Intersection on Graph-Walking Automata. DCFS (2021)
Olga Martynova, Alexander Okhotin
Lower Bounds for Graph-Walking Automata. STACS (2021)
Viliam Geffert, Alexander Okhotin
Deterministic One-Way Simulation of Two-Way Deterministic Finite Automata over Small Alphabets. DCFS (2021)
Semyon Petrov, Alexander Okhotin
On the Transformation of Two-Way Deterministic Finite Automata to Unambiguous Finite Automata. LATA (2021)
Ilya Olkhovsky, Alexander Okhotin
On LL(k) linear conjunctive grammars. CoRR (2021)
Alexander Okhotin, Elizaveta Sazhneva
State Complexity of GF(2)-inverse and GF(2)-star on Binary Languages. DCFS (2020)
Alexander Okhotin, Victor L. Selivanov
Input-driven automata on well-nested infinite strings: automata-theoretic and topological properties. CoRR (2020)
Alexander Okhotin
Describing the syntax of programming languages using conjunctive and Boolean grammars. CoRR (2020)
Michal Kunc, Alexander Okhotin
Reversibility of computations in graph-walking automata. Inf. Comput. 275 (2020)
Olga Martynova, Alexander Okhotin
State complexity of halting, returning and reversible graph-walking automata. CoRR (2020)
Franz Baader, Pavlos Marantidis, Antoine Mottet, Alexander Okhotin
Extensions of unification modulo ACUI. Math. Struct. Comput. Sci. 30 (6) (2020)
Mikhail Mrykhin, Alexander Okhotin
The hardest language for grammars with context operators. CoRR (2020)
Alexander Okhotin, Alexey Sorokin
Cyclic Shift on Multi-component Grammars. LATA (2020)
Ekaterina N. Shemetova, Alexander Okhotin, Semyon V. Grigorev
Rational index of bounded-oscillation languages. CoRR (2020)
Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin
Computational and proof complexity of partial string avoidability. Electron. Colloquium Comput. Complex. 27 (2020)
Stanislav Krymski, Alexander Okhotin
Longer Shortest Strings in Two-Way Finite Automata. DCFS (2020)
Alexander Okhotin, Ilya Olkhovsky
On the Transformation of LL(k)-linear Grammars to LL(1)-linear. CSR (2020)
Egor Dobronravov, Nikita Dobronravov, Alexander Okhotin
On the Length of Shortest Strings Accepted by Two-Way Finite Automata. DLT (2019)
Alexander Okhotin
Graph-Walking Automata: From Whence They Come, and Whither They are Bound. CIAA (2019)
Alexander Okhotin
Hardest languages for conjunctive and Boolean grammars. Inf. Comput. 266 (2019)
Vladislav Makarov, Alexander Okhotin
On the Expressive Power of GF(2)-Grammars. SOFSEM (2019)
Alexander Okhotin, Kai Salomaa
Further closure properties of input-driven pushdown automata. Theor. Comput. Sci. 798 (2019)
Alexander Okhotin, Elizaveta Sazhneva
State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages. DCFS (2019)
Alexander Okhotin, Kai Salomaa
State Complexity of the Quotient Operation on Input-Driven Pushdown Automata. Int. J. Found. Comput. Sci. 30 (6-7) (2019)
Alexander Okhotin, Kai Salomaa
Edit distance neighbourhoods of input-driven pushdown automata. Theor. Comput. Sci. 777 (2019)
Galina Jirásková, Alexander Okhotin
State complexity of unambiguous operations on finite automata. Theor. Comput. Sci. 798 (2019)
Galina Jirásková, Alexander Okhotin
Towards Exact State Complexity Bounds for Input-Driven Pushdown Automata. DLT (2018)
Ekaterina Bakinova, Artem Basharin, Igor Batmanov, Konstantin Lyubort, Alexander Okhotin, Elizaveta Sazhneva
Formal Languages over GF(2). LATA (2018)
Jarkko Kari, Alexander Okhotin
Preface. Int. J. Found. Comput. Sci. 29 (4) (2018)
Alexander Okhotin
Underlying Principles and Recurring Ideas of Formal Grammars. LATA (2018)
Alexander Okhotin
A Tale of Conjunctive Grammars. DLT (2018)
Artur Jez, Alexander Okhotin
On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars. Fundam. Informaticae 162 (1) (2018)
Mikhail Barash, Alexander Okhotin
Linear-space recognition for grammars with contexts. Theor. Comput. Sci. 719 (2018)
Galina Jirásková, Alexander Okhotin
State Complexity of Unambiguous Operations on Deterministic Finite Automata. DCFS (2018)
Alexander Okhotin, Kai Salomaa
Further Closure Properties of Input-Driven Pushdown Automata. DCFS (2018)
Jeffrey O. Shallit, Alexander Okhotin
Preface. Inf. Comput. 259 (2) (2018)
Alexander Okhotin, Kai Salomaa
The Quotient Operation on Input-Driven Pushdown Automata. DCFS (2017)
Artur Jez, Alexander Okhotin
Unambiguous conjunctive grammars over a one-symbol alphabet. Theor. Comput. Sci. 665 (2017)
Alexander Okhotin, Kai Salomaa
State complexity of operations on input-driven pushdown automata. J. Comput. Syst. Sci. 86 (2017)
Galina Jirásková, Alexander Okhotin
On the state complexity of operations on two-way finite automata. Inf. Comput. 253 (2017)
Mikhail Barash, Alexander Okhotin
Generalized LR Parsing Algorithm for Grammars with One-Sided Contexts. Theory Comput. Syst. 61 (2) (2017)
Alexander Okhotin, Kai Salomaa
Edit Distance Neighbourhoods of Input-Driven Pushdown Automata. CSR (2017)
Stepan L. Kuznetsov, Alexander Okhotin
Conjunctive Categorial Grammars. MOL (2017)
Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin
Computational and Proof Complexity of Partial String Avoidability. MFCS (2016)
Alexander Okhotin
Input-driven languages are linear conjunctive. Theor. Comput. Sci. 618 (2016)
Helmut Jürgensen, Juhani Karhumäki, Alexander Okhotin
Descriptional Complexity of Formal Systems. Theor. Comput. Sci. 610 (2016)
Franz Baader, Pavlos Marantidis, Alexander Okhotin
Approximately Solving Set Equations. UNIF (2016)
Artur Jez, Alexander Okhotin
Equations over sets of integers with addition only. J. Comput. Syst. Sci. 82 (6) (2016)
Alexander Okhotin
The Hardest Language for Conjunctive Grammars. CSR (2016)
Franz Baader, Pavlos Marantidis, Alexander Okhotin
_0. JELIA (2016)
Artur Jez, Alexander Okhotin
Least and greatest solutions of equations over sets of integers. Theor. Comput. Sci. 619 (2016)
Alexander Okhotin
Improved normal form for grammars with one-sided contexts. Theor. Comput. Sci. 588 (2015)
Alexander Okhotin, Kai Salomaa
Descriptional complexity of unambiguous input-driven pushdown automata. Theor. Comput. Sci. 566 (2015)
Mikhail Barash, Alexander Okhotin
Generalized LR Parsing for Grammars with Contexts. CSR (2015)
Alexander Okhotin
On language equations with concatenation and various sets of Boolean operations. RAIRO Theor. Informatics Appl. 49 (3) (2015)
Mikhail Barash, Alexander Okhotin
Two-sided context specifications in formal grammars. Theor. Comput. Sci. 591 (2015)
Mikhail Barash, Alexander Okhotin
Linear grammars with one-sided contexts and their automaton representation. RAIRO Theor. Informatics Appl. 49 (2) (2015)
Viliam Geffert, Alexander Okhotin
Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata. MFCS (1) (2014)
Mikhail Barash, Alexander Okhotin
Linear Grammars with One-Sided Contexts and Their Automaton Representation. LATIN (2014)
Mikhail Barash, Alexander Okhotin
Grammars with two-sided contexts. AFL (2014)
Alexander Okhotin, Kai Salomaa
Input-Driven Pushdown Automata with Limited Nondeterminism - (Invited Paper). Developments in Language Theory (2014)
Alexander Okhotin, Kai Salomaa
Complexity of input-driven pushdown automata. SIGACT News 45 (2) (2014)
Juhani Karhumäki, Alexander Okhotin
On the Determinization Blowup for Finite Automata Recognizing Equal-Length Languages. Computing with New Resources (2014)
Mikhail Barash, Alexander Okhotin
An extension of context-free grammars with one-sided context specifications. Inf. Comput. 237 (2014)
Alexander Okhotin
Parsing by matrix multiplication generalized to Boolean grammars. Theor. Comput. Sci. 516 (2014)
Artur Jez, Alexander Okhotin
Computational completeness of equations over sets of natural numbers. Inf. Comput. 237 (2014)
Michal Kunc, Alexander Okhotin
Reversibility of Computations in Graph-Walking Automata. MFCS (2013)

Alexander Okhotin.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Alexander Okhotin