Edit Profile (opens in new tab) Okhotin, Alexander Co-Author Distance Author ID: okhotin.alexander Published as: Okhotin, Alexander; Okhotin, A. S. External Links: MGP · ORCID · Wikidata · Math-Net.Ru · dblp Documents Indexed: 179 Publications since 2001, including 1 Additional arXiv Preprint 7 Contributions as Editor Reviewing Activity: 1 Review Co-Authors: 43 Co-Authors with 125 Joint Publications 976 Co-Co-Authors all top 5 Co-Authors 59 single-authored 19 Jeż, Artur 15 Salomaa, Kai T. 10 Kunc, Michal 9 Barash, Mikhail 9 Jirásková, Galina 8 Karhumaki, Juhani 7 Martynova, Olga 6 Lehtinen, Tommi 6 Sazhneva, Elizaveta 5 Domaratzki, Michael 5 Mrykhin, Mikhail 4 Baader, Franz 3 Petrov, Semyon 3 Reitwießner, Christian 3 Shallit, Jeffrey Outlaw 3 Yakimova, Oksana S. 2 Bakinova, Ekaterina 2 Basharin, Artem 2 Batmanov, Igor 2 Dobronravov, Egor 2 Dobronravov, Nikita 2 Geffert, Viliam 2 Ibarra, Oscar H. 2 Itsykson, Dmitry M. 2 Jürgensen, Helmut 2 Lyubort, Konstantin 2 Marantidis, Pavlos 2 Olkhovsky, Ilya 2 Oparin, Vsevolod 1 Grigorev, Semyon 1 Kari, Jarkko 1 Kuznetsov, Stepan L’vovich 1 Makarov, Vladislav 1 Martín-Vide, Carlos 1 Mottet, Antoine 1 Ogawa, Mizuhito 1 Petrov, Fedor Vladimirovich 1 Piao, Xiaoxue 1 Selivanov, Viktor L’vovich 1 Shapira, Dana 1 Shemetova, Ekaterina 1 Sorokin, Alexey 1 Yu, Sheng all top 5 Serials 30 Theoretical Computer Science 17 Information and Computation 11 Fundamenta Informaticae 10 International Journal of Foundations of Computer Science 6 Theory of Computing Systems 6 Journal of Automata, Languages and Combinatorics 4 Lecture Notes in Computer Science 3 Journal of Computer and System Sciences 2 Bulletin of the European Association for Theoretical Computer Science EATCS 2 Grammars 2 RAIRO. Theoretical Informatics and Applications 2 RAIRO. Theoretical Informatics and Applications 1 Acta Informatica 1 Information Processing Letters 1 Programming and Computer Software 1 MSCS. Mathematical Structures in Computer Science 1 Discrete Mathematics and Applications 1 Computer Science Review 1 ACM Transactions on Computation Theory Fields 183 Computer science (68-XX) 20 Mathematical logic and foundations (03-XX) 7 General and overarching topics; collections (00-XX) 2 Group theory and generalizations (20-XX) 1 Order, lattices, ordered algebraic structures (06-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 140 Publications have been cited 928 times in 292 Documents Cited by ▼ Year ▼ Conjunctive grammars. Zbl 1004.68082 Okhotin, Alexander 71 2001 Boolean grammars. Zbl 1073.68037 Okhotin, Alexander 48 2004 On the equivalence of linear conjunctive grammars and trellis automata. Zbl 1084.68079 Okhotin, Alexander 31 2004 State complexity of power. Zbl 1168.68024 Domaratzki, Michael; Okhotin, Alexander 28 2009 Conjunctive and Boolean grammars: the true general case of the context-free grammars. Zbl 1286.68268 Okhotin, Alexander 26 2013 Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth. Zbl 1183.68327 Jeż, Artur; Okhotin, Alexander 24 2010 State complexity of cyclic shift. Zbl 1144.68033 Jirásková, Galina; Okhotin, Alexander 20 2008 Conjunctive grammars and systems of language equations. Zbl 1036.68063 Okhotin, A. S. 19 2002 Describing periodicity in two-way deterministic finite automata using transformation semigroups. Zbl 1221.68157 Kunc, Michal; Okhotin, Alexander 18 2011 Unambiguous finite automata over a unary alphabet. Zbl 1280.68118 Okhotin, Alexander 17 2012 Complexity of equations over sets of natural numbers. Zbl 1209.68263 Jeż, Artur; Okhotin, Alexander 15 2011 Parsing by matrix multiplication generalized to Boolean grammars. Zbl 1277.68108 Okhotin, Alexander 15 2014 Decision problems for language equations. Zbl 1201.68067 Okhotin, Alexander 14 2010 An extension of context-free grammars with one-sided context specifications. Zbl 1360.68531 Barash, Mikhail; Okhotin, Alexander 14 2014 Generalized LR parsing algorithm for Boolean grammars. Zbl 1098.68060 Okhotin, Alexander 13 2006 On the state complexity of star of union and star of intersection. Zbl 1252.68175 Jirásková, Galina; Okhotin, Alexander 13 2011 The dual of concatenation. Zbl 1079.68053 Okhotin, Alexander 12 2005 Unambiguous Boolean grammars. Zbl 1328.68106 Okhotin, Alexander 12 2008 State complexity of operations on two-way finite automata over a unary alphabet. Zbl 1255.68078 Kunc, Michal; Okhotin, Alexander 11 2012 Input-driven pushdown automata with limited nondeterminism (invited paper). Zbl 1425.68224 Okhotin, Alexander; Salomaa, Kai 11 2014 On the state complexity of scattered substrings and superstrings. Zbl 1208.68139 Okhotin, Alexander 11 2010 Recursive descent parsing for Boolean grammars. Zbl 1119.68101 Okhotin, Alexander 10 2007 Conjunctive grammars with restricted disjunction. Zbl 1203.68078 Okhotin, Alexander; Reitwießner, Christian 10 2010 On the expressive power of univariate equations over sets of natural numbers. Zbl 1263.68102 Okhotin, Alexander; Rondogiannis, Panos 10 2012 A recognition and parsing algorithm for arbitrary conjunctive grammars. Zbl 1044.68081 Okhotin, Alexander 10 2003 On the computational completeness of equations over sets of natural numbers. Zbl 1155.03309 Jeż, Artur; Okhotin, Alexander 10 2008 Unresolved systems of language equations: expressive power and decision problems. Zbl 1086.68077 Okhotin, Alexander 9 2005 Decision problems for language equations with Boolean operations. Zbl 1039.68069 Okhotin, Alexander 9 2003 On the closure properties of linear conjunctive languages. Zbl 1042.68069 Okhotin, Alexander 9 2003 On stateless multihead automata: hierarchies and the emptiness problem. Zbl 1184.68316 Ibarra, Oscar H.; Karhumäki, Juhani; Okhotin, Alexander 8 2010 One-nonterminal conjunctive grammars over a unary alphabet. Zbl 1248.68304 Jeż, Artur; Okhotin, Alexander 8 2011 Transforming two-way alternating finite automata to one-way nondeterministic automata. Zbl 1425.68200 Geffert, Viliam; Okhotin, Alexander 8 2014 On the state complexity of operations on two-way finite automata. Zbl 1161.68540 Jirásková, Galina; Okhotin, Alexander 8 2008 Descriptional complexity of unambiguous input-driven pushdown automata. Zbl 1318.68111 Okhotin, Alexander; Salomaa, Kai 8 2015 State complexity of operations on input-driven pushdown automata. Zbl 1370.68186 Okhotin, Alexander; Salomaa, Kai 8 2017 Reversibility of computations in graph-walking automata. Zbl 1496.68176 Kunc, Michal; Okhotin, Alexander 8 2020 Unambiguous finite automata over a unary alphabet. Zbl 1287.68098 Okhotin, Alexander 8 2010 Fast parsing for Boolean grammars: a generalization of Valiant’s algorithm. Zbl 1250.68145 Okhotin, Alexander 8 2010 On stateless multihead automata: Hierarchies and the emptiness problem. Zbl 1136.68397 Ibarra, Oscar H.; Karhumäki, Juhani; Okhotin, Alexander 7 2008 Equations over sets of natural numbers with addition only. Zbl 1236.68171 Jeż, Artur; Okhotin, Alexander 7 2009 Top-down parsing of conjunctive languages. Zbl 1003.68058 Okhotin, Alexander 7 2002 On the number of nonterminals in linear conjunctive grammars. Zbl 1068.68072 Okhotin, Alexander 7 2004 On the complexity of the string geneation problem. Zbl 1088.68611 Okhotin, A. S. 7 2003 Non-erasing variants of the Chomsky-Schützenberger theorem. Zbl 1370.68211 Okhotin, Alexander 7 2012 A tale of conjunctive grammars. Zbl 1517.68169 Okhotin, Alexander 7 2018 Language equations with complementation: decision problems. Zbl 1111.68062 Okhotin, Alexander; Yakimova, Oksana 6 2007 Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth. Zbl 1188.68165 Jeż, Artur; Okhotin, Alexander 6 2007 State complexity of operations on input-driven pushdown automata. Zbl 1343.68147 Okhotin, Alexander; Salomaa, Kai 6 2011 Comparing linear conjunctive languages to subfamilies of the context-free languages. Zbl 1298.68153 Okhotin, Alexander 6 2011 State complexity of union and intersection for two-way nondeterministic finite automata. Zbl 1234.68220 Kunc, Michal; Okhotin, Alexander 6 2011 Nine open problems on conjunctive and Boolean grammars. Zbl 1169.68454 Okhotin, Alexander 6 2007 Computational completeness of equations over sets of natural numbers. Zbl 1291.03078 Jeż, Artur; Okhotin, Alexander 6 2014 Input-driven languages are linear conjunctive. Zbl 1335.68127 Okhotin, Alexander 6 2016 Two-sided context specifications in formal grammars. Zbl 1408.68086 Barash, Mikhail; Okhotin, Alexander 6 2015 Linear grammars with one-sided contexts and their automaton representation. Zbl 1328.68100 Barash, Mikhail; Okhotin, Alexander 6 2015 LR parsing for conjunctive grammars. Zbl 1041.68054 Okhotin, Alexander 6 2002 Boolean grammars and gsm mappings. Zbl 1207.68176 Lehtinen, Tommi; Okhotin, Alexander 6 2010 Representing hyper-arithmetical sets by equations over sets of integers. Zbl 1279.68158 Jeż, Artur; Okhotin, Alexander 6 2012 State complexity of operations on two-way deterministic finite automata over a unary alphabet. Zbl 1341.68099 Kunc, Michal; Okhotin, Alexander 5 2011 On equations over sets of numbers and their limitations. Zbl 1209.68301 Lehtinen, Tommi; Okhotin, Alexander 5 2011 Language equations with complementation: expressive power. Zbl 1279.68168 Okhotin, Alexander; Yakimova, Oksana 5 2012 Homomorphisms preserving linear conjunctive languages. Zbl 1193.68156 Okhotin, Alexander 5 2008 The hardest linear conjunctive language. Zbl 1162.68474 Okhotin, Alexander 5 2003 Edit distance neighbourhoods of input-driven pushdown automata. Zbl 1489.68133 Okhotin, Alexander; Salomaa, Kai 5 2017 On the state complexity of operations on two-way finite automata. Zbl 1371.68153 Jirásková, Galina; Okhotin, Alexander 5 2017 Automaton representation of linear conjunctive languages. Zbl 1015.68093 Okhotin, Alexander 5 2003 Whale Calf, a parser generator for conjunctive grammars. Zbl 1033.68579 Okhotin, Alexander 5 2003 On the expressive power of GF(2)-grammars. Zbl 1445.68120 Makarov, Vladislav; Okhotin, Alexander 5 2019 Hardest languages for conjunctive and Boolean grammars. Zbl 1426.68152 Okhotin, Alexander 5 2019 On language equations \(XXK = XXL\) and \(XM = N\) over a unary alphabet. Zbl 1205.68207 Lehtinen, Tommi; Okhotin, Alexander 5 2010 On hardest languages for one-dimensional cellular automata. Zbl 07405982 Mrykhin, Mikhail; Okhotin, Alexander 5 2021 Parsing Boolean grammars over a one-letter alphabet using online convolution. Zbl 1253.68200 Okhotin, Alexander; Reitwießner, Christian 4 2012 Language equations with symmetric difference. Zbl 1263.68101 Okhotin, Alexander 4 2012 Approximate unification in the description logic \(\mathcal {FL}_0\). Zbl 1483.68364 Baader, Franz; Marantidis, Pavlos; Okhotin, Alexander 4 2016 Improved normal form for grammars with one-sided contexts. Zbl 1329.68155 Okhotin, Alexander 4 2015 Input-driven pushdown automata on well-nested infinite strings. Zbl 07493541 Okhotin, Alexander; Selivanov, Victor L. 4 2021 On language equations with one-sided concatenation. Zbl 1359.68155 Baader, Franz; Okhotin, Alexander 4 2013 Underlying principles and recurring ideas of formal grammars. Zbl 1504.68091 Okhotin, Alexander 4 2018 Expressive power of LL\((k)\) Boolean grammars. Zbl 1135.68450 Okhotin, Alexander 3 2007 Expressive power of \(\text{LL}(k)\) Boolean grammars. Zbl 1239.68040 Okhotin, Alexander 3 2011 State complexity of linear conjunctive languages. Zbl 1098.68076 Okhotin, Alexander 3 2004 Representing recursively enumerable languages by iterated deletion. Zbl 1072.68055 Domaratzki, Michael; Okhotin, Alexander 3 2004 Strict language inequalities and their decision problems. Zbl 1156.68461 Okhotin, Alexander 3 2005 Generalized LR parsing algorithm for grammars with one-sided contexts. Zbl 1379.68192 Barash, Mikhail; Okhotin, Alexander 3 2017 Conjunctive categorial grammars. Zbl 1376.03034 Kuznetsov, Stepan; Okhotin, Alexander 3 2017 State complexity of unambiguous operations on finite automata. Zbl 1435.68170 Jirásková, Galina; Okhotin, Alexander 3 2019 Reversibility of computations in graph-walking automata. Zbl 1398.68317 Kunc, Michal; Okhotin, Alexander 3 2013 A simple P-complete problem and its language-theoretic representations. Zbl 1207.68197 Okhotin, Alexander 3 2011 Descriptional complexity of input-driven pushdown automata. Zbl 1367.68176 Okhotin, Alexander; Piao, Xiaoxue; Salomaa, Kai 3 2012 State complexity of GF(2)-concatenation and GF(2)-inverse on unary languages. Zbl 1434.68282 Okhotin, Alexander; Sazhneva, Elizaveta 3 2019 Formal languages over GF(2). Zbl 07488445 Bakinova, Ekaterina; Basharin, Artem; Batmanov, Igor; Lyubort, Konstantin; Okhotin, Alexander; Sazhneva, Elizaveta 3 2022 On the transformation of two-way deterministic finite automata to unambiguous finite automata. Zbl 07405979 Petrov, Semyon; Okhotin, Alexander 3 2021 Complexity of solutions of equations over sets of natural numbers. Zbl 1259.68083 Okhotin, Alexander; Jeż, Artur 3 2008 Formal languages over GF(2). Zbl 1434.68226 Bakinova, Ekaterina; Basharin, Artem; Batmanov, Igor; Lyubort, Konstantin; Okhotin, Alexander; Sazhneva, Elizaveta 3 2018 Edit distance neighbourhoods of input-driven pushdown automata. Zbl 1423.68262 Okhotin, Alexander; Salomaa, Kai 3 2019 Deterministic one-way simulation of two-way deterministic finite automata over small alphabets. Zbl 07614739 Geffert, Viliam; Okhotin, Alexander 3 2021 State complexity of union and intersection on graph-walking automata. Zbl 07614747 Martynova, Olga; Okhotin, Alexander 3 2021 Language equations with symmetric difference. Zbl 1185.68396 Okhotin, Alexander 2 2006 Efficient automaton-based recognition for linear conjunctive languages. Zbl 1101.68663 Okhotin, Alexander 2 2003 One-visit caterpillar tree automata. Zbl 1012.68102 Okhotin, Alexander; Salomaa, Kai; Domaratzki, Michael 2 2002 State complexity of transforming graph-walking automata to halting, returning and reversible. Zbl 1506.68048 Martynova, Olga; Okhotin, Alexander 2 2023 The hardest \(\operatorname{LL}(k)\) language. Zbl 07727037 Mrykhin, Mikhail; Okhotin, Alexander 1 2023 Formal languages over GF(2). Zbl 07488445 Bakinova, Ekaterina; Basharin, Artem; Batmanov, Igor; Lyubort, Konstantin; Okhotin, Alexander; Sazhneva, Elizaveta 3 2022 Rational index of languages with bounded dimension of parse trees. Zbl 07571015 Shemetova, Ekaterina; Okhotin, Alexander; Grigorev, Semyon 1 2022 State complexity of GF(2)-operations on unary languages. Zbl 07488459 Okhotin, Alexander; Sazhneva, Elizaveta 1 2022 On hardest languages for one-dimensional cellular automata. Zbl 07405982 Mrykhin, Mikhail; Okhotin, Alexander 5 2021 Input-driven pushdown automata on well-nested infinite strings. Zbl 07493541 Okhotin, Alexander; Selivanov, Victor L. 4 2021 On the transformation of two-way deterministic finite automata to unambiguous finite automata. Zbl 07405979 Petrov, Semyon; Okhotin, Alexander 3 2021 Deterministic one-way simulation of two-way deterministic finite automata over small alphabets. Zbl 07614739 Geffert, Viliam; Okhotin, Alexander 3 2021 State complexity of union and intersection on graph-walking automata. Zbl 07614747 Martynova, Olga; Okhotin, Alexander 3 2021 The hardest \(\operatorname{LL}(k)\) language. Zbl 1518.68186 Mrykhin, Mikhail; Okhotin, Alexander 1 2021 On the length of shortest strings accepted by two-way finite automata. Zbl 1497.68257 Dobronravov, Egor; Dobronravov, Nikita; Okhotin, Alexander 1 2021 Language equations. Zbl 1510.68038 Kunc, Michal; Okhotin, Alexander 1 2021 Reversibility of computations in graph-walking automata. Zbl 1496.68176 Kunc, Michal; Okhotin, Alexander 8 2020 Extensions of unification modulo ACUI. Zbl 1495.68237 Baader, Franz; Marantidis, Pavlos; Mottet, Antoine; Okhotin, Alexander 1 2020 Longer shortest strings in two-way finite automata. Zbl 07371293 Krymski, Stanislav; Okhotin, Alexander 1 2020 On the expressive power of GF(2)-grammars. Zbl 1445.68120 Makarov, Vladislav; Okhotin, Alexander 5 2019 Hardest languages for conjunctive and Boolean grammars. Zbl 1426.68152 Okhotin, Alexander 5 2019 State complexity of unambiguous operations on finite automata. Zbl 1435.68170 Jirásková, Galina; Okhotin, Alexander 3 2019 State complexity of GF(2)-concatenation and GF(2)-inverse on unary languages. Zbl 1434.68282 Okhotin, Alexander; Sazhneva, Elizaveta 3 2019 Edit distance neighbourhoods of input-driven pushdown automata. Zbl 1423.68262 Okhotin, Alexander; Salomaa, Kai 3 2019 Graph-walking automata: from whence they come, and whither they are bound. Zbl 1434.68281 Okhotin, Alexander 1 2019 A tale of conjunctive grammars. Zbl 1517.68169 Okhotin, Alexander 7 2018 Underlying principles and recurring ideas of formal grammars. Zbl 1504.68091 Okhotin, Alexander 4 2018 Formal languages over GF(2). Zbl 1434.68226 Bakinova, Ekaterina; Basharin, Artem; Batmanov, Igor; Lyubort, Konstantin; Okhotin, Alexander; Sazhneva, Elizaveta 3 2018 Further closure properties of input-driven pushdown automata. Zbl 1435.68180 Okhotin, Alexander; Salomaa, Kai 2 2018 Linear-space recognition for grammars with contexts. Zbl 1388.68152 Barash, Mikhail; Okhotin, Alexander 1 2018 Towards exact state complexity bounds for input-driven pushdown automata. Zbl 1517.68201 Jirásková, Galina; Okhotin, Alexander 1 2018 State complexity of operations on input-driven pushdown automata. Zbl 1370.68186 Okhotin, Alexander; Salomaa, Kai 8 2017 Edit distance neighbourhoods of input-driven pushdown automata. Zbl 1489.68133 Okhotin, Alexander; Salomaa, Kai 5 2017 On the state complexity of operations on two-way finite automata. Zbl 1371.68153 Jirásková, Galina; Okhotin, Alexander 5 2017 Generalized LR parsing algorithm for grammars with one-sided contexts. Zbl 1379.68192 Barash, Mikhail; Okhotin, Alexander 3 2017 Conjunctive categorial grammars. Zbl 1376.03034 Kuznetsov, Stepan; Okhotin, Alexander 3 2017 The quotient operation on input-driven pushdown automata. Zbl 1426.68153 Okhotin, Alexander; Salomaa, Kai 2 2017 Unambiguous conjunctive grammars over a one-symbol alphabet. Zbl 1356.68121 Jeż, Artur; Okhotin, Alexander 1 2017 Input-driven languages are linear conjunctive. Zbl 1335.68127 Okhotin, Alexander 6 2016 Approximate unification in the description logic \(\mathcal {FL}_0\). Zbl 1483.68364 Baader, Franz; Marantidis, Pavlos; Okhotin, Alexander 4 2016 Equations over sets of integers with addition only. Zbl 1342.68185 Jeż, Artur; Okhotin, Alexander 1 2016 Descriptional complexity of unambiguous input-driven pushdown automata. Zbl 1318.68111 Okhotin, Alexander; Salomaa, Kai 8 2015 Two-sided context specifications in formal grammars. Zbl 1408.68086 Barash, Mikhail; Okhotin, Alexander 6 2015 Linear grammars with one-sided contexts and their automaton representation. Zbl 1328.68100 Barash, Mikhail; Okhotin, Alexander 6 2015 Improved normal form for grammars with one-sided contexts. Zbl 1329.68155 Okhotin, Alexander 4 2015 Generalized LR parsing for grammars with contexts. Zbl 1466.68049 Barash, Mikhail; Okhotin, Alexander 2 2015 On language equations with concatenation and various sets of Boolean operations. Zbl 1347.68209 Okhotin, Alexander 1 2015 Parsing by matrix multiplication generalized to Boolean grammars. Zbl 1277.68108 Okhotin, Alexander 15 2014 An extension of context-free grammars with one-sided context specifications. Zbl 1360.68531 Barash, Mikhail; Okhotin, Alexander 14 2014 Input-driven pushdown automata with limited nondeterminism (invited paper). Zbl 1425.68224 Okhotin, Alexander; Salomaa, Kai 11 2014 Transforming two-way alternating finite automata to one-way nondeterministic automata. Zbl 1425.68200 Geffert, Viliam; Okhotin, Alexander 8 2014 Computational completeness of equations over sets of natural numbers. Zbl 1291.03078 Jeż, Artur; Okhotin, Alexander 6 2014 On the determinization blowup for finite automata recognizing equal-length languages. Zbl 1323.68341 Karhumäki, Juhani; Okhotin, Alexander 1 2014 Linear grammars with one-sided contexts and their automaton representation. Zbl 1405.68159 Barash, Mikhail; Okhotin, Alexander 1 2014 Conjunctive and Boolean grammars: the true general case of the context-free grammars. Zbl 1286.68268 Okhotin, Alexander 26 2013 On language equations with one-sided concatenation. Zbl 1359.68155 Baader, Franz; Okhotin, Alexander 4 2013 Reversibility of computations in graph-walking automata. Zbl 1398.68317 Kunc, Michal; Okhotin, Alexander 3 2013 Homomorphisms preserving deterministic context-free languages. Zbl 1360.68610 Lehtinen, Tommi; Okhotin, Alexander 2 2013 Unambiguous conjunctive grammars over a one-letter alphabet. Zbl 1381.68106 Jeż, Artur; Okhotin, Alexander 2 2013 Improved normal form for grammars with one-sided contexts. Zbl 1390.68370 Okhotin, Alexander 2 2013 Unambiguous finite automata over a unary alphabet. Zbl 1280.68118 Okhotin, Alexander 17 2012 State complexity of operations on two-way finite automata over a unary alphabet. Zbl 1255.68078 Kunc, Michal; Okhotin, Alexander 11 2012 On the expressive power of univariate equations over sets of natural numbers. Zbl 1263.68102 Okhotin, Alexander; Rondogiannis, Panos 10 2012 Non-erasing variants of the Chomsky-Schützenberger theorem. Zbl 1370.68211 Okhotin, Alexander 7 2012 Representing hyper-arithmetical sets by equations over sets of integers. Zbl 1279.68158 Jeż, Artur; Okhotin, Alexander 6 2012 Language equations with complementation: expressive power. Zbl 1279.68168 Okhotin, Alexander; Yakimova, Oksana 5 2012 Parsing Boolean grammars over a one-letter alphabet using online convolution. Zbl 1253.68200 Okhotin, Alexander; Reitwießner, Christian 4 2012 Language equations with symmetric difference. Zbl 1263.68101 Okhotin, Alexander 4 2012 Descriptional complexity of input-driven pushdown automata. Zbl 1367.68176 Okhotin, Alexander; Piao, Xiaoxue; Salomaa, Kai 3 2012 Defining contexts in context-free grammars. Zbl 1351.68127 Barash, Mikhail; Okhotin, Alexander 2 2012 Solving language equations and disequations with applications to disunification in description logics and monadic set constraints. Zbl 1352.68124 Baader, Franz; Okhotin, Alexander 2 2012 Homomorphisms preserving deterministic context-free languages. Zbl 1370.68210 Lehtinen, Tommi; Okhotin, Alexander 1 2012 On the number of nonterminal symbols in unambiguous conjunctive grammars. Zbl 1304.68089 Jeż, Artur; Okhotin, Alexander 1 2012 Describing periodicity in two-way deterministic finite automata using transformation semigroups. Zbl 1221.68157 Kunc, Michal; Okhotin, Alexander 18 2011 Complexity of equations over sets of natural numbers. Zbl 1209.68263 Jeż, Artur; Okhotin, Alexander 15 2011 On the state complexity of star of union and star of intersection. Zbl 1252.68175 Jirásková, Galina; Okhotin, Alexander 13 2011 One-nonterminal conjunctive grammars over a unary alphabet. Zbl 1248.68304 Jeż, Artur; Okhotin, Alexander 8 2011 State complexity of operations on input-driven pushdown automata. Zbl 1343.68147 Okhotin, Alexander; Salomaa, Kai 6 2011 Comparing linear conjunctive languages to subfamilies of the context-free languages. Zbl 1298.68153 Okhotin, Alexander 6 2011 State complexity of union and intersection for two-way nondeterministic finite automata. Zbl 1234.68220 Kunc, Michal; Okhotin, Alexander 6 2011 State complexity of operations on two-way deterministic finite automata over a unary alphabet. Zbl 1341.68099 Kunc, Michal; Okhotin, Alexander 5 2011 On equations over sets of numbers and their limitations. Zbl 1209.68301 Lehtinen, Tommi; Okhotin, Alexander 5 2011 Expressive power of \(\text{LL}(k)\) Boolean grammars. Zbl 1239.68040 Okhotin, Alexander 3 2011 A simple P-complete problem and its language-theoretic representations. Zbl 1207.68197 Okhotin, Alexander 3 2011 Descriptional complexity of unambiguous nested word automata. Zbl 1330.68172 Okhotin, Alexander; Salomaa, Kai 2 2011 Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth. Zbl 1183.68327 Jeż, Artur; Okhotin, Alexander 24 2010 Decision problems for language equations. Zbl 1201.68067 Okhotin, Alexander 14 2010 On the state complexity of scattered substrings and superstrings. Zbl 1208.68139 Okhotin, Alexander 11 2010 Conjunctive grammars with restricted disjunction. Zbl 1203.68078 Okhotin, Alexander; Reitwießner, Christian 10 2010 On stateless multihead automata: hierarchies and the emptiness problem. Zbl 1184.68316 Ibarra, Oscar H.; Karhumäki, Juhani; Okhotin, Alexander 8 2010 Unambiguous finite automata over a unary alphabet. Zbl 1287.68098 Okhotin, Alexander 8 2010 Fast parsing for Boolean grammars: a generalization of Valiant’s algorithm. Zbl 1250.68145 Okhotin, Alexander 8 2010 Boolean grammars and gsm mappings. Zbl 1207.68176 Lehtinen, Tommi; Okhotin, Alexander 6 2010 On language equations \(XXK = XXL\) and \(XM = N\) over a unary alphabet. Zbl 1205.68207 Lehtinen, Tommi; Okhotin, Alexander 5 2010 Least and greatest solutions of equations over sets of integers. Zbl 1287.03090 Jeż, Artur; Okhotin, Alexander 1 2010 Computational power of two stacks with restricted communication. Zbl 1209.68288 Karhumäki, Juhani; Kunc, Michal; Okhotin, Alexander 1 2010 State complexity of power. Zbl 1168.68024 Domaratzki, Michael; Okhotin, Alexander 28 2009 Equations over sets of natural numbers with addition only. Zbl 1236.68171 Jeż, Artur; Okhotin, Alexander 7 2009 State complexity of cyclic shift. Zbl 1144.68033 Jirásková, Galina; Okhotin, Alexander 20 2008 Unambiguous Boolean grammars. Zbl 1328.68106 Okhotin, Alexander 12 2008 On the computational completeness of equations over sets of natural numbers. Zbl 1155.03309 Jeż, Artur; Okhotin, Alexander 10 2008 On the state complexity of operations on two-way finite automata. Zbl 1161.68540 Jirásková, Galina; Okhotin, Alexander 8 2008 On stateless multihead automata: Hierarchies and the emptiness problem. Zbl 1136.68397 Ibarra, Oscar H.; Karhumäki, Juhani; Okhotin, Alexander 7 2008 ...and 40 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 263 Authors 92 Okhotin, Alexander 22 Salomaa, Kai T. 21 Kutrib, Martin 13 Jirásková, Galina 11 Jeż, Artur 10 Malcher, Andreas 10 Yu, Sheng 9 Han, Yo-Sub 9 Wendlandt, Matthias 8 Gao, Yuan 8 Kari, Lila 8 Martynova, Olga 7 Caron, Pascal 7 Luque, Jean-Gabriel 7 Pighizzini, Giovanni 6 Barash, Mikhail 6 Kunc, Michal 5 Baader, Franz 5 Geffert, Viliam 5 Hospodár, Michal 5 Ibarra, Oscar H. 5 Ko, Sang-Ki 5 Mrykhin, Mikhail 5 Otto, Friedrich 5 Patrou, Bruno 5 Piao, Xiaoxue 4 Aizikowitz, Tamar 4 Court, Edwin Hamel-De Le 4 Cui, Bo 4 Domaratzki, Michael 4 Holzer, Markus 4 Kaminski, Michael 4 Kapoutsis, Christos A. 4 Lehtinen, Tommi 4 Nomikos, Christos 4 Rondogiannis, Panos 4 Shallit, Jeffrey Outlaw 3 Brzozowski, Janusz Antoni 3 Crespi Reghizzi, Stefano 3 Dassow, Jürgen 3 Egecioglu, Omer 3 Eom, Hae-Sung 3 Kountouriotis, Vassilis 3 Kuznetsov, Stepan L’vovich 3 Marantidis, Pavlos 3 Mereghetti, Carlo 3 Mlynárčik, Peter 3 Palano, Beatrice 3 Prigioniero, Luca 3 Reitwießner, Christian 3 Sazhneva, Elizaveta 3 Šebej, Juraj 3 Selivanov, Viktor L’vovich 3 Yoshinaka, Ryo 3 Zakzok, Mohammad 2 Akl, Selim G. 2 Berwanger, Dietmar 2 Bianchi, Maria Paola 2 Cheon, Hyunjoon 2 Ésik, Zoltán 2 Fleischer, Lukas 2 Geldenhuys, Jaco 2 Glaßer, Christian 2 Gruber, Hermann 2 Hoffmann, Stefan 2 Jecker, Ismaël 2 Jirásek, Jozef jun. 2 Jonsson, Peter 2 Kanovich, Max Iosifovich 2 Karhumaki, Juhani 2 Mahalingam, Kalpana 2 Maity, Anuran 2 Mandrioli, Dino 2 Martin, Barnaby D. 2 Messerschmidt, Hartmut 2 Moriya, Etsuro 2 Olejár, Viktor 2 Olkhovsky, Ilya 2 Palioudakis, Alexandros 2 Pandoh, Palak 2 Petrov, Semyon 2 Rajasekaran, Aayush 2 Reidenbach, Daniel 2 Say, A. C. Cem 2 Scedrov, Andre 2 Schmid, Markus L. 2 Šiljak, Dragoslav D. 2 Terrier, Véronique 2 van den Bogaard, Marie 2 van der Merwe, Brink 2 van Zijl, Lynette 2 Yakimova, Oksana S. 2 Zan, Jinfeng 1 Abascal, Jackson 1 Alhazov, Artiom 1 Azimov, Rustam 1 Bachmeier, Georg 1 Bakinova, Ekaterina 1 Basharin, Artem 1 Batmanov, Igor ...and 163 more Authors all top 5 Cited in 40 Serials 66 Theoretical Computer Science 32 Information and Computation 31 International Journal of Foundations of Computer Science 11 Theory of Computing Systems 9 Acta Informatica 9 Journal of Computer and System Sciences 4 Journal of Automata, Languages and Combinatorics 3 Logical Methods in Computer Science 3 RAIRO. Theoretical Informatics and Applications 2 Journal of Mathematical Psychology 2 Programming and Computer Software 2 MSCS. Mathematical Structures in Computer Science 2 Journal of Functional Programming 2 RAIRO. Theoretical Informatics and Applications 2 Natural Computing 1 Artificial Intelligence 1 Information Processing Letters 1 Journal of Mathematical Analysis and Applications 1 Automatica 1 Kybernetika 1 Acta Mathematica Hungarica 1 Annals of Pure and Applied Logic 1 Algorithmica 1 Machine Learning 1 Discrete Mathematics and Applications 1 International Journal of Computer Mathematics 1 Formal Methods in System Design 1 Journal of Logic, Language and Information 1 Complexity 1 PAA. Pattern Analysis and Applications 1 Discrete Mathematics and Theoretical Computer Science. DMTCS 1 Fundamenta Informaticae 1 Theory and Practice of Logic Programming 1 Journal of Applied Logic 1 Chebyshevskiĭ Sbornik 1 Algorithms 1 Computability 1 Computer Science Review 1 Modelirovanie i Analiz Informatsionnykh Sistem 1 Journal of Siberian Federal University. Mathematics & Physics all top 5 Cited in 15 Fields 280 Computer science (68-XX) 24 Mathematical logic and foundations (03-XX) 6 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 4 Information and communication theory, circuits (94-XX) 3 Number theory (11-XX) 3 Systems theory; control (93-XX) 2 Combinatorics (05-XX) 2 Group theory and generalizations (20-XX) 1 General and overarching topics; collections (00-XX) 1 General algebraic systems (08-XX) 1 Ordinary differential equations (34-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Statistics (62-XX) 1 Quantum theory (81-XX) 1 Operations research, mathematical programming (90-XX) Citations by Year Wikidata Timeline The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.