Edit Profile Potapov, Igor Compute Distance To: Compute Author ID: potapov.igor Published as: Potapov, I.; Potapov, Igor Documents Indexed: 88 Publications since 2001, including 19 Books all top 5 Co-Authors 3 single-authored 14 Bell, Paul C. 8 Gąsieniec, Leszek Antoni 8 Kurganskyy, Oleksiy 6 Halava, Vesa 6 Niskanen, Reino 6 Semukhin, Pavel 5 Pagourtzis, Aris T. 4 Ko, Sang-Ki 4 Lisitsa, Alexei 3 Bournez, Olivier 3 Grunsky, Igor 3 Harju, Tero 3 Nickson, Thomas 3 Rytter, Wojciech 3 Worrell, James B. 2 Abdulla, Parosh Aziz 2 Delzanno, Giorgio 2 Finkel, Alain 2 Hirvensalo, Mika 2 Kolpakov, Roman M. 2 Kucera, Antonin 2 Larsen, Kim Guldstrand 2 Leroux, Jérôme 2 Martin, Russell A. 2 Ouaknine, Joel O. 2 Reichert, Julien 2 Saleh, Rafiq 2 Sancho-Caparrini, Fernando 2 Srba, Jiří 2 Xin, Qin 1 Adamson, Duncan 1 Almethen, Abdullah 1 Bojańczyk, Mikołaj 1 Ciabattoni, Agata 1 Deligkas, Argyrios 1 Demri, Stéphane P. 1 Diekert, Volker 1 Filiot, Emmanuel 1 Freivalds, Rūsiņš Mārtiņš 1 Gibbons, Alan M. 1 Gusev, Vladimir Valer’evich 1 Hague, Matthew 1 Ibarra, Oscar H. 1 Jungers, Raphaël M. 1 Karhumaki, Juhani 1 Lasota, Sławomir 1 Michail, Othon 1 Prianychnykova, Olena 1 Pryanichnikova, Elena 1 Radzik, Tomasz 1 Reynier, Pierre-Alain 1 Schmitz, Sylvain 1 Song, Haomin 1 Spirakis, Paul G. 1 Szeider, Stefan 1 Verlan, Sergey 1 Yen, Hsu-Chun all top 5 Serials 13 Lecture Notes in Computer Science 9 Theoretical Computer Science 7 International Journal of Foundations of Computer Science 6 Fundamenta Informaticae 2 Journal of Computer and System Sciences 2 Information and Computation 1 The Computer Journal. Section A / Section B 1 Algorithmica 1 International Journal of Algebra and Computation 1 Natural Computing 1 Electronic Notes in Theoretical Computer Science 1 LIPIcs – Leibniz International Proceedings in Informatics all top 5 Fields 77 Computer science (68-XX) 22 General and overarching topics; collections (00-XX) 16 Group theory and generalizations (20-XX) 13 Mathematical logic and foundations (03-XX) 9 Linear and multilinear algebra; matrix theory (15-XX) 4 Number theory (11-XX) 4 Dynamical systems and ergodic theory (37-XX) 4 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 3 Operations research, mathematical programming (90-XX) 2 Combinatorics (05-XX) 1 Convex and discrete geometry (52-XX) 1 Manifolds and cell complexes (57-XX) 1 Numerical analysis (65-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Systems theory; control (93-XX) 1 Information and communication theory, circuits (94-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH 44 Publications have been cited 136 times in 62 Documents Cited by ▼ Year ▼ Reachability problems in quaternion matrix and rotation semigroups. Zbl 1151.03021Bell, Paul; Potapov, Igor 9 2008 Matrix equations and Hilbert’s tenth problem. Zbl 1173.03009Bell, Paul; Halava, Vesa; Harju, Tero; Karhumäki, Juhani; Potapov, Igor 8 2008 On the computational complexity of matrix semigroup problems. Zbl 1242.68120Bell, Paul C.; Potapov, Igor 7 2012 On undecidability bounds for matrix decision problems. Zbl 1133.03019Bell, Paul; Potapov, Igor 7 2008 Deterministic communication in radio networks with large labels. Zbl 1147.68008Gąsieniec, Leszek; Pagourtzis, Aris; Potapov, Igor; Radzik, Tomasz 6 2007 Time efficient gossiping in known radio networks. Zbl 1085.68512Gąsieniec, Leszek; Potapov, Igor; Xin, Qin 6 2004 Composition problems for braids. Zbl 1359.68142Potapov, Igor 5 2013 On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups. Zbl 1209.68393Bell, Paul C.; Potapov, Igor 5 2010 Periodic and infinite traces in matrix semigroups. Zbl 1133.03017Bell, Paul; Potapov, Igor 5 2008 From Post systems to the reachability problems for matrix semigroups and multicounter automata. Zbl 1117.03341Potapov, Igor 5 2004 Membership and reachability problems for row-monomial transformations. Zbl 1096.68108Lisitsa, Alexei; Potapov, Igor 5 2004 Deterministic communication in radio networks with large labels. Zbl 1019.90503Gasieniec, Leszek; Pagourtzis, Aris; Potapov, Igor 5 2002 The identity problem for matrix semigroups in \(\mathrm{SL}_2(\mathbb{Z})\) is NP-complete. Zbl 1410.68139Bell, Paul C.; Hirvensalo, Mika; Potapov, Igor 4 2017 Undecidability of two-dimensional robot games. Zbl 1398.91012Niskanen, Reino; Potapov, Igor; Reichert, Julien 4 2016 Mortality for \(2 \times 2\) matrices is NP-hard. Zbl 1365.68265Bell, Paul C.; Hirvensalo, Mika; Potapov, Igor 4 2012 Reachability problems in low-dimensional iterative maps. Zbl 1155.68025Kurganskyy, Oleksiy; Potapov, Igor; Sancho-Caparrini, Fernando 4 2008 On the membership of invertible diagonal and scalar matrices. Zbl 1108.68092Bell, Paul; Potapov, Igor 4 2007 Decidability of the membership problem for \(2\times 2\) integer matrices. Zbl 1410.68245Potapov, Igor; Semukhin, Pavel 3 2017 Vector reachability problem in \(\operatorname{SL}(2,\mathbb{Z})\). Zbl 1404.65037Potapov, Igor; Semukhin, Pavel 3 2016 Time efficient centralized gossiping in radio networks. Zbl 1124.68008Gąsieniec, Leszek; Potapov, Igor; Xin, Qin 3 2007 Space efficient search for maximal repetitions. Zbl 1076.68054Gąsieniec, Leszek; Kolpakov, Roman; Potapov, Igor 3 2005 Time/space efficient compressed pattern matching. Zbl 1030.68071Gąsieniec, Leszek; Potapov, Igor 3 2003 Matrix semigroup freeness problems in \(\mathrm{SL}(2,\mathbb {Z})\). Zbl 1444.20034Ko, Sang-Ki; Potapov, Igor 2 2017 Broadcasting automata and patterns on \(\mathbb{Z}^2\). Zbl 1328.68115Nickson, Thomas; Potapov, Igor 2 2015 “Quorum sensing” generated multistability and chaos in a synthetic genetic oscillator. Zbl 1331.92103Potapov, I.; Zhurov, B.; Volkov, E. 2 2012 Computation in one-dimensional piecewise maps. Zbl 1221.93028Kurganskyy, Oleksiy; Potapov, Igor; Caparrini, Fernando Sancho 2 2007 Lowering undecidability bounds for decision questions in matrices. Zbl 1227.03057Bell, Paul; Potapov, Igor 2 2006 Computation in one-dimensional piecewise maps and planar pseudo-billiard systems. Zbl 1161.68460Kurganskyy, Oleksiy; Potapov, Igor 2 2005 Reachability problems. 11th international workshop, RP 2017, London, UK, September 7–9, 2017. Proceedings. Zbl 1371.68009Hague, Matthew (ed.); Potapov, Igor (ed.) 1 2017 Weighted automata on infinite words in the context of attacker-defender games. Zbl 1371.68150Halava, V.; Harju, T.; Niskanen, R.; Potapov, I. 1 2017 Vector ambiguity and freeness problems in \(\text{SL} (2,\mathbb {Z})\). Zbl 06721531Ko, Sang-Ki; Potapov, Igor 1 2017 Reachability problems. 10th international workshop, RP 2016, Aalborg, Denmark, September 19–21, 2016. Proceedings. Zbl 1371.68012Larsen, Kim Guldstrand (ed.); Potapov, Igor (ed.); Srba, Jiří (ed.) 1 2016 Reachability problems for PAMs. Zbl 1448.37050Kurganskyy, Oleksiy; Potapov, Igor 1 2016 On robot games of degree two. Zbl 1451.68150Halava, Vesa; Niskanen, Reino; Potapov, Igor 1 2015 Reachability problems. 8th international workshop, RP 2014, Oxford, UK, September 22–24, 2014. Proceedings. Zbl 1317.68013Ouaknine, Joël (ed.); Potapov, Igor (ed.); Worrell, James (ed.) 1 2014 Geometric computations by broadcasting automata. Zbl 1332.68265Martin, Russell; Nickson, Thomas; Potapov, Igor 1 2012 Reachability problems. 3rd international workshop, RP 2009, Palaiseau, France, September 23–25, 2009. Proceedings. Zbl 1175.68005Bournez, Olivier (ed.); Potapov, Igor (ed.) 1 2009 On the computational power of querying the history. Zbl 1176.68082Lisitsa, Alexei; Potapov, Igor 1 2009 Automata on Gauss words. Zbl 1234.68225Lisitsa, Alexei; Potapov, Igor; Saleh, Rafiq 1 2009 Reachability problems in quaternion matrix and rotation semigroups. Zbl 1147.03312Bell, Paul; Potapov, Igor 1 2007 On a maximal NFA without mergible states. Zbl 1185.68388Grunsky, Igor; Kurganskyy, Oleksiy; Potapov, Igor 1 2006 Languages representable by vertex-labeled graphs. Zbl 1156.68454Grunsky, Igor; Kurganskyy, Oleksiy; Potapov, Igor 1 2005 On the membership of invertible diagonal matrices. Zbl 1132.03344Bell, Paul; Potapov, Igor 1 2005 Time/space efficient compressed pattern matching. Zbl 0999.68538Gasieniec, Leszek; Potapov, Igor 1 2001 The identity problem for matrix semigroups in \(\mathrm{SL}_2(\mathbb{Z})\) is NP-complete. Zbl 1410.68139Bell, Paul C.; Hirvensalo, Mika; Potapov, Igor 4 2017 Decidability of the membership problem for \(2\times 2\) integer matrices. Zbl 1410.68245Potapov, Igor; Semukhin, Pavel 3 2017 Matrix semigroup freeness problems in \(\mathrm{SL}(2,\mathbb {Z})\). Zbl 1444.20034Ko, Sang-Ki; Potapov, Igor 2 2017 Reachability problems. 11th international workshop, RP 2017, London, UK, September 7–9, 2017. Proceedings. Zbl 1371.68009Hague, Matthew (ed.); Potapov, Igor (ed.) 1 2017 Weighted automata on infinite words in the context of attacker-defender games. Zbl 1371.68150Halava, V.; Harju, T.; Niskanen, R.; Potapov, I. 1 2017 Vector ambiguity and freeness problems in \(\text{SL} (2,\mathbb {Z})\). Zbl 06721531Ko, Sang-Ki; Potapov, Igor 1 2017 Undecidability of two-dimensional robot games. Zbl 1398.91012Niskanen, Reino; Potapov, Igor; Reichert, Julien 4 2016 Vector reachability problem in \(\operatorname{SL}(2,\mathbb{Z})\). Zbl 1404.65037Potapov, Igor; Semukhin, Pavel 3 2016 Reachability problems. 10th international workshop, RP 2016, Aalborg, Denmark, September 19–21, 2016. Proceedings. Zbl 1371.68012Larsen, Kim Guldstrand (ed.); Potapov, Igor (ed.); Srba, Jiří (ed.) 1 2016 Reachability problems for PAMs. Zbl 1448.37050Kurganskyy, Oleksiy; Potapov, Igor 1 2016 Broadcasting automata and patterns on \(\mathbb{Z}^2\). Zbl 1328.68115Nickson, Thomas; Potapov, Igor 2 2015 On robot games of degree two. Zbl 1451.68150Halava, Vesa; Niskanen, Reino; Potapov, Igor 1 2015 Reachability problems. 8th international workshop, RP 2014, Oxford, UK, September 22–24, 2014. Proceedings. Zbl 1317.68013Ouaknine, Joël (ed.); Potapov, Igor (ed.); Worrell, James (ed.) 1 2014 Composition problems for braids. Zbl 1359.68142Potapov, Igor 5 2013 On the computational complexity of matrix semigroup problems. Zbl 1242.68120Bell, Paul C.; Potapov, Igor 7 2012 Mortality for \(2 \times 2\) matrices is NP-hard. Zbl 1365.68265Bell, Paul C.; Hirvensalo, Mika; Potapov, Igor 4 2012 “Quorum sensing” generated multistability and chaos in a synthetic genetic oscillator. Zbl 1331.92103Potapov, I.; Zhurov, B.; Volkov, E. 2 2012 Geometric computations by broadcasting automata. Zbl 1332.68265Martin, Russell; Nickson, Thomas; Potapov, Igor 1 2012 On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups. Zbl 1209.68393Bell, Paul C.; Potapov, Igor 5 2010 Reachability problems. 3rd international workshop, RP 2009, Palaiseau, France, September 23–25, 2009. Proceedings. Zbl 1175.68005Bournez, Olivier (ed.); Potapov, Igor (ed.) 1 2009 On the computational power of querying the history. Zbl 1176.68082Lisitsa, Alexei; Potapov, Igor 1 2009 Automata on Gauss words. Zbl 1234.68225Lisitsa, Alexei; Potapov, Igor; Saleh, Rafiq 1 2009 Reachability problems in quaternion matrix and rotation semigroups. Zbl 1151.03021Bell, Paul; Potapov, Igor 9 2008 Matrix equations and Hilbert’s tenth problem. Zbl 1173.03009Bell, Paul; Halava, Vesa; Harju, Tero; Karhumäki, Juhani; Potapov, Igor 8 2008 On undecidability bounds for matrix decision problems. Zbl 1133.03019Bell, Paul; Potapov, Igor 7 2008 Periodic and infinite traces in matrix semigroups. Zbl 1133.03017Bell, Paul; Potapov, Igor 5 2008 Reachability problems in low-dimensional iterative maps. Zbl 1155.68025Kurganskyy, Oleksiy; Potapov, Igor; Sancho-Caparrini, Fernando 4 2008 Deterministic communication in radio networks with large labels. Zbl 1147.68008Gąsieniec, Leszek; Pagourtzis, Aris; Potapov, Igor; Radzik, Tomasz 6 2007 On the membership of invertible diagonal and scalar matrices. Zbl 1108.68092Bell, Paul; Potapov, Igor 4 2007 Time efficient centralized gossiping in radio networks. Zbl 1124.68008Gąsieniec, Leszek; Potapov, Igor; Xin, Qin 3 2007 Computation in one-dimensional piecewise maps. Zbl 1221.93028Kurganskyy, Oleksiy; Potapov, Igor; Caparrini, Fernando Sancho 2 2007 Reachability problems in quaternion matrix and rotation semigroups. Zbl 1147.03312Bell, Paul; Potapov, Igor 1 2007 Lowering undecidability bounds for decision questions in matrices. Zbl 1227.03057Bell, Paul; Potapov, Igor 2 2006 On a maximal NFA without mergible states. Zbl 1185.68388Grunsky, Igor; Kurganskyy, Oleksiy; Potapov, Igor 1 2006 Space efficient search for maximal repetitions. Zbl 1076.68054Gąsieniec, Leszek; Kolpakov, Roman; Potapov, Igor 3 2005 Computation in one-dimensional piecewise maps and planar pseudo-billiard systems. Zbl 1161.68460Kurganskyy, Oleksiy; Potapov, Igor 2 2005 Languages representable by vertex-labeled graphs. Zbl 1156.68454Grunsky, Igor; Kurganskyy, Oleksiy; Potapov, Igor 1 2005 On the membership of invertible diagonal matrices. Zbl 1132.03344Bell, Paul; Potapov, Igor 1 2005 Time efficient gossiping in known radio networks. Zbl 1085.68512Gąsieniec, Leszek; Potapov, Igor; Xin, Qin 6 2004 From Post systems to the reachability problems for matrix semigroups and multicounter automata. Zbl 1117.03341Potapov, Igor 5 2004 Membership and reachability problems for row-monomial transformations. Zbl 1096.68108Lisitsa, Alexei; Potapov, Igor 5 2004 Time/space efficient compressed pattern matching. Zbl 1030.68071Gąsieniec, Leszek; Potapov, Igor 3 2003 Deterministic communication in radio networks with large labels. Zbl 1019.90503Gasieniec, Leszek; Pagourtzis, Aris; Potapov, Igor 5 2002 Time/space efficient compressed pattern matching. Zbl 0999.68538Gasieniec, Leszek; Potapov, Igor 1 2001 all cited Publications top 5 cited Publications all top 5 Cited by 99 Authors 16 Potapov, Igor 7 Bell, Paul C. 7 Gąsieniec, Leszek Antoni 6 Xin, Qin 5 Halava, Vesa 4 Harju, Tero 3 Honkala, Juha 3 Manne, Fredrik 3 Niskanen, Reino 3 Pelc, Andrzej 2 Bille, Philip 2 Chen, Shang 2 Elsässer, Robert 2 Gorain, Barun 2 Jackson, Lisa A. 2 Ko, Sang-Ki 2 Kolpakov, Roman M. 2 Kowalski, Dariusz R. 2 Peleg, David 2 Semukhin, Pavel 2 Vaya, Shailesh 1 Asarin, Eugene 1 Belazzougui, Djamal 1 Björklund, Johanna 1 Bournez, Olivier 1 Bouyer, Patricia 1 Cassaigne, Julien 1 Charlier, Emilie 1 Chatterjee, Krishnendu 1 Chlebus, Bogdan Stanislaw 1 Cicalese, Ferdinando 1 Claude, Francisco 1 Cunial, Fabio 1 Czumaj, Artur 1 D’angeli, Daniele 1 Dräger, Klaus 1 Esbelin, Henri-Alex 1 Fernau, Henning 1 Feudel, Ulrike 1 Gallagher, John P. 1 Gange, Graeme 1 Gedeon, Tomáš 1 Gørtz, Inge Li 1 Grunsky, Igor 1 Gutan, Marin 1 Hidalgo, Marta R. 1 Hirvensalo, Mika 1 Hofman, Piotr 1 Joan-Arinyo, Robert 1 Kafle, Bishoksan 1 Kantor, Erez 1 Karhumaki, Juhani 1 Kari, Jarkko 1 Kasprzik, Anna 1 Kranakis, Evangelos Konstantinou 1 Kurganskyy, Oleksiy 1 Landau, Gad M. 1 Lohrey, Markus 1 Manuel, Amaldev 1 Markey, Nicolas 1 Matiyasevich, Yuriĭ Vladimirovich 1 Miller, Avery 1 Mysore, Venkatesh P. 1 Nagy, Benedek 1 Navarro, Gonzalo 1 Nicolas, François 1 Pernarowski, Mark 1 Pisarchik, Alexander N. 1 Pnueli, Amir 1 Pryanichnikova, Elena 1 Radzik, Tomasz 1 Raman, Rajeev 1 Ramanujam, Rohit Sunkam 1 Randour, Mickael 1 Reichert, Julien 1 Rodaro, Emanuele 1 Sach, Benjamin 1 Sadakane, Kunihiko 1 Satti, Srinivasa Rao 1 Sauerwald, Thomas 1 Schachte, Peter 1 Schneider, Gerardo 1 Søndergaard, Harald 1 Song, Haomin 1 Stuckey, Peter James 1 Su, Chang 1 Tarasov, Sergey P. 1 Vágvölgyi, Sándor 1 Velner, Yaron 1 Vildhøj, Hjalte Wedel 1 Vyalyi, Mikhail N. 1 Wächter, Jan Philipp 1 Wang, Xin 1 Wang, Xin 1 Weimann, Oren 1 Wilander, Adam 1 Yao, Xiaolan 1 Zhang, Yan 1 Zimmermann, Martín G. all top 5 Cited in 19 Serials 15 Theoretical Computer Science 7 Information and Computation 5 Journal of Computer and System Sciences 3 International Journal of Algebra and Computation 3 Distributed Computing 2 Algorithmica 2 International Journal of Foundations of Computer Science 1 Acta Informatica 1 Discrete Applied Mathematics 1 Information Processing Letters 1 Israel Journal of Mathematics 1 Physics Reports 1 Bulletin of Mathematical Biology 1 SIAM Journal on Computing 1 Journal of Automated Reasoning 1 Theory and Practice of Logic Programming 1 Journal of Discrete Algorithms 1 RAIRO. Theoretical Informatics and Applications 1 Journal of Logical and Algebraic Methods in Programming all top 5 Cited in 15 Fields 48 Computer science (68-XX) 15 Mathematical logic and foundations (03-XX) 11 Group theory and generalizations (20-XX) 6 Linear and multilinear algebra; matrix theory (15-XX) 4 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 3 Combinatorics (05-XX) 3 Number theory (11-XX) 3 Dynamical systems and ergodic theory (37-XX) 3 Operations research, mathematical programming (90-XX) 2 Systems theory; control (93-XX) 2 Information and communication theory, circuits (94-XX) 1 Associative rings and algebras (16-XX) 1 Ordinary differential equations (34-XX) 1 Optics, electromagnetic theory (78-XX) 1 Biology and other natural sciences (92-XX) Citations by Year