Alexander Okhotin

233 papers A* 2A 4B 17C 40Misc 9Journal 125Unranked 33
YearRankTypeTitle / Venue / Authors
2026 J jnl
A Time to Cast Away Stones: On a Family of Pebble Automata.
Int. J. Found. Comput. Sci.
Olga Martynova, Alexander Okhotin
2026 J jnl
Sweeping permutation automata.
Acta Informatica
Maria Radionova, Alexander Okhotin
2025 C conf
A Hierarchy of Reversible Finite Automata.
CIAA
Maria Radionova, Alexander Okhotin
2025 J jnl
A parallel algorithm for counting parse trees.
Inf. Comput.
Margarita Mikhelson, Alexander Okhotin
2025 J jnl
Decision problems for systems of language equations and inequations.
Inf. Comput.
Alexander Okhotin
2025 C conf
From Regular Expressions to Deterministic Finite Automata: $2^{\frac{n}{2}+\sqrt{n}(\log n)^{\varTheta (1)}}$ States Are Necessary and Sufficient.
CIAA
Olga Martynova, Alexander Okhotin
2025 J jnl
From regular expressions to deterministic finite automata: $2
CoRR
Olga Martynova, Alexander Okhotin
2025 A* conf
Nondeterministic Tree-Walking Automata Are Not Closed Under Complementation.
ICALP
Olga Martynova, Alexander Okhotin
2025 C conf
On the Transformation of Two-Way Nondeterministic Finite Automata to Unambiguous Finite Automata.
DLT
Semyon Petrov, Alexander Okhotin
2025 J jnl
On the expressive power of categorial grammars with unique category assignment.
J. Log. Lang. Inf.
Maxim Vishnikin, Alexander Okhotin
2025 J jnl
Probabilistic input-driven pushdown automata.
Inf. Comput.
Alex Rose, Alexander Okhotin
2025 C conf
Simulating Two-Way Nondeterministic Finite Automata Over Small Alphabets by One-Way Nondeterministic Automata.
CIAA
Viliam Geffert, Alexander Okhotin
2024 J jnl
A hierarchy of reversible finite automata.
CoRR
Maria Radionova, Alexander Okhotin
2024 J jnl
A lower bound on the state complexity of transforming two-way nondeterministic finite automata to unambiguous finite automata.
CoRR
Semyon Petrov, Alexander Okhotin
2024 J jnl
Conjunctive categorial grammars and Lambek grammars with additives.
CoRR
Stepan L. Kuznetsov, Alexander Okhotin
2024 C conf
Decision Problems for Reversible and Permutation Automata.
CIAA
Maria Radionova, Alexander Okhotin
2024 J jnl
GF(2)-operations on basic families of formal languages.
Theor. Comput. Sci.
Alexander Okhotin, Maria Radionova, Elizaveta Sazhneva
2024 J jnl
Nondeterministic tree-walking automata are not closed under complementation.
CoRR
Olga Martynova, Alexander Okhotin
2024 J jnl
Rational Index of Languages Defined by Grammars with Bounded Dimension of Parse Trees.
Theory Comput. Syst.
Ekaterina N. Shemetova, Alexander Okhotin, Semyon V. Grigorev
2023 C conf
A Time to Cast Away Stones.
CIAA
Olga Martynova, Alexander Okhotin
2023 J jnl
Correction to: On the Transformation of LL(k)-linear to LL(1)-linear Grammars.
Theory Comput. Syst.
Ilya Olkhovsky, Alexander Okhotin
2023 J jnl
Homomorphisms and inverse homomorphisms on graph-walking automata.
Theor. Comput. Sci.
Olga Martynova, Alexander Okhotin
2023 J jnl
Non-closure under complementation for unambiguous linear grammars.
Inf. Comput.
Olga Martynova, Alexander Okhotin
2023 J jnl
On hardest languages for one-dimensional cellular automata.
Inf. Comput.
Mikhail Mrykhin, Alexander Okhotin
2023 J jnl
On the Transformation of LL(k)-linear to LL(1)-linear Grammars.
Theory Comput. Syst.
Ilya Olkhovsky, Alexander Okhotin
2023 J jnl
On the rank of the communication matrix for deterministic two-way finite automata.
CoRR
Semyon Petrov, Fedor Petrov, Alexander Okhotin
2023 J jnl
On the transformation of two-way finite automata to unambiguous finite automata.
Inf. Comput.
Semyon Petrov, Alexander Okhotin
2023 B conf
Parallel Enumeration of Parse Trees.
MFCS
Margarita Mikhelson, Alexander Okhotin
2023 B conf
Probabilistic Input-Driven Pushdown Automata.
MFCS
Alex Rose, Alexander Okhotin
2023 — conf
Shortest Accepted Strings for Two-Way Finite Automata: Approaching the 2
DCFS
Olga Martynova, Alexander Okhotin
2023 J jnl
State Complexity of GF(2)-Inverse and GF(2)-Star on Binary Languages.
J. Autom. Lang. Comb.
Alexander Okhotin, Elizaveta Sazhneva
2023 J jnl
State complexity of transforming graph-walking automata to halting, returning and reversible.
Inf. Comput.
Olga Martynova, Alexander Okhotin
2023 — conf
Sweeping Permutation Automata.
NCMA
Maria Radionova, Alexander Okhotin
2023 J jnl
The Hardest LL(k) Language.
Int. J. Found. Comput. Sci.
Mikhail Mrykhin, Alexander Okhotin
2023 J jnl
The hardest language for grammars with context operators.
Theor. Comput. Sci.
Mikhail Mrykhin, Alexander Okhotin
2022 J jnl
Formal languages over GF(2).
Inf. Comput.
Ekaterina Bakinova, Artem Basharin, Igor Batmanov, Konstantin Lyubort, Alexander Okhotin, Elizaveta Sazhneva
2022 C conf
Homomorphisms on Graph-Walking Automata.
CIAA
Olga Martynova, Alexander Okhotin
2022 J jnl
Non-closure under complementation for unambiguous linear grammars.
CoRR
Olga Martynova, Alexander Okhotin
2022 Misc conf
On the Determinization of Event-Clock Input-Driven Pushdown Automata.
CSR
Mizuhito Ogawa, Alexander Okhotin
2022 C conf
Rational Index of Languages with Bounded Dimension of Parse Trees.
DLT
Ekaterina N. Shemetova, Alexander Okhotin, Semyon V. Grigorev
2022 J jnl
State complexity of GF(2)-operations on unary languages.
Inf. Comput.
Alexander Okhotin, Elizaveta Sazhneva
2022 J jnl
The maximum length of shortest accepted strings for direction-determinate two-way finite automata.
CoRR
Olga Martynova, Alexander Okhotin
2021 J jnl
Computational and Proof Complexity of Partial String Avoidability.
ACM Trans. Comput. Theory
Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin
2021 — conf
Deterministic One-Way Simulation of Two-Way Deterministic Finite Automata over Small Alphabets.
DCFS
Viliam Geffert, Alexander Okhotin
2021 J jnl
Homomorphisms on graph-walking automata.
CoRR
Olga Martynova, Alexander Okhotin
2021 Misc conf
Input-Driven Pushdown Automata on Well-Nested Infinite Strings.
CSR
Alexander Okhotin, Victor L. Selivanov
2021 — ch.
Language equations.
Handbook of Automata Theory (I.)
Michal Kunc, Alexander Okhotin
2021 A conf
Lower Bounds for Graph-Walking Automata.
STACS
Olga Martynova, Alexander Okhotin
2021 C conf
On Hardest Languages for One-Dimensional Cellular Automata.
LATA
Mikhail Mrykhin, Alexander Okhotin
2021 J jnl
On LL(k) linear conjunctive grammars.
CoRR
Ilya Olkhovsky, Alexander Okhotin
2021 J jnl
On the Length of Shortest Strings Accepted by Two-way Finite Automata.
Fundam. Informaticae
Egor Dobronravov, Nikita Dobronravov, Alexander Okhotin
2021 C conf
On the Transformation of Two-Way Deterministic Finite Automata to Unambiguous Finite Automata.
LATA
Semyon Petrov, Alexander Okhotin
2021 J jnl
On the determinization of event-clock input-driven pushdown automata.
CoRR
Mizuhito Ogawa, Alexander Okhotin
2021 — conf
State Complexity of Union and Intersection on Graph-Walking Automata.
DCFS
Olga Martynova, Alexander Okhotin
2021 C conf
The Hardest LL(k) Language.
DLT
Mikhail Mrykhin, Alexander Okhotin
2020 J jnl
Computational and proof complexity of partial string avoidability.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin
2020 C conf
Cyclic Shift on Multi-component Grammars.
LATA
Alexander Okhotin, Alexey Sorokin
2020 J jnl
Describing the syntax of programming languages using conjunctive and Boolean grammars.
CoRR
Alexander Okhotin
2020 J jnl
Extensions of unification modulo ACUI.
Math. Struct. Comput. Sci.
Franz Baader, Pavlos Marantidis, Antoine Mottet, Alexander Okhotin
2020 J jnl
Input-driven automata on well-nested infinite strings: automata-theoretic and topological properties.
CoRR
Alexander Okhotin, Victor L. Selivanov
2020 — conf
Longer Shortest Strings in Two-Way Finite Automata.
DCFS
Stanislav Krymski, Alexander Okhotin
2020 Misc conf
On the Transformation of LL(k)-linear Grammars to LL(1)-linear.
CSR
Alexander Okhotin, Ilya Olkhovsky
2020 J jnl
Rational index of bounded-oscillation languages.
CoRR
Ekaterina N. Shemetova, Alexander Okhotin, Semyon V. Grigorev
2020 J jnl
Reversibility of computations in graph-walking automata.
Inf. Comput.
Michal Kunc, Alexander Okhotin
2020 — conf
State Complexity of GF(2)-inverse and GF(2)-star on Binary Languages.
DCFS
Alexander Okhotin, Elizaveta Sazhneva
2020 J jnl
State complexity of halting, returning and reversible graph-walking automata.
CoRR
Olga Martynova, Alexander Okhotin
2020 J jnl
The hardest language for grammars with context operators.
CoRR
Mikhail Mrykhin, Alexander Okhotin
2019 J jnl
Edit distance neighbourhoods of input-driven pushdown automata.
Theor. Comput. Sci.
Alexander Okhotin, Kai Salomaa
2019 J jnl
Further closure properties of input-driven pushdown automata.
Theor. Comput. Sci.
Alexander Okhotin, Kai Salomaa
2019 C conf
Graph-Walking Automata: From Whence They Come, and Whither They are Bound.
CIAA
Alexander Okhotin
2019 J jnl
Hardest languages for conjunctive and Boolean grammars.
Inf. Comput.
Alexander Okhotin
2019 C ed.
Language and Automata Theory and Applications - 13th International Conference, LATA 2019, St. Petersburg, Russia, March 26-29, 2019, Proceedings
LATA
Carlos Martín-Vide, Alexander Okhotin, Dana Shapira
2019 B conf
On the Expressive Power of GF(2)-Grammars.
SOFSEM
Vladislav Makarov, Alexander Okhotin
2019 C conf
On the Length of Shortest Strings Accepted by Two-Way Finite Automata.
DLT
Egor Dobronravov, Nikita Dobronravov, Alexander Okhotin
2019 — conf
State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages.
DCFS
Alexander Okhotin, Elizaveta Sazhneva
2019 J jnl
State Complexity of the Quotient Operation on Input-Driven Pushdown Automata.
Int. J. Found. Comput. Sci.
Alexander Okhotin, Kai Salomaa
2019 J jnl
State complexity of unambiguous operations on finite automata.
Theor. Comput. Sci.
Galina Jirásková, Alexander Okhotin
2018 C conf
A Tale of Conjunctive Grammars.
DLT
Alexander Okhotin
2018 C conf
Formal Languages over GF(2).
LATA
Ekaterina Bakinova, Artem Basharin, Igor Batmanov, Konstantin Lyubort, Alexander Okhotin, Elizaveta Sazhneva
2018 — conf
Further Closure Properties of Input-Driven Pushdown Automata.
DCFS
Alexander Okhotin, Kai Salomaa
2018 J jnl
Linear-space recognition for grammars with contexts.
Theor. Comput. Sci.
Mikhail Barash, Alexander Okhotin
2018 J jnl
On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars.
Fundam. Informaticae
Artur Jez, Alexander Okhotin
2018 J jnl
Preface.
Inf. Comput.
Jeffrey O. Shallit, Alexander Okhotin
2018 J jnl
Preface.
Int. J. Found. Comput. Sci.
Jarkko Kari, Alexander Okhotin
2018 — conf
State Complexity of Unambiguous Operations on Deterministic Finite Automata.
DCFS
Galina Jirásková, Alexander Okhotin
2018 C conf
Towards Exact State Complexity Bounds for Input-Driven Pushdown Automata.
DLT
Galina Jirásková, Alexander Okhotin
2018 C conf
Underlying Principles and Recurring Ideas of Formal Grammars.
LATA
Alexander Okhotin
2017 — conf
Conjunctive Categorial Grammars.
MOL
Stepan L. Kuznetsov, Alexander Okhotin
2017 Misc conf
Edit Distance Neighbourhoods of Input-Driven Pushdown Automata.
CSR
Alexander Okhotin, Kai Salomaa
2017 J jnl
Generalized LR Parsing Algorithm for Grammars with One-Sided Contexts.
Theory Comput. Syst.
Mikhail Barash, Alexander Okhotin
2017 J jnl
On the state complexity of operations on two-way finite automata.
Inf. Comput.
Galina Jirásková, Alexander Okhotin
2017 J jnl
State complexity of operations on input-driven pushdown automata.
J. Comput. Syst. Sci.
Alexander Okhotin, Kai Salomaa
2017 — conf
The Quotient Operation on Input-Driven Pushdown Automata.
DCFS
Alexander Okhotin, Kai Salomaa
2017 J jnl
Unambiguous conjunctive grammars over a one-symbol alphabet.
Theor. Comput. Sci.
Artur Jez, Alexander Okhotin
2016 B conf
Approximate Unification in the Description Logic
JELIA
Franz Baader, Pavlos Marantidis, Alexander Okhotin
2016 — conf
Approximately Solving Set Equations.
UNIF
Franz Baader, Pavlos Marantidis, Alexander Okhotin
2016 B conf
Computational and Proof Complexity of Partial String Avoidability.
MFCS
Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin
2016 J jnl
Descriptional Complexity of Formal Systems.
Theor. Comput. Sci.
Helmut Jürgensen, Juhani Karhumäki, Alexander Okhotin
2016 J jnl
Equations over sets of integers with addition only.
J. Comput. Syst. Sci.
Artur Jez, Alexander Okhotin
2016 J jnl
Input-driven languages are linear conjunctive.
Theor. Comput. Sci.
Alexander Okhotin
2016 J jnl
Least and greatest solutions of equations over sets of integers.
Theor. Comput. Sci.
Artur Jez, Alexander Okhotin
2016 Misc conf
The Hardest Language for Conjunctive Grammars.
CSR
Alexander Okhotin
2015 — ed.
Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings
DCFS
Jeffrey O. Shallit, Alexander Okhotin
2015 J jnl
Descriptional complexity of unambiguous input-driven pushdown automata.
Theor. Comput. Sci.
Alexander Okhotin, Kai Salomaa
2015 Misc conf
Generalized LR Parsing for Grammars with Contexts.
CSR
Mikhail Barash, Alexander Okhotin
2015 J jnl
Improved normal form for grammars with one-sided contexts.
Theor. Comput. Sci.
Alexander Okhotin
2015 J jnl
Linear grammars with one-sided contexts and their automaton representation.
RAIRO Theor. Informatics Appl.
Mikhail Barash, Alexander Okhotin
2015 J jnl
On language equations with concatenation and various sets of Boolean operations.
RAIRO Theor. Informatics Appl.
Alexander Okhotin
2015 J jnl
Two-sided context specifications in formal grammars.
Theor. Comput. Sci.
Mikhail Barash, Alexander Okhotin
2014 J jnl
An extension of context-free grammars with one-sided context specifications.
Inf. Comput.
Mikhail Barash, Alexander Okhotin
2014 J jnl
Complexity of input-driven pushdown automata.
SIGACT News
Alexander Okhotin, Kai Salomaa
2014 J jnl
Computational completeness of equations over sets of natural numbers.
Inf. Comput.
Artur Jez, Alexander Okhotin
2014 — ed.
Descriptional Complexity of Formal Systems - 16th International Workshop, DCFS 2014, Turku, Finland, August 5-8, 2014. Proceedings
DCFS
Helmut Jürgensen, Juhani Karhumäki, Alexander Okhotin
2014 — conf
Grammars with two-sided contexts.
AFL
Mikhail Barash, Alexander Okhotin
2014 C conf
Input-Driven Pushdown Automata with Limited Nondeterminism - (Invited Paper).
Developments in Language Theory
Alexander Okhotin, Kai Salomaa
2014 B conf
Linear Grammars with One-Sided Contexts and Their Automaton Representation.
LATIN
Mikhail Barash, Alexander Okhotin
2014 — conf
On the Determinization Blowup for Finite Automata Recognizing Equal-Length Languages.
Computing with New Resources
Juhani Karhumäki, Alexander Okhotin
2014 J jnl
Parsing by matrix multiplication generalized to Boolean grammars.
Theor. Comput. Sci.
Alexander Okhotin
2014 — conf
Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata.
MFCS (1)
Viliam Geffert, Alexander Okhotin
2013 J jnl
Conjunctive and Boolean grammars: The true general case of the context-free grammars.
Comput. Sci. Rev.
Alexander Okhotin
2013 J jnl
Homomorphisms Preserving Deterministic Context-Free Languages.
Int. J. Found. Comput. Sci.
Tommi Lehtinen, Alexander Okhotin
2013 — conf
Improved Normal Form for Grammars with One-Sided Contexts.
DCFS
Alexander Okhotin
2013 — conf
Input-driven pushdown automata: nondeterminism and unambiguity.
NCMA
Alexander Okhotin, Kai Salomaa
2013 J jnl
On Language Equations with One-sided Concatenation.
Fundam. Informaticae
Franz Baader, Alexander Okhotin
2013 — conf
One-way simulation of two-way finite automata over small alphabets.
NCMA
Viliam Geffert, Alexander Okhotin
2013 B conf
Reversibility of Computations in Graph-Walking Automata.
MFCS
Michal Kunc, Alexander Okhotin
2013 C conf
Unambiguous Conjunctive Grammars over a One-Letter Alphabet.
Developments in Language Theory
Artur Jez, Alexander Okhotin
2012 C conf
Defining Contexts in Context-Free Grammars.
LATA
Mikhail Barash, Alexander Okhotin
2012 — conf
Descriptional Complexity of Input-Driven Pushdown Automata.
Languages Alive
Alexander Okhotin, Xiaoxue Piao, Kai Salomaa
2012 C conf
Homomorphisms Preserving Deterministic Context-Free Languages.
Developments in Language Theory
Tommi Lehtinen, Alexander Okhotin
2012 J jnl
Language Equations with Symmetric Difference.
Fundam. Informaticae
Alexander Okhotin
2012 J jnl
Language equations with complementation: Expressive power.
Theor. Comput. Sci.
Alexander Okhotin, Oksana Yakimova
2012 C conf
Non-erasing Variants of the Chomsky-Schützenberger Theorem.
Developments in Language Theory
Alexander Okhotin
2012 — conf
On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars.
DCFS
Artur Jez, Alexander Okhotin
2012 J jnl
On the expressive power of univariate equations over sets of natural numbers.
Inf. Comput.
Alexander Okhotin, Panos Rondogiannis
2012 J jnl
Parsing Boolean grammars over a one-letter alphabet using online convolution.
Theor. Comput. Sci.
Alexander Okhotin, Christian Reitwießner
2012 J jnl
Representing Hyper-arithmetical Sets by Equations over Sets of Integers.
Theory Comput. Syst.
Artur Jez, Alexander Okhotin
2012 B conf
Solving Language Equations and Disequations with Applications to Disunification in Description Logics and Monadic Set Constraints.
LPAR
Franz Baader, Alexander Okhotin
2012 J jnl
State complexity of operations on two-way finite automata over a unary alphabet.
Theor. Comput. Sci.
Michal Kunc, Alexander Okhotin
2012 J jnl
Unambiguous finite automata over a unary alphabet.
Inf. Comput.
Alexander Okhotin
2011 J jnl
A simple P-complete problem and its language-theoretic representations.
Theor. Comput. Sci.
Alexander Okhotin
2011 B conf
Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages.
SOFSEM
Alexander Okhotin
2011 J jnl
Complexity of Equations over Sets of Natural Numbers.
Theory Comput. Syst.
Artur Jez, Alexander Okhotin
2011 C conf
Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups.
Developments in Language Theory
Michal Kunc, Alexander Okhotin
2011 C conf
Descriptional Complexity of Unambiguous Nested Word Automata.
LATA
Alexander Okhotin, Kai Salomaa
2011 J jnl
Expressive power of LL(k) Boolean grammars.
Theor. Comput. Sci.
Alexander Okhotin
2011 J jnl
On Equations over Sets of Numbers and their Limitations.
Int. J. Found. Comput. Sci.
Tommi Lehtinen, Alexander Okhotin
2011 J jnl
On the State Complexity of Star of Union and Star of Intersection.
Fundam. Informaticae
Galina Jirásková, Alexander Okhotin
2011 J jnl
One-Nonterminal Conjunctive Grammars over a Unary Alphabet.
Theory Comput. Syst.
Artur Jez, Alexander Okhotin
2011 B conf
State Complexity of Operations on Input-Driven Pushdown Automata.
MFCS
Alexander Okhotin, Kai Salomaa
2011 — conf
State Complexity of Operations on Two-Way Deterministic Finite Automata over a Unary Alphabet.
DCFS
Michal Kunc, Alexander Okhotin
2011 J jnl
State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata.
Fundam. Informaticae
Michal Kunc, Alexander Okhotin
2010 J jnl
Boolean Grammars and GSM Mappings.
Int. J. Found. Comput. Sci.
Tommi Lehtinen, Alexander Okhotin
2010 J jnl
Computational power of two stacks with restricted communication.
Inf. Comput.
Juhani Karhumäki, Michal Kunc, Alexander Okhotin
2010 J jnl
Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth.
Theory Comput. Syst.
Artur Jez, Alexander Okhotin
2010 J jnl
Conjunctive grammars with restricted disjunction.
Theor. Comput. Sci.
Alexander Okhotin, Christian Reitwießner
2010 J jnl
Decision problems for language equations.
J. Comput. Syst. Sci.
Alexander Okhotin
2010 C conf
Fast Parsing for Boolean Grammars: A Generalization of Valiant's Algorithm.
Developments in Language Theory
Alexander Okhotin
2010 B conf
Least and Greatest Solutions of Equations over Sets of Integers.
MFCS
Artur Jez, Alexander Okhotin
2010 J jnl
Nondeterministic State Complexity of Positional Addition.
J. Autom. Lang. Comb.
Galina Jirásková, Alexander Okhotin
2010 A conf
On Equations over Sets of Integers.
STACS
Artur Jez, Alexander Okhotin
2010 C conf
On Language Equations
Developments in Language Theory
Tommi Lehtinen, Alexander Okhotin
2010 J jnl
On equations over sets of integers
CoRR
Artur Jez, Alexander Okhotin
2010 J jnl
On stateless multihead automata: Hierarchies and the emptiness problem.
Theor. Comput. Sci.
Oscar H. Ibarra, Juhani Karhumäki, Alexander Okhotin
2010 J jnl
On the State Complexity of Scattered Substrings and Superstrings.
Fundam. Informaticae
Alexander Okhotin
2010 — conf
Parsing Unary Boolean Grammars Using Online Convolution.
Advances and Applications of Automata on Words and Trees
Alexander Okhotin, Christian Reitwießner
2010 B conf
Unambiguous Finite Automata over a Unary Alphabet.
MFCS
Alexander Okhotin
2010 J jnl
Univariate Equations Over Sets of Natural Numbers.
Fundam. Informaticae
Artur Jez, Alexander Okhotin
2009 B conf
Conjunctive Grammars with Restricted Disjunction.
SOFSEM
Alexander Okhotin, Christian Reitwießner
2009 A conf
Equations over Sets of Natural Numbers with Addition Only.
STACS
Artur Jez, Alexander Okhotin
2009 — conf
Nondeterministic State Complexity of Positional Addition
DCFS
Galina Jirásková, Alexander Okhotin
2009 C conf
On Equations over Sets of Numbers and Their Limitations.
Developments in Language Theory
Tommi Lehtinen, Alexander Okhotin
2009 Misc conf
One-Nonterminal Conjunctive Grammars over a Unary Alphabet.
CSR
Artur Jez, Alexander Okhotin
2009 J jnl
State complexity of power.
Theor. Comput. Sci.
Michael Domaratzki, Alexander Okhotin
2008 — conf
Boolean grammars and gsm mappings.
AFL
Tommi Lehtinen, Alexander Okhotin
2008 A conf
Complexity of solutions of equations over sets of natural numbers.
STACS
Alexander Okhotin, Artur Jez
2008 J jnl
Homomorphisms Preserving Linear Conjunctive Languages.
J. Autom. Lang. Comb.
Alexander Okhotin
2008 B conf
On Stateless Multihead Automata: Hierarchies and the Emptiness Problem.
LATIN
Oscar H. Ibarra, Juhani Karhumäki, Alexander Okhotin
2008 — conf
On the Computational Completeness of Equations over Sets of Natural Numbers.
ICALP (2)
Artur Jez, Alexander Okhotin
2008 C conf
On the State Complexity of Operations on Two-Way Finite Automata.
Developments in Language Theory
Galina Jirásková, Alexander Okhotin
2008 — conf
On the expressive power of univariate equations over sets of natural numbers.
IFIP TCS
Alexander Okhotin, Panos Rondogiannis
2008 — conf
Representing a P-complete problem by small trellis automata
CSP
Alexander Okhotin
2008 J jnl
State complexity of cyclic shift.
RAIRO Theor. Informatics Appl.
Galina Jirásková, Alexander Okhotin
2008 J jnl
Unambiguous Boolean grammars.
Inf. Comput.
Alexander Okhotin
2007 C conf
A Simple P-Complete Problem and Its Representations by Language Equations.
MCU
Alexander Okhotin
2007 Misc conf
Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth.
CSR
Artur Jez, Alexander Okhotin
2007 J jnl
Enumeration of Context-Free Languages and Related Structures.
J. Autom. Lang. Comb.
Michael Domaratzki, Alexander Okhotin, Jeffrey O. Shallit
2007 B conf
Expressive Power of LL(k) Boolean Grammars.
FCT
Alexander Okhotin
2007 J jnl
Language equations with complementation: Decision problems.
Theor. Comput. Sci.
Alexander Okhotin, Oksana Yakimova
2007 J jnl
Nine Open Problems on Conjunctive and Boolean Grammars.
Bull. EATCS
Alexander Okhotin
2007 J jnl
Notes on Dual Concatenation.
Int. J. Found. Comput. Sci.
Alexander Okhotin
2007 J jnl
Recursive descent parsing for Boolean grammars.
Acta Informatica
Alexander Okhotin
2007 C conf
Unambiguous Boolean grammars.
LATA
Alexander Okhotin
2006 — conf
Communication of Two Stacks and Rewriting.
ICALP (2)
Juhani Karhumäki, Michal Kunc, Alexander Okhotin
2006 J jnl
Computational Universality in One-variable Language Equations.
Fundam. Informaticae
Alexander Okhotin
2006 J jnl
Computing by commuting.
Theor. Comput. Sci.
Juhani Karhumäki, Michal Kunc, Alexander Okhotin
2006 J jnl
Generalized Lr Parsing Algorithm for Boolean Grammars.
Int. J. Found. Comput. Sci.
Alexander Okhotin
2006 C conf
Language Equations with Complementation.
Developments in Language Theory
Alexander Okhotin, Oksana Yakimova
2006 Misc conf
Language Equations with Symmetric Difference.
CSR
Alexander Okhotin
2005 J jnl
A characterization of the arithmetical hierarchy by language equations.
Int. J. Found. Comput. Sci.
Alexander Okhotin
2005 J jnl
Contextual Grammars with Uniform Sets of Trajectories.
Fundam. Informaticae
Alexander Okhotin, Kai Salomaa
2005 — conf
Enumeration of Context-Free Languages and Related Structures.
DCFS
Michael Domaratzki, Alexander Okhotin, Jeffrey O. Shallit
2005 C conf
LR Parsing for Boolean Grammars.
Developments in Language Theory
Alexander Okhotin
2005 — conf
State complexity of cyclic shift.
DCFS
Galina Jirásková, Alexander Okhotin
2005 B conf
Strict Language Inequalities and Their Decision Problems.
MFCS
Alexander Okhotin
2005 J jnl
The dual of concatenation.
Theor. Comput. Sci.
Alexander Okhotin
2005 J jnl
Unresolved systems of language equations: Expressive power and decision problems.
Theor. Comput. Sci.
Alexander Okhotin
2004 — conf
A characterization of the arithmetical hierarchy by language equations.
DCFS
Alexander Okhotin
2004 J jnl
Boolean grammars.
Inf. Comput.
Alexander Okhotin
2004 C ed.
Implementation and Application of Automata, 9th International Conference, CIAA 2004, Kingston, Canada, July 22-24, 2004, Revised Selected Papers
CIAA
Michael Domaratzki, Alexander Okhotin, Kai Salomaa, Sheng Yu
2004 C conf
On Computational Universality in Language Equations.
MCU
Alexander Okhotin
2004 J jnl
On the equivalence of linear conjunctive grammars and trellis automata.
RAIRO Theor. Informatics Appl.
Alexander Okhotin
2004 J jnl
On the number of nonterminals in linear conjunctive grammars.
Theor. Comput. Sci.
Alexander Okhotin
2004 J jnl
Representing recursively enumerable languages by iterated deletion.
Theor. Comput. Sci.
Michael Domaratzki, Alexander Okhotin
2004 J jnl
State Complexity of Linear Conjunctive Languages.
J. Autom. Lang. Comb.
Alexander Okhotin
2004 B conf
The Dual of Concatenation.
MFCS
Alexander Okhotin
2003 J jnl
A recognition and parsing algorithm for arbitrary conjunctive grammars.
Theor. Comput. Sci.
Alexander Okhotin
2003 J jnl
An overview of conjunctive grammars, Formal Language Theory Column.
Bull. EATCS
Alexander Okhotin
2003 C conf
Boolean Grammars.
Developments in Language Theory
Alexander Okhotin
2003 A* conf
Decision Problems for Language Equations with Boolean Operations.
ICALP
Alexander Okhotin
2003 J jnl
Efficient Automaton-Based Recognition For Linear Conjunctive Languages.
Int. J. Found. Comput. Sci.
Alexander Okhotin
2003 — conf
On the Number of Nonterminals in Linear Conjunctive Grammars.
DCFS
Alexander Okhotin
2003 J jnl
On the closure properties of linear conjunctive languages.
Theor. Comput. Sci.
Alexander Okhotin
2003 J jnl
The hardest linear conjunctive language.
Inf. Process. Lett.
Alexander Okhotin
2002 C conf
Automaton Representation of Linear Conjunctive Languages.
Developments in Language Theory
Alexander Okhotin
2002 J jnl
Conjunctive Grammars and Systems of Language Equations.
Program. Comput. Softw.
Alexander Okhotin
2002 C conf
Efficient Automaton-Based Recognition for Linear Conjunctive Languages.
CIAA
Alexander Okhotin
2002 J jnl
LR Parsing for Conjunctive Grammars.
Grammars
Alexander Okhotin
2002 J jnl
One-Visit Caterpillar Tree Automata.
Fundam. Informaticae
Alexander Okhotin, Kai Salomaa, Michael Domaratzki
2002 — conf
State complexity of linear conjunctive languages.
DCFS
Alexander Okhotin
2002 J jnl
Top-Down Parsing of Conjunctive Languages.
Grammars
Alexander Okhotin
2002 C conf
Whale Calf, a Parser Generator for Conjunctive Grammars.
CIAA
Alexander Okhotin
2001 J jnl
Conjunctive Grammars.
J. Autom. Lang. Comb.
Alexander Okhotin