×
Author ID: okhotin.alexander Recent zbMATH articles by "Okhotin, Alexander"
Published as: Okhotin, Alexander; Okhotin, A. S.
External Links: MGP · ORCID · Wikidata · Math-Net.Ru · dblp

Publications by Year

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 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

Citations by Year

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.