Edit Profile (opens in new tab) Okhotin, Alexander Compute Distance To: Compute Author ID: okhotin.alexander Published as: Okhotin, Alexander; Okhotin, A. S. External Links: MGP · ORCID · Wikidata · Math-Net.Ru · dblp Documents Indexed: 161 Publications since 2001 7 Contributions as Editor Reviewing Activity: 1 Review Co-Authors: 39 Co-Authors with 109 Joint Publications 849 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 6 Lehtinen, Tommi 5 Domaratzki, Michael 5 Sazhneva, Elizaveta 4 Baader, Franz 3 Reitwießner, Christian 3 Shallit, Jeffrey O. 3 Yakimova, Oksana S. 2 Bakinova, Ekaterina 2 Basharin, Artem 2 Batmanov, Igor 2 Dobronravov, Egor 2 Dobronravov, Nikita 2 Ibarra, Oscar H. 2 Itsykson, Dmitry M. 2 Jürgensen, Helmut 2 Lyubort, Konstantin 2 Marantidis, Pavlos 2 Mrykhin, Mikhail 2 Oparin, Vsevolod 1 Geffert, Viliam 1 Kari, Jarkko 1 Krymski, Stanislav 1 Kuznetsov, Stepan L’vovich 1 Makarov, Vladislav 1 Martín-Vide, Carlos 1 Mottet, Antoine 1 Petrov, Semyon 1 Piao, Xiaoxue 1 Rondogiannis, Panos 1 Selivanov, Viktor L’vovich 1 Shapira, Dana 1 Sorokin, Alexey 1 Yu, Sheng all top 5 Serials 28 Theoretical Computer Science 13 Information and Computation 11 Fundamenta Informaticae 9 International Journal of Foundations of Computer Science 5 Theory of Computing Systems 5 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 165 Computer science (68-XX) 19 Mathematical logic and foundations (03-XX) 7 General and overarching topics; collections (00-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 Group theory and generalizations (20-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 123 Publications have been cited 755 times in 222 Documents Cited by ▼ Year ▼ Conjunctive grammars. Zbl 1004.68082Okhotin, Alexander 60 2001 Boolean grammars. Zbl 1073.68037Okhotin, Alexander 45 2004 On the equivalence of linear conjunctive grammars and trellis automata. Zbl 1084.68079Okhotin, Alexander 29 2004 Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth. Zbl 1183.68327Jeż, Artur; Okhotin, Alexander 24 2010 State complexity of power. Zbl 1168.68024Domaratzki, Michael; Okhotin, Alexander 23 2009 Conjunctive and Boolean grammars: the true general case of the context-free grammars. Zbl 1286.68268Okhotin, Alexander 23 2013 Conjunctive grammars and systems of language equations. Zbl 1036.68063Okhotin, A. S. 18 2002 Complexity of equations over sets of natural numbers. Zbl 1209.68263Jeż, Artur; Okhotin, Alexander 15 2011 Unambiguous finite automata over a unary alphabet. Zbl 1280.68118Okhotin, Alexander 14 2012 Describing periodicity in two-way deterministic finite automata using transformation semigroups. Zbl 1221.68157Kunc, Michal; Okhotin, Alexander 13 2011 Parsing by matrix multiplication generalized to Boolean grammars. Zbl 1277.68108Okhotin, Alexander 13 2014 Generalized LR parsing algorithm for Boolean grammars. Zbl 1098.68060Okhotin, Alexander 12 2006 Decision problems for language equations. Zbl 1201.68067Okhotin, Alexander 12 2010 State complexity of cyclic shift. Zbl 1144.68033Jirásková, Galina; Okhotin, Alexander 12 2008 On the state complexity of star of union and star of intersection. Zbl 1252.68175Jirásková, Galina; Okhotin, Alexander 11 2011 Unambiguous Boolean grammars. Zbl 1328.68106Okhotin, Alexander 11 2008 An extension of context-free grammars with one-sided context specifications. Zbl 1360.68531Barash, Mikhail; Okhotin, Alexander 10 2014 A recognition and parsing algorithm for arbitrary conjunctive grammars. Zbl 1044.68081Okhotin, Alexander 10 2003 The dual of concatenation. Zbl 1079.68053Okhotin, Alexander 10 2005 Recursive descent parsing for Boolean grammars. Zbl 1119.68101Okhotin, Alexander 10 2007 On the computational completeness of equations over sets of natural numbers. Zbl 1155.03309Jeż, Artur; Okhotin, Alexander 10 2008 On the expressive power of univariate equations over sets of natural numbers. Zbl 1263.68102Okhotin, Alexander; Rondogiannis, Panos 10 2012 Conjunctive grammars with restricted disjunction. Zbl 1203.68078Okhotin, Alexander; Reitwießner, Christian 9 2010 Unresolved systems of language equations: expressive power and decision problems. Zbl 1086.68077Okhotin, Alexander 9 2005 On the closure properties of linear conjunctive languages. Zbl 1042.68069Okhotin, Alexander 9 2003 Decision problems for language equations with Boolean operations. Zbl 1039.68069Okhotin, Alexander 9 2003 Fast parsing for Boolean grammars: a generalization of Valiant’s algorithm. Zbl 1250.68145Okhotin, Alexander 8 2010 On the state complexity of scattered substrings and superstrings. Zbl 1208.68139Okhotin, Alexander 8 2010 One-nonterminal conjunctive grammars over a unary alphabet. Zbl 1248.68304Jeż, Artur; Okhotin, Alexander 8 2011 Unambiguous finite automata over a unary alphabet. Zbl 1287.68098Okhotin, Alexander 7 2010 On the number of nonterminals in linear conjunctive grammars. Zbl 1068.68072Okhotin, Alexander 7 2004 On stateless multihead automata: Hierarchies and the emptiness problem. Zbl 1136.68397Ibarra, Oscar H.; Karhumäki, Juhani; Okhotin, Alexander 7 2008 On stateless multihead automata: hierarchies and the emptiness problem. Zbl 1184.68316Ibarra, Oscar H.; Karhumäki, Juhani; Okhotin, Alexander 7 2010 State complexity of operations on two-way finite automata over a unary alphabet. Zbl 1255.68078Kunc, Michal; Okhotin, Alexander 7 2012 On the state complexity of operations on two-way finite automata. Zbl 1161.68540Jirásková, Galina; Okhotin, Alexander 7 2008 State complexity of operations on input-driven pushdown automata. Zbl 1370.68186Okhotin, Alexander; Salomaa, Kai 7 2017 Top-down parsing of conjunctive languages. Zbl 1003.68058Okhotin, Alexander 6 2002 Input-driven languages are linear conjunctive. Zbl 1335.68127Okhotin, Alexander 6 2016 State complexity of operations on input-driven pushdown automata. Zbl 1343.68147Okhotin, Alexander; Salomaa, Kai 6 2011 Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth. Zbl 1188.68165Jeż, Artur; Okhotin, Alexander 6 2007 Non-erasing variants of the Chomsky-Schützenberger theorem. Zbl 1370.68211Okhotin, Alexander 6 2012 Representing hyper-arithmetical sets by equations over sets of integers. Zbl 1279.68158Jeż, Artur; Okhotin, Alexander 6 2012 Equations over sets of natural numbers with addition only. Zbl 1236.68171Jeż, Artur; Okhotin, Alexander 6 2009 Nine open problems on conjunctive and Boolean grammars. Zbl 1169.68454Okhotin, Alexander 6 2007 Descriptional complexity of unambiguous input-driven pushdown automata. Zbl 1318.68111Okhotin, Alexander; Salomaa, Kai 6 2015 Boolean grammars and gsm mappings. Zbl 1207.68176Lehtinen, Tommi; Okhotin, Alexander 5 2010 Computational completeness of equations over sets of natural numbers. Zbl 1291.03078Jeż, Artur; Okhotin, Alexander 5 2014 Automaton representation of linear conjunctive languages. Zbl 1015.68093Okhotin, Alexander 5 2003 Whale Calf, a parser generator for conjunctive grammars. Zbl 1033.68579Okhotin, Alexander 5 2003 On the complexity of the string geneation problem. Zbl 1088.68611Okhotin, A. S. 5 2003 Language equations with complementation: decision problems. Zbl 1111.68062Okhotin, Alexander; Yakimova, Oksana 5 2007 Comparing linear conjunctive languages to subfamilies of the context-free languages. Zbl 1298.68153Okhotin, Alexander 5 2011 On equations over sets of numbers and their limitations. Zbl 1209.68301Lehtinen, Tommi; Okhotin, Alexander 5 2011 The hardest linear conjunctive language. Zbl 1162.68474Okhotin, Alexander 5 2003 Homomorphisms preserving linear conjunctive languages. Zbl 1193.68156Okhotin, Alexander 5 2008 Language equations with complementation: expressive power. Zbl 1279.68168Okhotin, Alexander; Yakimova, Oksana 5 2012 LR parsing for conjunctive grammars. Zbl 1041.68054Okhotin, Alexander 4 2002 On language equations \(XXK = XXL\) and \(XM = N\) over a unary alphabet. Zbl 1205.68207Lehtinen, Tommi; Okhotin, Alexander 4 2010 Transforming two-way alternating finite automata to one-way nondeterministic automata. Zbl 1425.68200Geffert, Viliam; Okhotin, Alexander 4 2014 Input-driven pushdown automata with limited nondeterminism (invited paper). Zbl 1425.68224Okhotin, Alexander; Salomaa, Kai 4 2014 State complexity of operations on two-way deterministic finite automata over a unary alphabet. Zbl 1341.68099Kunc, Michal; Okhotin, Alexander 4 2011 Parsing Boolean grammars over a one-letter alphabet using online convolution. Zbl 1253.68200Okhotin, Alexander; Reitwießner, Christian 4 2012 Two-sided context specifications in formal grammars. Zbl 1408.68086Barash, Mikhail; Okhotin, Alexander 4 2015 Linear grammars with one-sided contexts and their automaton representation. Zbl 1328.68100Barash, Mikhail; Okhotin, Alexander 4 2015 On language equations with one-sided concatenation. Zbl 1359.68155Baader, Franz; Okhotin, Alexander 4 2013 Edit distance neighbourhoods of input-driven pushdown automata. Zbl 06763511Okhotin, Alexander; Salomaa, Kai 4 2017 A tale of conjunctive grammars. Zbl 06983366Okhotin, Alexander 3 2018 Conjunctive categorial grammars. Zbl 1376.03034Kuznetsov, Stepan; Okhotin, Alexander 3 2017 Approximate unification in the description logic \(\mathcal {FL}_0\). Zbl 1483.68364Baader, Franz; Marantidis, Pavlos; Okhotin, Alexander 3 2016 Formal languages over GF(2). Zbl 1434.68226Bakinova, Ekaterina; Basharin, Artem; Batmanov, Igor; Lyubort, Konstantin; Okhotin, Alexander; Sazhneva, Elizaveta 3 2018 Complexity of solutions of equations over sets of natural numbers. Zbl 1259.68083Okhotin, Alexander; Jeż, Artur 3 2008 State complexity of union and intersection for two-way nondeterministic finite automata. Zbl 1234.68220Kunc, Michal; Okhotin, Alexander 3 2011 Expressive power of LL\((k)\) Boolean grammars. Zbl 1135.68450Okhotin, Alexander 3 2007 A simple P-complete problem and its language-theoretic representations. Zbl 1207.68197Okhotin, Alexander 3 2011 Reversibility of computations in graph-walking automata. Zbl 1398.68317Kunc, Michal; Okhotin, Alexander 3 2013 Language equations with symmetric difference. Zbl 1263.68101Okhotin, Alexander 3 2012 Improved normal form for grammars with one-sided contexts. Zbl 1329.68155Okhotin, Alexander 3 2015 On the expressive power of GF(2)-grammars. Zbl 1445.68120Makarov, Vladislav; Okhotin, Alexander 3 2019 Generalized LR parsing algorithm for grammars with one-sided contexts. Zbl 1379.68192Barash, Mikhail; Okhotin, Alexander 2 2017 Generalized LR parsing for grammars with contexts. Zbl 1466.68049Barash, Mikhail; Okhotin, Alexander 2 2015 Underlying principles and recurring ideas of formal grammars. Zbl 06894738Okhotin, Alexander 2 2018 Representing recursively enumerable languages by iterated deletion. Zbl 1072.68055Domaratzki, Michael; Okhotin, Alexander 2 2004 Boolean grammars. Zbl 1037.68071Okhotin, Alexander 2 2003 Strict language inequalities and their decision problems. Zbl 1156.68461Okhotin, Alexander 2 2005 Computational universality in one-variable language equations. Zbl 1106.68063Okhotin, Alexander 2 2006 Language equations with symmetric difference. Zbl 1185.68396Okhotin, Alexander 2 2006 Unambiguous conjunctive grammars over a one-letter alphabet. Zbl 1381.68106Jeż, Artur; Okhotin, Alexander 2 2013 State complexity of linear conjunctive languages. Zbl 1098.68076Okhotin, Alexander 2 2004 Efficient automaton-based recognition for linear conjunctive languages. Zbl 1101.68663Okhotin, Alexander 2 2003 Descriptional complexity of unambiguous nested word automata. Zbl 1330.68172Okhotin, Alexander; Salomaa, Kai 2 2011 Descriptional complexity of input-driven pushdown automata. Zbl 1367.68176Okhotin, Alexander; Piao, Xiaoxue; Salomaa, Kai 2 2012 State complexity of GF(2)-concatenation and GF(2)-inverse on unary languages. Zbl 1434.68282Okhotin, Alexander; Sazhneva, Elizaveta 2 2019 Further closure properties of input-driven pushdown automata. Zbl 1435.68180Okhotin, Alexander; Salomaa, Kai 2 2018 Defining contexts in context-free grammars. Zbl 1351.68127Barash, Mikhail; Okhotin, Alexander 2 2012 Language equations with complementation. Zbl 1227.68066Okhotin, Alexander; Yakimova, Oksana 2 2006 Hardest languages for conjunctive and Boolean grammars. Zbl 1426.68152Okhotin, Alexander 2 2019 State complexity of unambiguous operations on finite automata. Zbl 1435.68170Jirásková, Galina; Okhotin, Alexander 2 2019 Edit distance neighbourhoods of input-driven pushdown automata. Zbl 1423.68262Okhotin, Alexander; Salomaa, Kai 2 2019 The quotient operation on input-driven pushdown automata. Zbl 1426.68153Okhotin, Alexander; Salomaa, Kai 2 2017 Least and greatest solutions of equations over sets of integers. Zbl 1287.03090Jeż, Artur; Okhotin, Alexander 1 2010 On hardest languages for one-dimensional cellular automata. Zbl 07405982Mrykhin, Mikhail; Okhotin, Alexander 1 2021 Language equations. Zbl 07469519Kunc, Michal; Okhotin, Alexander 1 2021 Extensions of unificationmodulo ACUI. Zbl 07283028Baader, Franz; Marantidis, Pavlos; Mottet, Antoine; Okhotin, Alexander 1 2020 On the expressive power of GF(2)-grammars. Zbl 1445.68120Makarov, Vladislav; Okhotin, Alexander 3 2019 State complexity of GF(2)-concatenation and GF(2)-inverse on unary languages. Zbl 1434.68282Okhotin, Alexander; Sazhneva, Elizaveta 2 2019 Hardest languages for conjunctive and Boolean grammars. Zbl 1426.68152Okhotin, Alexander 2 2019 State complexity of unambiguous operations on finite automata. Zbl 1435.68170Jirásková, Galina; Okhotin, Alexander 2 2019 Edit distance neighbourhoods of input-driven pushdown automata. Zbl 1423.68262Okhotin, Alexander; Salomaa, Kai 2 2019 A tale of conjunctive grammars. Zbl 06983366Okhotin, Alexander 3 2018 Formal languages over GF(2). Zbl 1434.68226Bakinova, Ekaterina; Basharin, Artem; Batmanov, Igor; Lyubort, Konstantin; Okhotin, Alexander; Sazhneva, Elizaveta 3 2018 Underlying principles and recurring ideas of formal grammars. Zbl 06894738Okhotin, Alexander 2 2018 Further closure properties of input-driven pushdown automata. Zbl 1435.68180Okhotin, Alexander; Salomaa, Kai 2 2018 Towards exact state complexity bounds for input-driven pushdown automata. Zbl 06983398Jirásková, Galina; Okhotin, Alexander 1 2018 State complexity of operations on input-driven pushdown automata. Zbl 1370.68186Okhotin, Alexander; Salomaa, Kai 7 2017 Edit distance neighbourhoods of input-driven pushdown automata. Zbl 06763511Okhotin, Alexander; Salomaa, Kai 4 2017 Conjunctive categorial grammars. Zbl 1376.03034Kuznetsov, Stepan; Okhotin, Alexander 3 2017 Generalized LR parsing algorithm for grammars with one-sided contexts. Zbl 1379.68192Barash, Mikhail; Okhotin, Alexander 2 2017 The quotient operation on input-driven pushdown automata. Zbl 1426.68153Okhotin, Alexander; Salomaa, Kai 2 2017 Unambiguous conjunctive grammars over a one-symbol alphabet. Zbl 1356.68121Jeż, Artur; Okhotin, Alexander 1 2017 On the state complexity of operations on two-way finite automata. Zbl 1371.68153Jirásková, Galina; Okhotin, Alexander 1 2017 Input-driven languages are linear conjunctive. Zbl 1335.68127Okhotin, Alexander 6 2016 Approximate unification in the description logic \(\mathcal {FL}_0\). Zbl 1483.68364Baader, Franz; Marantidis, Pavlos; Okhotin, Alexander 3 2016 Equations over sets of integers with addition only. Zbl 1342.68185Jeż, Artur; Okhotin, Alexander 1 2016 Descriptional complexity of unambiguous input-driven pushdown automata. Zbl 1318.68111Okhotin, Alexander; Salomaa, Kai 6 2015 Two-sided context specifications in formal grammars. Zbl 1408.68086Barash, Mikhail; Okhotin, Alexander 4 2015 Linear grammars with one-sided contexts and their automaton representation. Zbl 1328.68100Barash, Mikhail; Okhotin, Alexander 4 2015 Improved normal form for grammars with one-sided contexts. Zbl 1329.68155Okhotin, Alexander 3 2015 Generalized LR parsing for grammars with contexts. Zbl 1466.68049Barash, Mikhail; Okhotin, Alexander 2 2015 On language equations with concatenation and various sets of Boolean operations. Zbl 1347.68209Okhotin, Alexander 1 2015 Parsing by matrix multiplication generalized to Boolean grammars. Zbl 1277.68108Okhotin, Alexander 13 2014 An extension of context-free grammars with one-sided context specifications. Zbl 1360.68531Barash, Mikhail; Okhotin, Alexander 10 2014 Computational completeness of equations over sets of natural numbers. Zbl 1291.03078Jeż, Artur; Okhotin, Alexander 5 2014 Transforming two-way alternating finite automata to one-way nondeterministic automata. Zbl 1425.68200Geffert, Viliam; Okhotin, Alexander 4 2014 Input-driven pushdown automata with limited nondeterminism (invited paper). Zbl 1425.68224Okhotin, Alexander; Salomaa, Kai 4 2014 Linear grammars with one-sided contexts and their automaton representation. Zbl 1405.68159Barash, Mikhail; Okhotin, Alexander 1 2014 Conjunctive and Boolean grammars: the true general case of the context-free grammars. Zbl 1286.68268Okhotin, Alexander 23 2013 On language equations with one-sided concatenation. Zbl 1359.68155Baader, Franz; Okhotin, Alexander 4 2013 Reversibility of computations in graph-walking automata. Zbl 1398.68317Kunc, Michal; Okhotin, Alexander 3 2013 Unambiguous conjunctive grammars over a one-letter alphabet. Zbl 1381.68106Jeż, Artur; Okhotin, Alexander 2 2013 Homomorphisms preserving deterministic context-free languages. Zbl 1360.68610Lehtinen, Tommi; Okhotin, Alexander 1 2013 Improved normal form for grammars with one-sided contexts. Zbl 1390.68370Okhotin, Alexander 1 2013 Unambiguous finite automata over a unary alphabet. Zbl 1280.68118Okhotin, Alexander 14 2012 On the expressive power of univariate equations over sets of natural numbers. Zbl 1263.68102Okhotin, Alexander; Rondogiannis, Panos 10 2012 State complexity of operations on two-way finite automata over a unary alphabet. Zbl 1255.68078Kunc, Michal; Okhotin, Alexander 7 2012 Non-erasing variants of the Chomsky-Schützenberger theorem. Zbl 1370.68211Okhotin, Alexander 6 2012 Representing hyper-arithmetical sets by equations over sets of integers. Zbl 1279.68158Jeż, Artur; Okhotin, Alexander 6 2012 Language equations with complementation: expressive power. Zbl 1279.68168Okhotin, Alexander; Yakimova, Oksana 5 2012 Parsing Boolean grammars over a one-letter alphabet using online convolution. Zbl 1253.68200Okhotin, Alexander; Reitwießner, Christian 4 2012 Language equations with symmetric difference. Zbl 1263.68101Okhotin, Alexander 3 2012 Descriptional complexity of input-driven pushdown automata. Zbl 1367.68176Okhotin, Alexander; Piao, Xiaoxue; Salomaa, Kai 2 2012 Defining contexts in context-free grammars. Zbl 1351.68127Barash, Mikhail; Okhotin, Alexander 2 2012 Homomorphisms preserving deterministic context-free languages. Zbl 1370.68210Lehtinen, Tommi; Okhotin, Alexander 1 2012 On the number of nonterminal symbols in unambiguous conjunctive grammars. Zbl 1304.68089Jeż, Artur; Okhotin, Alexander 1 2012 Solving language equations and disequations with applications to disunification in description logics and monadic set constraints. Zbl 1352.68124Baader, Franz; Okhotin, Alexander 1 2012 Complexity of equations over sets of natural numbers. Zbl 1209.68263Jeż, Artur; Okhotin, Alexander 15 2011 Describing periodicity in two-way deterministic finite automata using transformation semigroups. Zbl 1221.68157Kunc, Michal; Okhotin, Alexander 13 2011 On the state complexity of star of union and star of intersection. Zbl 1252.68175Jirásková, Galina; Okhotin, Alexander 11 2011 One-nonterminal conjunctive grammars over a unary alphabet. Zbl 1248.68304Jeż, Artur; Okhotin, Alexander 8 2011 State complexity of operations on input-driven pushdown automata. Zbl 1343.68147Okhotin, Alexander; Salomaa, Kai 6 2011 Comparing linear conjunctive languages to subfamilies of the context-free languages. Zbl 1298.68153Okhotin, Alexander 5 2011 On equations over sets of numbers and their limitations. Zbl 1209.68301Lehtinen, Tommi; Okhotin, Alexander 5 2011 State complexity of operations on two-way deterministic finite automata over a unary alphabet. Zbl 1341.68099Kunc, Michal; Okhotin, Alexander 4 2011 State complexity of union and intersection for two-way nondeterministic finite automata. Zbl 1234.68220Kunc, Michal; Okhotin, Alexander 3 2011 A simple P-complete problem and its language-theoretic representations. Zbl 1207.68197Okhotin, Alexander 3 2011 Descriptional complexity of unambiguous nested word automata. Zbl 1330.68172Okhotin, Alexander; Salomaa, Kai 2 2011 Expressive power of \(\text{LL}(k)\) Boolean grammars. Zbl 1239.68040Okhotin, Alexander 1 2011 Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth. Zbl 1183.68327Jeż, Artur; Okhotin, Alexander 24 2010 Decision problems for language equations. Zbl 1201.68067Okhotin, Alexander 12 2010 Conjunctive grammars with restricted disjunction. Zbl 1203.68078Okhotin, Alexander; Reitwießner, Christian 9 2010 Fast parsing for Boolean grammars: a generalization of Valiant’s algorithm. Zbl 1250.68145Okhotin, Alexander 8 2010 On the state complexity of scattered substrings and superstrings. Zbl 1208.68139Okhotin, Alexander 8 2010 Unambiguous finite automata over a unary alphabet. Zbl 1287.68098Okhotin, Alexander 7 2010 On stateless multihead automata: hierarchies and the emptiness problem. Zbl 1184.68316Ibarra, Oscar H.; Karhumäki, Juhani; Okhotin, Alexander 7 2010 Boolean grammars and gsm mappings. Zbl 1207.68176Lehtinen, Tommi; Okhotin, Alexander 5 2010 On language equations \(XXK = XXL\) and \(XM = N\) over a unary alphabet. Zbl 1205.68207Lehtinen, Tommi; Okhotin, Alexander 4 2010 Least and greatest solutions of equations over sets of integers. Zbl 1287.03090Jeż, Artur; Okhotin, Alexander 1 2010 Computational power of two stacks with restricted communication. Zbl 1209.68288Karhumäki, Juhani; Kunc, Michal; Okhotin, Alexander 1 2010 State complexity of power. Zbl 1168.68024Domaratzki, Michael; Okhotin, Alexander 23 2009 Equations over sets of natural numbers with addition only. Zbl 1236.68171Jeż, Artur; Okhotin, Alexander 6 2009 State complexity of cyclic shift. Zbl 1144.68033Jirásková, Galina; Okhotin, Alexander 12 2008 Unambiguous Boolean grammars. Zbl 1328.68106Okhotin, Alexander 11 2008 On the computational completeness of equations over sets of natural numbers. Zbl 1155.03309Jeż, Artur; Okhotin, Alexander 10 2008 On stateless multihead automata: Hierarchies and the emptiness problem. Zbl 1136.68397Ibarra, Oscar H.; Karhumäki, Juhani; Okhotin, Alexander 7 2008 On the state complexity of operations on two-way finite automata. Zbl 1161.68540Jirásková, Galina; Okhotin, Alexander 7 2008 Homomorphisms preserving linear conjunctive languages. Zbl 1193.68156Okhotin, Alexander 5 2008 Complexity of solutions of equations over sets of natural numbers. Zbl 1259.68083Okhotin, Alexander; Jeż, Artur 3 2008 Recursive descent parsing for Boolean grammars. Zbl 1119.68101Okhotin, Alexander 10 2007 Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth. Zbl 1188.68165Jeż, Artur; Okhotin, Alexander 6 2007 Nine open problems on conjunctive and Boolean grammars. Zbl 1169.68454Okhotin, Alexander 6 2007 Language equations with complementation: decision problems. Zbl 1111.68062Okhotin, Alexander; Yakimova, Oksana 5 2007 Expressive power of LL\((k)\) Boolean grammars. Zbl 1135.68450Okhotin, Alexander 3 2007 Notes on dual concatenation. Zbl 1183.68352Okhotin, Alexander 1 2007 Generalized LR parsing algorithm for Boolean grammars. Zbl 1098.68060Okhotin, Alexander 12 2006 Computational universality in one-variable language equations. Zbl 1106.68063Okhotin, Alexander 2 2006 Language equations with symmetric difference. Zbl 1185.68396Okhotin, Alexander 2 2006 Language equations with complementation. Zbl 1227.68066Okhotin, Alexander; Yakimova, Oksana 2 2006 Computing by commuting. Zbl 1160.68415Karhumäki, Juhani; Kunc, Michal; Okhotin, Alexander 1 2006 Communication of two stacks and rewriting. Zbl 1133.68356Karhumäki, Juhani; Kunc, Michal; Okhotin, Alexander 1 2006 The dual of concatenation. Zbl 1079.68053Okhotin, Alexander 10 2005 Unresolved systems of language equations: expressive power and decision problems. Zbl 1086.68077Okhotin, Alexander 9 2005 ...and 23 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 212 Authors 74 Okhotin, Alexander 20 Salomaa, Kai T. 16 Kutrib, Martin 11 Jeż, Artur 11 Jirásková, Galina 9 Yu, Sheng 8 Gao, Yuan 8 Kari, Lila 8 Malcher, Andreas 6 Han, Yo-Sub 6 Kunc, Michal 6 Pighizzini, Giovanni 6 Wendlandt, Matthias 5 Barash, Mikhail 5 Ibarra, Oscar H. 5 Piao, Xiaoxue 5 Rondogiannis, Panos 4 Aizikowitz, Tamar 4 Baader, Franz 4 Cui, Bo 4 Domaratzki, Michael 4 Kaminski, Michael 4 Ko, Sang-Ki 4 Lehtinen, Tommi 4 Luque, Jean-Gabriel 4 Nomikos, Christos 4 Otto, Friedrich 3 Brzozowski, Janusz Antoni 3 Caron, Pascal 3 Crespi Reghizzi, Stefano 3 Egecioglu, Omer 3 Eom, Hae-Sung 3 Geffert, Viliam 3 Holzer, Markus 3 Kapoutsis, Christos A. 3 Kountouriotis, Vassilis 3 Kuznetsov, Stepan L’vovich 3 Marantidis, Pavlos 3 Mereghetti, Carlo 3 Palano, Beatrice 3 Patrou, Bruno 3 Reitwießner, Christian 2 Akl, Selim G. 2 Bianchi, Maria Paola 2 Court, Edwin Hamel-De Le 2 Ésik, Zoltán 2 Geldenhuys, Jaco 2 Glaßer, Christian 2 Gruber, Hermann 2 Jirásek, Jozef jun. 2 Jonsson, Peter A. 2 Kanovich, Max Iosifovich 2 Karhumaki, Juhani 2 Mahalingam, Kalpana 2 Maity, Anuran 2 Mandrioli, Dino 2 Martin, Barnaby D. 2 Messerschmidt, Hartmut 2 Mrykhin, Mikhail 2 Palioudakis, Alexandros 2 Pandoh, Palak 2 Prigioniero, Luca 2 Rajasekaran, Aayush 2 Sazhneva, Elizaveta 2 Scedrov, Andre 2 Šebej, Juraj 2 Shallit, Jeffrey O. 2 Šiljak, Dragoslav D. 2 van Zijl, Lynette 2 Yakimova, Oksana S. 2 Yoshinaka, Ryo 2 Zakzok, Mohammad 1 Abascal, Jackson 1 Alhazov, Artiom 1 Azimov, Rustam 1 Bakinova, Ekaterina 1 Basharin, Artem 1 Batmanov, Igor 1 Bednárová, Zuzana 1 Bernardy, Jean-Philippe 1 Berwanger, Dietmar 1 Björklund, Henrik 1 Bonsangue, Marcello Maria 1 Borgwardt, Stefan 1 Camino, Carlos 1 Chiniforooshan, Ehsan 1 Cho, Da-Jung 1 Claessen, Koen 1 Clark, Alexander T. 1 Daley, Mark 1 Dassow, Jürgen 1 Davies, Sylvie 1 Dawar, Anuj 1 Diekert, Volker 1 Dobronravov, Egor 1 Dobronravov, Nikita 1 Düntsch, Ivo 1 Dundua, Besik 1 Efanov, Nikolaĭ Nikolaevich 1 Fernández Gil, Oliver ...and 112 more Authors all top 5 Cited in 36 Serials 60 Theoretical Computer Science 26 International Journal of Foundations of Computer Science 24 Information and Computation 10 Theory of Computing Systems 9 Journal of Computer and System Sciences 7 Acta Informatica 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 Logical Methods in Computer Science 1 Artificial Intelligence 1 Information Processing Letters 1 Journal of Mathematical Analysis and Applications 1 Automatica 1 Kybernetika 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 Journal of Automata, Languages and Combinatorics 1 PAA. Pattern Analysis and Applications 1 Discrete Mathematics and Theoretical Computer Science. DMTCS 1 Fundamenta Informaticae 1 Natural Computing 1 Journal of Applied Logic 1 Chebyshevskiĭ Sbornik 1 Algorithms 1 Computer Science Review 1 Journal of Siberian Federal University. Mathematics & Physics all top 5 Cited in 14 Fields 213 Computer science (68-XX) 19 Mathematical logic and foundations (03-XX) 5 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 4 Information and communication theory, circuits (94-XX) 3 Systems theory; control (93-XX) 2 Combinatorics (05-XX) 2 Number theory (11-XX) 1 General algebraic systems (08-XX) 1 Group theory and generalizations (20-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.