Igor Potapov

According to our database, Igor Potapov authored at least 105 papers between 2001 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

The membership problem for subsemigroups of GL2(Z) is NP-complete.

Paul C. Bell, Mika Hirvensalo, Igor Potapov

Inf. Comput., January, 2024

Decidability of Membership Problems for Flat Rational Subsets of \(\boldsymbol{{\textrm{GL}}(2,\boldsymbol{{\mathbb{Q}}})}\) and Singular Matrices.

Volker Diekert, Igor Potapov, Pavel Semukhin

SIAM J. Comput., 2024

Brief Announcement: Collision-Free Robot Scheduling.

Duncan Adamson, Nathan Flaherty, Igor Potapov, Paul G. Spirakis

Proceedings of the 3rd Symposium on Algorithmic Foundations of Dynamic Networks, 2024

Reachability in Linear Recurrence Automata.

Mika Hirvensalo, Akitoshi Kawamura, Igor Potapov, Takao Yuyama

Proceedings of the Reachability Problems - 18th International Conference, 2024

Structural and Combinatorial Properties of 2-Swap Word Permutation Graphs.

Duncan Adamson, Nathan Flaherty, Igor Potapov, Paul G. Spirakis

Proceedings of the LATIN 2024: Theoretical Informatics, 2024

Collision-Free Robot Scheduling.

Duncan Adamson, Nathan Flaherty, Igor Potapov, Paul G. Spirakis

Proceedings of the Algorithmics of Wireless Networks - 20th International Symposium, 2024

2023

Distributed transformations of Hamiltonian shapes based on line moves.

Abdullah Almethen, Othon Michail, Igor Potapov

Theor. Comput. Sci., 2023

Optimality guarantees for crystal structure prediction.

Vladimir V. Gusev, Duncan Adamson, Argyrios Deligkas, Dmytro Antypov, Christopher M. Collins, Piotr Krysta, Igor Potapov, George R. Darling, Matthew S. Dyer, Paul G. Spirakis, Matthew J. Rosseinsky

Nat., 2023

Integer Weighted Automata on Infinite Words.

Vesa Halava, Tero Harju, Reino Niskanen, Igor Potapov

Int. J. Found. Comput. Sci., 2023

The Maximum Cover with Rotating Field of View.

Igor Potapov, Jason F. Ralph, Theofilos Triommatis

CoRR, 2023

The k-Centre Problem for Classes of Cyclic Words.

Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, Igor Potapov

Proceedings of the SOFSEM 2023: Theory and Practice of Computer Science, 2023

On the Identity and Group Problems for Complex Heisenberg Matrices.

Paul C. Bell, Reino Niskanen, Igor Potapov, Pavel Semukhin

Proceedings of the Reachability Problems - 17th International Conference, 2023

2022

Centralised connectivity-preserving transformations for programmable matter: A minimal seed approach.

Matthew Connor, Othon Michail, Igor Potapov

Theor. Comput. Sci., 2022

On efficient connectivity-preserving transformations in a grid.

Abdullah Almethen, Othon Michail, Igor Potapov

Theor. Comput. Sci., 2022

Optimizing reachability sets in temporal graphs by delaying.

Argyrios Deligkas, Igor Potapov

Inf. Comput., 2022

Preface.

Paul C. Bell, Igor Potapov, Sylvain Schmitz, Patrick Totzke

Fundam. Informaticae, 2022

Towards Uniform Online Spherical Tessellations.

Paul C. Bell, Igor Potapov

Discret. Comput. Geom., 2022

The Complexity of Periodic Energy Minimisation.

Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, Igor Potapov

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

A Geometric Approach to Passive Localisation.

Theofilos Triommatis, Igor Potapov, Gareth Rees, Jason F. Ralph

Proceedings of the 25th International Conference on Information Fusion, 2022

2021

Reachability problems in low-dimensional nondeterministic polynomial maps over integers.

Sang-Ki Ko, Reino Niskanen, Igor Potapov

Inf. Comput., 2021

Preface.

Mikolaj Bojanczyk, Thomas Brihaye, Christoph Haase, Slawomir Lasota, Joël Ouaknine, Igor Potapov

Inf. Comput., 2021

On the mortality problem: From multiplicative matrix equations to linear recurrence sequences and beyond.

Paul C. Bell, Igor Potapov, Pavel Semukhin

Inf. Comput., 2021

Preface.

Matthew Hague, Igor Potapov

Fundam. Informaticae, 2021

On the Hardness of Energy Minimisation for Crystal Structure Prediction.

Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, Igor Potapov

Fundam. Informaticae, 2021

The k-Centre Selection Problem for Multidimensional Necklaces.

Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, Igor Potapov

CoRR, 2021

Ranking Bracelets in Polynomial Time.

Duncan Adamson, Vladimir V. Gusev, Igor Potapov, Argyrios Deligkas

Proceedings of the 32nd Annual Symposium on Combinatorial Pattern Matching, 2021

2020

Pushing lines helps: Efficient universal centralised transformations for programmable matter.

Abdullah Almethen, Othon Michail, Igor Potapov

Theor. Comput. Sci., 2020

On decidability and complexity of low-dimensional robot games.

Reino Niskanen, Igor Potapov, Julien Reichert

J. Comput. Syst. Sci., 2020

The K-Centre Problem for Necklaces.

Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, Igor Potapov

CoRR, 2020

Decidability of membership problems for flat rational subsets of GL(2, Q) and singular matrices.

Volker Diekert, Igor Potapov, Pavel Semukhin

Proceedings of the ISSAC '20: International Symposium on Symbolic and Algebraic Computation, 2020

2019

Vector and scalar reachability problems in SL(2, Z).

Igor Potapov, Pavel Semukhin

J. Comput. Syst. Sci., 2019

Decidability of the Mortality Problem: from multiplicative matrix equations to linear recurrence sequences and beyond.

Paul C. Bell, Igor Potapov, Pavel Semukhin

CoRR, 2019

Polygon Approximations of the Euclidean Circles on the Square Grid by Broadcasting Sequences.

Haomin Song, Igor Potapov

Proceedings of the Discrete Geometry for Computer Imagery, 2019

2018

Reachability Problems 2014: Special issue.

Joël Ouaknine, Igor Potapov, James Worrell

Theor. Comput. Sci., 2018

Reachability problems: Special issue.

Kim G. Larsen, Igor Potapov, Jirí Srba

Theor. Comput. Sci., 2018

Preface.

Igor Potapov, Pavel Semukhin

Int. J. Found. Comput. Sci., 2018

Reachability Problems for One-Dimensional Piecewise Affine Maps.

Olivier Bournez, Oleksiy Kurganskyy, Igor Potapov

Int. J. Found. Comput. Sci., 2018

Vector Ambiguity and Freeness Problems in SL(2, ℤ).

Sang-Ki Ko, Igor Potapov

Fundam. Informaticae, 2018

De Bruijn graphs and powers of 3/2.

Oleksiy Kurganskyy, Igor Potapov

CoRR, 2018

On the Identity Problem for the Special Linear Group and the Heisenberg Group.

Sang-Ki Ko, Reino Niskanen, Igor Potapov

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Reachability Problems in Nondeterministic Polynomial Maps on the Integers.

Sang-Ki Ko, Reino Niskanen, Igor Potapov

Proceedings of the Developments in Language Theory - 22nd International Conference, 2018

2017

Weighted automata on infinite words in the context of Attacker-Defender games.

Vesa Halava, Tero Harju, Reino Niskanen, Igor Potapov

Inf. Comput., 2017

Composition problems for braids: Membership, Identity and Freeness.

Sang-Ki Ko, Igor Potapov

CoRR, 2017

Matrix Semigroup Freeness Problems in SL (2, \mathbb Z).

Sang-Ki Ko, Igor Potapov

Proceedings of the SOFSEM 2017: Theory and Practice of Computer Science, 2017

Decidability of the Membership Problem for 2 × 2 integer matrices.

Igor Potapov, Pavel Semukhin

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

The Identity Problem for Matrix Semigroups in SL₂(ℤ) is NP-complete.

Paul C. Bell, Mika Hirvensalo, Igor Potapov

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Membership Problem in GL(2, Z) Extended by Singular Matrices.

Igor Potapov, Pavel Semukhin

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

2016

Preface.

Parosh Aziz Abdulla, Stéphane Demri, Alain Finkel, Jérôme Leroux, Igor Potapov

Fundam. Informaticae, 2016

Matrix Semigroup Freeness Problems in SL(2,Z).

Sang-Ki Ko, Igor Potapov

CoRR, 2016

Reachability Problems for PAMs.

Oleksiy Kurganskyy, Igor Potapov

Proceedings of the SOFSEM 2016: Theory and Practice of Computer Science, 2016

Insertion-Deletion Systems over Relational Words.

Igor Potapov, Olena Prianychnykova, Sergey Verlan

Proceedings of the Reachability Problems - 10th International Workshop, 2016

Pattern formations with broadcasting automata model.

Igor Potapov

Proceedings of the Eighth Workshop on Non-Classical Models of Automata and Applications, 2016

Vector Reachability Problem in SL(2, Z).

Igor Potapov, Pavel Semukhin

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Undecidability of Two-dimensional Robot Games.

Reino Niskanen, Igor Potapov, Julien Reichert

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015

On Robot Games of Degree Two.

Vesa Halava, Reino Niskanen, Igor Potapov

Proceedings of the Language and Automata Theory and Applications, 2015

2014

Broadcasting Automata and Patterns on Z^2.

Thomas Nickson, Igor Potapov

CoRR, 2014

On Undecidability of Counter Reachability Games in Dimension One.

Vesa Halava, Reino Niskanen, Igor Potapov

CoRR, 2014

2013

Preface.

Giorgio Delzanno, Igor Potapov

Int. J. Found. Comput. Sci., 2013

Preface.

Agata Ciabattoni, Rusins Freivalds, Antonín Kucera, Igor Potapov, Stefan Szeider

Fundam. Informaticae, 2013

Composition Problems for Braids.

Igor Potapov

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013

2012

On algebra of languages representable by vertex-labeled graphs.

Igor Grunsky, Igor Potapov, Elena Pryanichnikova

Theor. Comput. Sci., 2012

Geometric computations by broadcasting automata.

Russell Martin, Thomas Nickson, Igor Potapov

Nat. Comput., 2012

On the Computational Complexity of Matrix Semigroup Problems.

Paul C. Bell, Igor Potapov

Fundam. Informaticae, 2012

Discrete Discs and Broadcasting Sequences.

Thomas Nickson, Igor Potapov

Proceedings of the Unconventional Computation and Natural Computation, 2012

Mortality for 2×2 Matrices Is NP-Hard.

Paul C. Bell, Mika Hirvensalo, Igor Potapov

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

2011

Preface.

Olivier Bournez, Igor Potapov

Int. J. Found. Comput. Sci., 2011

Geometric Computations by Broadcasting Automata on the Integer Grid.

Russell Martin, Thomas Nickson, Igor Potapov

Proceedings of the Unconventional Computation - 10th International Conference, 2011

Planarity of Knots, Register Automata and LogSpace Computability.

Alexei Lisitsa, Igor Potapov, Rafiq Saleh

Proceedings of the Language and Automata Theory and Applications, 2011

2010

On decision problems for parameterized machines.

Oscar H. Ibarra, Igor Potapov, Hsu-Chun Yen

Theor. Comput. Sci., 2010

On the Undecidability of the Identity Correspondence Problem and its Applications for Word and Matrix Semigroups.

Paul C. Bell, Igor Potapov

Int. J. Found. Comput. Sci., 2010

A measure of state transition of collective of stateless automata in discrete environment

Oleksiy Kurganskyy, Igor Potapov

CoRR, 2010

2009

On the Computational Power of Querying the History.

Alexei Lisitsa, Igor Potapov

Fundam. Informaticae, 2009

On Descriptional Complexity of the Planarity Problem for Gauss Words

Vitaliy Kurlin, Alexei Lisitsa, Igor Potapov, Rafiq Saleh

CoRR, 2009

Automata on Gauss Words.

Alexei Lisitsa, Igor Potapov, Rafiq Saleh

Proceedings of the Language and Automata Theory and Applications, 2009

The Identity Correspondence Problem and Its Applications.

Paul Bell, Igor Potapov

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

2008

On undecidability bounds for matrix decision problems.

Paul Bell, Igor Potapov

Theor. Comput. Sci., 2008

Reachability Problems in Low-Dimensional Iterative Maps.

Oleksiy Kurganskyy, Igor Potapov, Fernando Sancho-Caparrini

Int. J. Found. Comput. Sci., 2008

Preface.

Vesa Halava, Igor Potapov

Int. J. Found. Comput. Sci., 2008

Matrix Equations and Hilbert's Tenth Problem.

Paul Bell, Vesa Halava, Tero Harju, Juhani Karhumäki, Igor Potapov

Int. J. Algebra Comput., 2008

Reachability problems in quaternion matrix and rotation semigroups.

Paul Bell, Igor Potapov

Inf. Comput., 2008

Periodic and Infinite Traces in Matrix Semigroups.

Paul Bell, Igor Potapov

Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

2007

Time efficient centralized gossiping in radio networks.

Leszek Gasieniec, Igor Potapov, Qin Xin

Theor. Comput. Sci., 2007

On the membership of invertible diagonal and scalar matrices.

Paul Bell, Igor Potapov

Theor. Comput. Sci., 2007

Deterministic Communication in Radio Networks with Large Labels.

Leszek Gasieniec, Aris Pagourtzis, Igor Potapov, Tomasz Radzik

Algorithmica, 2007

Computation in One-Dimensional Piecewise Maps.

Oleksiy Kurganskyy, Igor Potapov, Fernando Sancho-Caparrini

Proceedings of the Hybrid Systems: Computation and Control, 10th International Workshop, 2007

2006

In time alone: on the computational power of querying the history.

Alexei Lisitsa, Igor Potapov

Proceedings of the 13th International Symposium on Temporal Representation and Reasoning (TIME 2006), 2006

Lowering Undecidability Bounds for Decision Questions in Matrices.

Paul Bell, Igor Potapov

Proceedings of the Developments in Language Theory, 10th International Conference, 2006

On a Maximal NFA Without Mergible States.

Igor Grunsky, Oleksiy Kurganskyy, Igor Potapov

Proceedings of the Computer Science, 2006

2005

Space efficient search for maximal repetitions.

Leszek Gasieniec, Roman M. Kolpakov, Igor Potapov

Theor. Comput. Sci., 2005

Computation in One-Dimensional Piecewise Maps and Planar Pseudo-Billiard Systems.

Oleksiy Kurganskyy, Igor Potapov

Proceedings of the Unconventional Computation, 4th International Conference, 2005

Temporal Logic with Predicate lambda-Abstraction.

Alexei Lisitsa, Igor Potapov

Proceedings of the 12th International Symposium on Temporal Representation and Reasoning (TIME 2005), 2005

Languages Representable by Vertex-Labeled Graphs.

Igor Grunsky, Oleksiy Kurganskyy, Igor Potapov

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

On the Membership of Invertible Diagonal Matrices.

Paul Bell, Igor Potapov

Proceedings of the Developments in Language Theory, 9th International Conference, 2005

Real-Time Traversal in Grammar-Based Compressed Files.

Leszek Gasieniec, Roman M. Kolpakov, Igor Potapov, Paul Sant

Proceedings of the 2005 Data Compression Conference (DCC 2005), 2005

2004

Temporal logic with predicate abstraction

Alexei Lisitsa, Igor Potapov

CoRR, 2004

Time Efficient Gossiping in Known Radio Networks.

Leszek Gasieniec, Igor Potapov, Qin Xin

Proceedings of the Structural Information and Communication Complexity, 2004

Membership and Reachability Problems for Row-Monomial Transformations.

Alexei Lisitsa, Igor Potapov

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

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

Igor Potapov

Proceedings of the Developments in Language Theory, 2004

On the Computation Power of Finite Automata in Two-dimensional Environments.

Oleksiy Kurganskyy, Igor Potapov

Proceedings of the Developments in Language Theory, 2004

2003

Time/Space Efficient Compressed Pattern Matching.

Leszek Gasieniec, Igor Potapov

Fundam. Informaticae, 2003

Coarse-Grained Parallel Transitive Closure Algorithm: Path Decomposition Technique.

Alan Gibbons, Aris Pagourtzis, Igor Potapov, Wojciech Rytter

Comput. J., 2003

2002

Observations on Parallel Computation of Transitive and Max-Closure Problems.

Aris Pagourtzis, Igor Potapov, Wojciech Rytter

Proceedings of the Recent Advances in Parallel Virtual Machine and Message Passing Interface, 9th European PVM/MPI Users' Group Meeting, Linz, Austria, September 29, 2002

Gossiping with Unit Messages in Known Radio Networks.

Leszek Gasieniec, Igor Potapov

Proceedings of the Foundations of Information Technology in the Era of Networking and Mobile Computing, 2002

Deterministic Communication in Radio Networks with Large Labels.

Leszek Gasieniec, Aris Pagourtzis, Igor Potapov

Proceedings of the Algorithms, 2002

2001

PVM Computation of the Transitive Closure: The Dependency Graph Approach.

Aris Pagourtzis, Igor Potapov, Wojciech Rytter

Proceedings of the Recent Advances in Parallel Virtual Machine and Message Passing Interface, 2001