Alexander Okhotin

Alexander Okhotin: Language Equations with Symmetric Difference. Fundam. Inform. 116(1-4): 205-222 (2012)

Alexander Okhotin, Panos Rondogiannis: On the expressive power of univariate equations over sets of natural numbers. Inf. Comput. 212: 1-14 (2012)

Alexander Okhotin: Unambiguous finite automata over a unary alphabet. Inf. Comput. 212: 15-36 (2012)

Artur Jez, Alexander Okhotin: Representing Hyper-arithmetical Sets by Equations over Sets of Integers. Theory Comput. Syst. 51(2): 196-228 (2012)

Alexander Okhotin, Oksana Yakimova: Language equations with complementation: Expressive power. Theor. Comput. Sci. 416: 71-86 (2012)

Michal Kunc, Alexander Okhotin: State complexity of operations on two-way finite automata over a unary alphabet. Theor. Comput. Sci. 449: 106-118 (2012)

Alexander Okhotin, Christian Reitwießner: Parsing Boolean grammars over a one-letter alphabet using online convolution. Theor. Comput. Sci. 457: 149-157 (2012)

Alexander Okhotin, Xiaoxue Piao, Kai Salomaa: Descriptional Complexity of Input-Driven Pushdown Automata. Languages Alive 2012: 186-206

Artur Jez, Alexander Okhotin: On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars. DCFS 2012: 183-195

Alexander Okhotin: Non-erasing Variants of the Chomsky-Schützenberger Theorem. Developments in Language Theory 2012: 121-129

Tommi Lehtinen, Alexander Okhotin: Homomorphisms Preserving Deterministic Context-Free Languages. Developments in Language Theory 2012: 154-165

Mikhail Barash, Alexander Okhotin: Defining Contexts in Context-Free Grammars. LATA 2012: 106-118

Franz Baader, Alexander Okhotin: Solving Language Equations and Disequations with Applications to Disunification in Description Logics and Monadic Set Constraints. LPAR 2012: 107-121

Galina Jirásková, Alexander Okhotin: On the State Complexity of Star of Union and Star of Intersection. Fundam. Inform. 109(2): 161-178 (2011)

Michal Kunc, Alexander Okhotin: State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata. Fundam. Inform. 110(1-4): 231-239 (2011)

Tommi Lehtinen, Alexander Okhotin: On Equations over Sets of Numbers and their Limitations. Int. J. Found. Comput. Sci. 22(2): 377-393 (2011)

Artur Jez, Alexander Okhotin: Complexity of Equations over Sets of Natural Numbers. Theory Comput. Syst. 48(2): 319-342 (2011)

Artur Jez, Alexander Okhotin: One-Nonterminal Conjunctive Grammars over a Unary Alphabet. Theory Comput. Syst. 49(2): 319-342 (2011)

Alexander Okhotin: A simple P-complete problem and its language-theoretic representations. Theor. Comput. Sci. 412(1-2): 68-82 (2011)

Alexander Okhotin: Expressive power of LL(k) Boolean grammars. Theor. Comput. Sci. 412(39): 5132-5155 (2011)

Michal Kunc, Alexander Okhotin: State Complexity of Operations on Two-Way Deterministic Finite Automata over a Unary Alphabet. DCFS 2011: 222-234

Michal Kunc, Alexander Okhotin: Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups. Developments in Language Theory 2011: 324-336

Alexander Okhotin, Kai Salomaa: Descriptional Complexity of Unambiguous Nested Word Automata. LATA 2011: 414-426

Alexander Okhotin, Kai Salomaa: State Complexity of Operations on Input-Driven Pushdown Automata. MFCS 2011: 485-496

Alexander Okhotin: Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages. SOFSEM 2011: 431-443

Alexander Okhotin: On the State Complexity of Scattered Substrings and Superstrings. Fundam. Inform. 99(3): 325-338 (2010)

Artur Jez, Alexander Okhotin: Univariate Equations Over Sets of Natural Numbers. Fundam. Inform. 104(4): 329-348 (2010)

Juhani Karhumäki, Michal Kunc, Alexander Okhotin: Computational power of two stacks with restricted communication. Inf. Comput. 208(9): 1060-1089 (2010)

Tommi Lehtinen, Alexander Okhotin: Boolean Grammars and GSM Mappings. Int. J. Found. Comput. Sci. 21(5): 799-815 (2010)

Galina Jirásková, Alexander Okhotin: Nondeterministic State Complexity of Positional Addition. Journal of Automata, Languages and Combinatorics 15(1/2): 121-133 (2010)

Alexander Okhotin: Decision problems for language equations. J. Comput. Syst. Sci. 76(3-4): 251-266 (2010)

Artur Jez, Alexander Okhotin: Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth. Theory Comput. Syst. 46(1): 27-58 (2010)

Oscar H. Ibarra, Juhani Karhumäki, Alexander Okhotin: On stateless multihead automata: Hierarchies and the emptiness problem. Theor. Comput. Sci. 411(3): 581-593 (2010)

Alexander Okhotin, Christian Reitwießner: Conjunctive grammars with restricted disjunction. Theor. Comput. Sci. 411(26-28): 2559-2571 (2010)

Tommi Lehtinen, Alexander Okhotin: On Language Equations XXK = XXL and XM = N over a Unary Alphabet. Developments in Language Theory 2010: 291-302

Alexander Okhotin: Fast Parsing for Boolean Grammars: A Generalization of Valiant's Algorithm. Developments in Language Theory 2010: 340-351

Artur Jez, Alexander Okhotin: Least and Greatest Solutions of Equations over Sets of Integers. MFCS 2010: 441-452

Alexander Okhotin: Unambiguous Finite Automata over a Unary Alphabet. MFCS 2010: 556-567

Artur Jez, Alexander Okhotin: On Equations over Sets of Integers. STACS 2010: 477-488

Artur Jez, Alexander Okhotin: On equations over sets of integers. CoRR abs/1001.2932 (2010)

Michael Domaratzki, Alexander Okhotin: State complexity of power. Theor. Comput. Sci. 410(24-25): 2377-2392 (2009)

Artur Jez, Alexander Okhotin: One-Nonterminal Conjunctive Grammars over a Unary Alphabet. CSR 2009: 191-202

Tommi Lehtinen, Alexander Okhotin: On Equations over Sets of Numbers and Their Limitations. Developments in Language Theory 2009: 360-371

Alexander Okhotin, Christian Reitwießner: Conjunctive Grammars with Restricted Disjunction. SOFSEM 2009: 425-436

Artur Jez, Alexander Okhotin: Equations over Sets of Natural Numbers with Addition Only. STACS 2009: 577-588

Galina Jirásková, Alexander Okhotin: Nondeterministic State Complexity of Positional Addition. DCFS 2009: 151-161

Alexander Okhotin: Unambiguous Boolean grammars. Inf. Comput. 206(9-10): 1234-1247 (2008)

Galina Jirásková, Alexander Okhotin: State complexity of cyclic shift. ITA 42(2): 335-360 (2008)

Alexander Okhotin: Homomorphisms Preserving Linear Conjunctive Languages. Journal of Automata, Languages and Combinatorics 13(3/4): 299-305 (2008)

Tommi Lehtinen, Alexander Okhotin: Boolean grammars and gsm mappings. AFL 2008: 269-280

Galina Jirásková, Alexander Okhotin: On the State Complexity of Operations on Two-Way Finite Automata. Developments in Language Theory 2008: 443-454

Artur Jez, Alexander Okhotin: On the Computational Completeness of Equations over Sets of Natural Numbers. ICALP (2) 2008: 63-74

Alexander Okhotin, Panos Rondogiannis: On the expressive power of univariate equations over sets of natural numbers. IFIP TCS 2008: 215-227

Oscar H. Ibarra, Juhani Karhumäki, Alexander Okhotin: On Stateless Multihead Automata: Hierarchies and the Emptiness Problem. LATIN 2008: 94-105

Alexander Okhotin, Artur Jez: Complexity of solutions of equations over sets of natural numbers. STACS 2008: 373-384

Alexander Okhotin: Representing a P-complete problem by small trellis automata. CSP 2008: 185-198

Alexander Okhotin: Recursive descent parsing for Boolean grammars. Acta Inf. 44(3-4): 167-189 (2007)

Alexander Okhotin: Nine Open Problems on Conjunctive and Boolean Grammars. Bulletin of the EATCS 91: 96-119 (2007)

Alexander Okhotin: Notes on Dual Concatenation. Int. J. Found. Comput. Sci. 18(6): 1361-1370 (2007)

Michael Domaratzki, Alexander Okhotin, Jeffrey Shallit: Enumeration of Context-Free Languages and Related Structures. Journal of Automata, Languages and Combinatorics 12(1-2): 79-95 (2007)

Alexander Okhotin, Oksana Yakimova: Language equations with complementation: Decision problems. Theor. Comput. Sci. 376(1-2): 112-126 (2007)

Artur Jez, Alexander Okhotin: Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth. CSR 2007: 168-181

Alexander Okhotin: Expressive Power of LL(k) Boolean Grammars. FCT 2007: 446-457

Alexander Okhotin: Unambiguous Boolean grammars. LATA 2007: 473-484

Alexander Okhotin: A Simple P-Complete Problem and Its Representations by Language Equations. MCU 2007: 267-278

Alexander Okhotin: Computational Universality in One-variable Language Equations. Fundam. Inform. 74(4): 563-578 (2006)

Alexander Okhotin: Generalized Lr Parsing Algorithm for Boolean Grammars. Int. J. Found. Comput. Sci. 17(3): 629-664 (2006)

Juhani Karhumäki, Michal Kunc, Alexander Okhotin: Computing by commuting. Theor. Comput. Sci. 356(1-2): 200-211 (2006)

Alexander Okhotin: Language Equations with Symmetric Difference. CSR 2006: 292-303

Alexander Okhotin, Oksana Yakimova: Language Equations with Complementation. Developments in Language Theory 2006: 420-432

Juhani Karhumäki, Michal Kunc, Alexander Okhotin: Communication of Two Stacks and Rewriting. ICALP (2) 2006: 468-479

Alexander Okhotin, Kai Salomaa: Contextual Grammars with Uniform Sets of Trajectories. Fundam. Inform. 64(1-4): 341-351 (2005)

Alexander Okhotin: A characterization of the arithmetical hierarchy by language equations. Int. J. Found. Comput. Sci. 16(5): 985-998 (2005)

Alexander Okhotin: The dual of concatenation. Theor. Comput. Sci. 345(2-3): 425-447 (2005)

Alexander Okhotin: Unresolved systems of language equations: Expressive power and decision problems. Theor. Comput. Sci. 349(3): 283-308 (2005)

Michael Domaratzki, Alexander Okhotin, Jeffrey Shallit: Enumeration of Context-Free Languages and Related Structures. DCFS 2005: 85-96

Galina Jirásková, Alexander Okhotin: State complexity of cyclic shift. DCFS 2005: 182-193

Alexander Okhotin: LR Parsing for Boolean Grammars. Developments in Language Theory 2005: 362-373

Alexander Okhotin: Strict Language Inequalities and Their Decision Problems. MFCS 2005: 708-719

Alexander Okhotin: Boolean grammars. Inf. Comput. 194(1): 19-48 (2004)

Alexander Okhotin: On the equivalence of linear conjunctive grammars and trellis automata. ITA 38(1): 69-88 (2004)

Alexander Okhotin: State Complexity of Linear Conjunctive Grammars. Journal of Automata, Languages and Combinatorics 9(2/3): 365-381 (2004)

Michael Domaratzki, Alexander Okhotin: Representing recursively enumerable languages by iterated deletion. Theor. Comput. Sci. 314(3): 451-457 (2004)

Alexander Okhotin: On the number of nonterminals in linear conjunctive grammars. Theor. Comput. Sci. 320(2-3): 419-448 (2004)

Alexander Okhotin: A characterization of the arithmetical hierarchy by language equations. DCFS 2004: 225-237

Alexander Okhotin: On Computational Universality in Language Equations. MCU 2004: 292-303

Alexander Okhotin: The Dual of Concatenation. MFCS 2004: 698-710

Michael Domaratzki, Alexander Okhotin, Kai Salomaa, Sheng Yu (Eds.): Implementation and Application of Automata, 9th International Conference, CIAA 2004, Kingston, Canada, July 22-24, 2004, Revised Selected Papers. Lecture Notes in Computer Science 3317, Springer 2004, isbn 3-540-24318-6

Alexander Okhotin: An overview of conjunctive grammars, Formal Language Theory Column. Bulletin of the EATCS 79: 145-163 (2003)

Alexander Okhotin: Efficient Automaton-Based Recognition For Linear Conjunctive Languages. Int. J. Found. Comput. Sci. 14(6): 1103-1116 (2003)

Alexander Okhotin: The hardest linear conjunctive language. Inf. Process. Lett. 86(5): 247-253 (2003)

Alexander Okhotin: On the closure properties of linear conjunctive languages. Theor. Comput. Sci. 1-3(299): 663-685 (2003)

Alexander Okhotin: A recognition and parsing algorithm for arbitrary conjunctive grammars. Theor. Comput. Sci. 302(1-3): 365-399 (2003)

Alexander Okhotin: On the Number of Nonterminals in Linear Conjunctive Grammars. DCFS 2003: 274-283

Alexander Okhotin: Boolean Grammars. Developments in Language Theory 2003: 398-410

Alexander Okhotin: Decision Problems for Language Equations with Boolean Operations. ICALP 2003: 239-251

Alexander Okhotin, Kai Salomaa, Michael Domaratzki: One-Visit Caterpillar Tree Automata. Fundam. Inform. 52(4): 361-375 (2002)

Alexander Okhotin: Top-Down Parsing of Conjunctive Languages. Grammars 5(1): 21-40 (2002)

Alexander Okhotin: LR Parsing for Conjunctive Grammars. Grammars 5(2): 81-124 (2002)

Alexander Okhotin: Conjunctive Grammars and Systems of Language Equations. Programming and Computer Software 28(5): 243-249 (2002)

Alexander Okhotin: State complexity of linear conjunctive languages. DCFS 2002: 256-270

Alexander Okhotin: Automaton Representation of Linear Conjunctive Languages. Developments in Language Theory 2002: 393-404

Alexander Okhotin: Efficient Automaton-Based Recognition for Linear Conjunctive Languages. CIAA 2002: 169-181

Alexander Okhotin: Whale Calf, a Parser Generator for Conjunctive Grammars. CIAA 2002: 213-220

Alexander Okhotin: Conjunctive Grammars. Journal of Automata, Languages and Combinatorics 6(4): 519-535 (2001)