Publications

Editorial work:

Agata Ciabattoni, R. Freivalds, A. Kucera, I. Potapov and S. Szeider. MFCS and CSL 2010 Satellite Workshops: Selected Papers.

Fundamenta Informaticae 123, IOS Press, 2013

Alain Finkel, Jerome Leroux, Igor Potapov (Eds.): Reachability Problems - 6th International Workshop, RP 2012,

Bordeaux, France, September 17-19, 2012. LNCS Proceedings Springer 7550, 2012

Giorgio Delzanno, Igor Potapov: Reachability Problems - 5th International Workshop, RP 2011,

Genoa, Italy, September 28-30, 2011. LNCS Proceedings Springer 2011

Olivier Bournez, Igor Potapov: International Journal of Foundations of Computer Science, 22(4): (2011)

Antonin Kucera, Igor Potapov: Reachability Problems, 4th International Workshop, RP 2010,

Brno, Czech Republic, August 28-29, 2010. LNCS Proceedings Springer 2010

Olivier Bournez, Igor Potapov: Reachability Problems, 3rd International Workshop, RP 2009,

Palaiseau, France, September 23-25, 2009. LNCS Proceedings Springer 2009

Vesa Halava, Igor Potapov: International Journal of Foundations of Computer Science, 20(5): (2009)

Vesa Halava, Igor Potapov: Electr. Notes Theor. Comput. Sci. 223: (2008)

Vesa Halava, Igor Potapov: International Journal of Foundations of Computer Science, 19(4) PART 2: (2008)

To appear

Giorgio Delzanno, Igor Potapov. Special issue of International Journal of Foundations of Computer Science, xx(x), (2013)

2012

P. C. Bell and I. Potapov. On the computational complexity of matrix semigroup problems.

Fundamenta Informaticae 116(1-4): 1-13 (2012).

Igor Grunsky, Igor Potapov and Elena Pryanichnikova. On algebra of languages representable by vertex-labeled graphs,

Theoretical Computer Science, doi:10.1016/j.tcs.2011.08.034

Russell Martin, Thomas Nickson, Igor Potapov: Geometric computations by broadcasting automata.

Natural Computing 11(4): 623-635 (2012)

Paul C. Bell, Mika Hirvensalo, Igor Potapov: Mortality for 2x2 Matrices Is NP-Hard. MFCS 2012: 148-159

Thomas Nickson, Igor Potapov: Discrete Discs and Broadcasting Sequences. UCNC 2012: 235

2011

Alexei Lisitsa, Igor Potapov, and Rafiq Saleh. Planarity of Knots, Register Automata and LogSpace Computability,

Language and Automata Theory and Applications, LATA 2011

Russell Martin, Thomas Nickson and Igor Potapov. Geometric Computations by Broadcasting Automata on the Integer Grid.

Unconventional Computation, UC 2011

2010

Paul Bell, Igor Potapov: On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups,

International Journal of Foundations of Computer Science (IJFCS), Volume: 21, Issue: 6,963-9

Oleksiy Kurganskyy, Igor Potapov: A measure of state transition of collective of stateless automata in discrete environment CoRR abs/1007.2353: (2010)

Oscar H. Ibarra, Igor Potapov, Hsu-Chun Yen: On decision problems for parameterized machines. Theor. Comput. Sci. 411(7-9): 1192-1201 (2010)

2009

Paul Bell, Igor Potapov: The Identity Correspondence Problem and Its Applications. ISAAC 2009: 657-667

Alexei Lisitsa, Igor Potapov, Rafiq Saleh: Automata on Gauss Words. LATA 2009: 505-517

Vitaliy Kurlin, Alexei Lisitsa, Igor Potapov, Rafiq Saleh: On Descriptional Complexity of the Planarity Problem for Gauss Words CoRR abs/0907.4180: (20

Alexei Lisitsa, Igor Potapov: On the Computational Power of Querying the History. Fundam. Inform. 91(2): 395-409 (2009)

2008

Paul Bell, Igor Potapov: Periodic and Infinite Traces in Matrix Semigroups. SOFSEM 2008: 148-161

Paul Bell, Vesa Halava, Tero Harju, Juhani Karhumaki, Igor Potapov: Matrix Equations and Hilbert's Tenth Problem. IJAC 18(8): 1231-1241 (2008)

Paul Bell, Igor Potapov: Reachability problems in quaternion matrix and rotation semigroups. Inf. Comput. 206(11): 1353-1361 (2008)

Paul Bell, Igor Potapov: On undecidability bounds for matrix decision problems. Theor. Comput. Sci. 391(1-2): 3-13 (2008)

Oleksiy Kurganskyy, Igor Potapov, Fernando Sancho-Caparrini: Reachability Problems in Low-Dimensional Iterative Maps. Int. J. Found. Comput. Sci. 19(4): 935-951 (2008)

2007

Oleksiy Kurganskyy, Igor Potapov, Fernando Sancho-Caparrini: Computation in One-Dimensional Piecewise Maps. HSCC 2007: 706-709

Paul Bell, Igor Potapov: Reachability Problems in Quaternion Matrix and Rotation Semigroups. MFCS 2007: 346-358

Leszek Gasieniec, Aris Pagourtzis, Igor Potapov, Tomasz Radzik: Deterministic Communication in Radio Networks with Large Labels.

Algorithmica 47(1): 97-117 (2007)

Paul Bell, Igor Potapov: On the membership of invertible diagonal and scalar matrices. Theor. Comput. Sci. 372(1): 37-45 (2007)

Leszek Gasieniec, Igor Potapov, Qin Xin: Time efficient centralized gossiping in radio networks. Theor. Comput. Sci. 383(1): 45-58 (2007)

2006

Igor Grunsky, Oleksiy Kurganskyy, Igor Potapov: On a Maximal NFA Without Mergible States. CSR 2006: 202-210

Paul Bell, Igor Potapov: Lowering Undecidability Bounds for Decision Questions in Matrices. Developments in Language Theory 2006: 375-385

Alexei Lisitsa, Igor Potapov: In time alone: on the computational power of querying the history. TIME 2006: 42-49

2005

Leszek Gasieniec, Roman M. Kolpakov, Igor Potapov, Paul Sant: Real-Time Traversal in Grammar-Based Compressed Files. DCC 2005: 458

Paul Bell, Igor Potapov: On the Membership of Invertible Diagonal Matrices. Developments in Language Theory 2005: 146-157

Igor Grunsky, Oleksiy Kurganskyy, Igor Potapov Languages Representable by Vertex-Labeled Graphs. MFCS 2005: 435-446

Alexei Lisitsa, Igor Potapov: Temporal Logic with Predicate lambda-Abstraction. TIME 2005: 147-155

Oleksiy Kurganskyy, Igor Potapov: Computation in One-Dimensional Piecewise Maps and Planar Pseudo-Billiard Systems. UC 2005: 169-175

Leszek Gasieniec, Roman M. Kolpakov, Igor Potapov: Space efficient search for maximal repetitions. Theor. Comput. Sci. 339(1): 35-48 (2005)

2004

Oleksiy Kurganskyy, Igor Potapov: On the Computation Power of Finite Automata in Two-dimensional Environments.

Developments in Language Theory 2004: 261-271

Igor Potapov: From Post Systems to the Reachability Problems for Matrix Semigroups and Multicounter Automata.

Developments in Language Theory 2004: 345-356

Alexei Lisitsa, Igor Potapov: Membership and Reachability Problems for Row-Monomial Transformations. MFCS 2004: 623-634

Leszek Gasieniec, Igor Potapov, Qin Xin: Time Efficient Gossiping in Known Radio Networks. SIROCCO 2004: 173-184

Alexei Lisitsa, Igor Potapov: Temporal logic with predicate abstraction CoRR cs.LO/0410072: (2004)

2003

Alan Gibbons, Aris Pagourtzis, Igor Potapov, Wojciech Rytter: Coarse-Grained Parallel Transitive Closure Algorithm: Path Decomposition Technique.

Comput. J. 46(4): 391-400 (2003)

Leszek Gasieniec, Igor Potapov: Time/Space Efficient Compressed Pattern Matching. Fundam. Inform. 56(1-2): 137-154 (2003)

L.Gasieniec, R.Kolpakov, and I.Potapov. Space efficient search for maximal repetitions. Proceedings of 4th International Conference on Words

Turku: Turku Centre for Computer Science. TUCS General Publication. 27, 269-281 (2003)

2002

Leszek Gasieniec, Aris Pagourtzis, Igor Potapov: Deterministic Communication in Radio Networks with Large Labels. ESA 2002: 512-524

Leszek Gasieniec, Igor Potapov: Gossiping with Unit Messages in Known Radio Networks. IFIP TCS 2002: 193-205

Aris Pagourtzis, Igor Potapov, Wojciech Rytter: Observations on Parallel Computation of Transitive and Max-Closure Problems. PVM/MPI 2002: 217-225

2001

Leszek Gasieniec, Igor Potapov: Time/Space Efficient Compressed Pattern Matching. FCT 2001: 138-149

Aris Pagourtzis, Igor Potapov, Wojciech Rytter: PVM Computation of the Transitive Closure: The Dependency Graph Approach. PVM/MPI 2001: 249-256

1998- 2000

Igor Potapov "Logical analysis of network protocols on the basis of CFSMs model" // PhD Thesis.

Institute of Applied Mathematics and Mechanics of NAS of Ukraine, Donetsk, Ukraine - 2000

I.G. Potapov, "Characteristic of definable communication systems" // Proceedings of the Institute of Applied Mathematics

and Mechanics of NAS of Ukraine, Vol. 4, 1999. p. 134-141.

A. N. Kurganskii and I. G. Potapov. On the bound of algorithmic resolvability of correctness problems of automaton interaction through communication channels. Cybernetics and System Analysis, Kiev, Ukraine, Volume 35, Number 3, May, 1999, p. 49-57

I.G. Potapov, "On decidability of the correctness problems for a net of communicating finite state machines", Modeling Continuous and Discrete Systems, Vol. 2, Proceedings of the Institute of Applied Mathematics and Mechanics of NAS of Ukraine, September 1998 - p. 128-135.