We stand with Ukraine

We stand with Ukraine

Igor Potapov

Orcid: 0000-0002-7192-7853

Affiliations:

University of Liverpool, UK

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

Collaborative distances:

Dijkstra number² of three.
Erdős number³ of three.

Timeline

Legend:

Book

In proceedings

Article

PhD thesis

Dataset

Other

Links

Online presence:

on orcid.org
on csc.liv.ac.uk

On csauthors.net:

Bibliography

2024

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

[BibT_eX]

[DOI]

,

Mika Hirvensalo

,

Inf. Comput., January, 2024

Collision-Free Robot Scheduling.

[BibT_eX]

[DOI]

,

Nathan Flaherty

,

,

Paul G. Spirakis

CoRR, 2024

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

[BibT_eX]

[DOI]

,

Nathan Flaherty

,

,

Paul G. Spirakis

Proceedings of the LATIN 2024: Theoretical Informatics, 2024

2023

Distributed transformations of Hamiltonian shapes based on line moves.

[BibT_eX]

[DOI]

Abdullah Almethen

,

,

Theor. Comput. Sci., 2023

Optimality guarantees for crystal structure prediction.

[BibT_eX]

[DOI]

Vladimir V. Gusev

,

,

Argyrios Deligkas

,

,

Christopher M. Collins

,

,

,

George R. Darling

,

Matthew S. Dyer

,

Paul G. Spirakis

,

Matthew J. Rosseinsky

Nat., 2023

Integer Weighted Automata on Infinite Words.

[BibT_eX]

[DOI]

,

,

,

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

The Maximum Cover with Rotating Field of View.

[BibT_eX]

[DOI]

,

,

Theofilos Triommatis

CoRR, 2023

The k-Centre Problem for Classes of Cyclic Words.

[BibT_eX]

[DOI]

,

Argyrios Deligkas

,

Vladimir V. Gusev

,

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

On the Identity and Group Problems for Complex Heisenberg Matrices.

[BibT_eX]

[DOI]

,

,

,

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

2022

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

[BibT_eX]

[DOI]

,

,

Theor. Comput. Sci., 2022

On efficient connectivity-preserving transformations in a grid.

[BibT_eX]

[DOI]

Abdullah Almethen

,

,

Theor. Comput. Sci., 2022

Optimizing reachability sets in temporal graphs by delaying.

[BibT_eX]

[DOI]

Argyrios Deligkas

,

Inf. Comput., 2022

Preface.

[BibT_eX]

[DOI]

,

,

Sylvain Schmitz

,

Fundam. Informaticae, 2022

Towards Uniform Online Spherical Tessellations.

[BibT_eX]

[DOI]

,

Discret. Comput. Geom., 2022

The Complexity of Periodic Energy Minimisation.

[BibT_eX]

[DOI]

,

Argyrios Deligkas

,

Vladimir V. Gusev

,

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

A Geometric Approach to Passive Localisation.

[BibT_eX]

[DOI]

Theofilos Triommatis

,

,

,

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

2021

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

[BibT_eX]

[DOI]

,

,

Inf. Comput., 2021

Preface.

[BibT_eX]

[DOI]

Mikolaj Bojanczyk

,

,

Christoph Haase

,

Slawomir Lasota

,

,

Inf. Comput., 2021

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

[BibT_eX]

[DOI]

,

,

Inf. Comput., 2021

Preface.

[BibT_eX]

[DOI]

,

Fundam. Informaticae, 2021

On the Hardness of Energy Minimisation for Crystal Structure Prediction.

[BibT_eX]

[DOI]

,

Argyrios Deligkas

,

Vladimir V. Gusev

,

Fundam. Informaticae, 2021

The k-Centre Selection Problem for Multidimensional Necklaces.

[BibT_eX]

[DOI]

,

Argyrios Deligkas

,

Vladimir V. Gusev

,

CoRR, 2021

Ranking Bracelets in Polynomial Time.

[BibT_eX]

[DOI]

,

Vladimir V. Gusev

,

,

Argyrios Deligkas

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

2020

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

[BibT_eX]

[DOI]

Abdullah Almethen

,

,

Theor. Comput. Sci., 2020

On decidability and complexity of low-dimensional robot games.

[BibT_eX]

[DOI]

,

,

Julien Reichert

J. Comput. Syst. Sci., 2020

The K-Centre Problem for Necklaces.

[BibT_eX]

[DOI]

,

Argyrios Deligkas

,

Vladimir V. Gusev

,

CoRR, 2020

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

[BibT_eX]

[DOI]

,

,

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

2019

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

[BibT_eX]

[DOI]

,

J. Comput. Syst. Sci., 2019

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

[BibT_eX]

[DOI]

,

,

CoRR, 2019

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

[BibT_eX]

[DOI]

,

Proceedings of the Discrete Geometry for Computer Imagery, 2019

2018

Reachability Problems 2014: Special issue.

[BibT_eX]

[DOI]

,

,

Theor. Comput. Sci., 2018

Reachability problems: Special issue.

[BibT_eX]

[DOI]

,

,

Theor. Comput. Sci., 2018

Preface.

[BibT_eX]

[DOI]

,

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

Reachability Problems for One-Dimensional Piecewise Affine Maps.

[BibT_eX]

[DOI]

Olivier Bournez

,

Oleksiy Kurganskyy

,

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

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

[BibT_eX]

[DOI]

,

Fundam. Informaticae, 2018

De Bruijn graphs and powers of 3/2.

[BibT_eX]

[DOI]

Oleksiy Kurganskyy

,

CoRR, 2018

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

[BibT_eX]

[DOI]

,

,

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

Reachability Problems in Nondeterministic Polynomial Maps on the Integers.

[BibT_eX]

[DOI]

,

,

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

2017

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

[BibT_eX]

[DOI]

,

,

,

Inf. Comput., 2017

Composition problems for braids: Membership, Identity and Freeness.

[BibT_eX]

[DOI]

,

CoRR, 2017

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

[BibT_eX]

[DOI]

,

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

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

[BibT_eX]

[DOI]

,

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

The Identity Problem for Matrix Semigroups in SL<sub>2</sub>(ℤ) is NP-complete.

[BibT_eX]

[DOI]

,

Mika Hirvensalo

,

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

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

[BibT_eX]

[DOI]

,

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

2016

Preface.

[BibT_eX]

[DOI]

Parosh Aziz Abdulla

,

Stéphane Demri

,

,

Jérôme Leroux

,

Fundam. Informaticae, 2016

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

[BibT_eX]

[DOI]

,

CoRR, 2016

Reachability Problems for PAMs.

[BibT_eX]

[DOI]

Oleksiy Kurganskyy

,

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

Insertion-Deletion Systems over Relational Words.

[BibT_eX]

[DOI]

,

Olena Prianychnykova

,

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

Pattern formations with broadcasting automata model.

[BibT_eX]

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

Vector Reachability Problem in SL(2, Z).

[BibT_eX]

[DOI]

,

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

Undecidability of Two-dimensional Robot Games.

[BibT_eX]

[DOI]

,

,

Julien Reichert

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

2015

On Robot Games of Degree Two.

[BibT_eX]

[DOI]

,

,

Proceedings of the Language and Automata Theory and Applications, 2015

2014

Broadcasting Automata and Patterns on Z^2.

[BibT_eX]

[DOI]

,

CoRR, 2014

On Undecidability of Counter Reachability Games in Dimension One.

[BibT_eX]

[DOI]

,

,

CoRR, 2014

2013

Preface.

[BibT_eX]

[DOI]

Giorgio Delzanno

,

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

Preface.

[BibT_eX]

[DOI]

Agata Ciabattoni

,

Rusins Freivalds

,

Antonín Kucera

,

,

Fundam. Informaticae, 2013

Composition Problems for Braids.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

,

,

Elena Pryanichnikova

Theor. Comput. Sci., 2012

Geometric computations by broadcasting automata.

[BibT_eX]

[DOI]

,

,

Nat. Comput., 2012

On the Computational Complexity of Matrix Semigroup Problems.

[BibT_eX]

[DOI]

,

Fundam. Informaticae, 2012

Discrete Discs and Broadcasting Sequences.

[BibT_eX]

[DOI]

,

Proceedings of the Unconventional Computation and Natural Computation, 2012

Mortality for 2×2 Matrices Is NP-Hard.

[BibT_eX]

[DOI]

,

Mika Hirvensalo

,

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

2011

Preface.

[BibT_eX]

[DOI]

Olivier Bournez

,

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

Geometric Computations by Broadcasting Automata on the Integer Grid.

[BibT_eX]

[DOI]

,

,

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

Planarity of Knots, Register Automata and LogSpace Computability.

[BibT_eX]

[DOI]

,

,

Proceedings of the Language and Automata Theory and Applications, 2011

2010

On decision problems for parameterized machines.

[BibT_eX]

[DOI]

Oscar H. Ibarra

,

,

Theor. Comput. Sci., 2010

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

[BibT_eX]

[DOI]

,

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

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

[BibT_eX]

[DOI]

Oleksiy Kurganskyy

,

CoRR, 2010

2009

On the Computational Power of Querying the History.

[BibT_eX]

[DOI]

,

Fundam. Informaticae, 2009

On Descriptional Complexity of the Planarity Problem for Gauss Words

[BibT_eX]

[DOI]

,

,

,

CoRR, 2009

Automata on Gauss Words.

[BibT_eX]

[DOI]

,

,

Proceedings of the Language and Automata Theory and Applications, 2009

The Identity Correspondence Problem and Its Applications.

[BibT_eX]

[DOI]

,

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

2008

On undecidability bounds for matrix decision problems.

[BibT_eX]

[DOI]

,

Theor. Comput. Sci., 2008

Reachability Problems in Low-Dimensional Iterative Maps.

[BibT_eX]

[DOI]

Oleksiy Kurganskyy

,

,

Fernando Sancho-Caparrini

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

Matrix Equations and Hilbert's Tenth Problem.

[BibT_eX]

[DOI]

,

,

,

Juhani Karhumäki

,

Int. J. Algebra Comput., 2008

Reachability problems in quaternion matrix and rotation semigroups.

[BibT_eX]

[DOI]

,

Inf. Comput., 2008

Preface.

[BibT_eX]

[DOI]

,

Proceedings of the Second Workshop on Reachability Problems in Computational Models, 2008

Periodic and Infinite Traces in Matrix Semigroups.

[BibT_eX]

[DOI]

,

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

2007

Time efficient centralized gossiping in radio networks.

[BibT_eX]

[DOI]

Leszek Gasieniec

,

,

Theor. Comput. Sci., 2007

On the membership of invertible diagonal and scalar matrices.

[BibT_eX]

[DOI]

,

Theor. Comput. Sci., 2007

Deterministic Communication in Radio Networks with Large Labels.

[BibT_eX]

[DOI]

Leszek Gasieniec

,

Aris Pagourtzis

,

,

Algorithmica, 2007

Computation in One-Dimensional Piecewise Maps.

[BibT_eX]

[DOI]

Oleksiy Kurganskyy

,

,

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.

[BibT_eX]

[DOI]

,

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

Lowering Undecidability Bounds for Decision Questions in Matrices.

[BibT_eX]

[DOI]

,

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

On a Maximal NFA Without Mergible States.

[BibT_eX]

[DOI]

,

Oleksiy Kurganskyy

,

Proceedings of the Computer Science, 2006

2005

Space efficient search for maximal repetitions.

[BibT_eX]

[DOI]

Leszek Gasieniec

,

Roman M. Kolpakov

,

Theor. Comput. Sci., 2005

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

[BibT_eX]

[DOI]

Oleksiy Kurganskyy

,

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

Temporal Logic with Predicate lambda-Abstraction.

[BibT_eX]

[DOI]

,

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

Languages Representable by Vertex-Labeled Graphs.

[BibT_eX]

[DOI]

,

Oleksiy Kurganskyy

,

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

On the Membership of Invertible Diagonal Matrices.

[BibT_eX]

[DOI]

,

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

Real-Time Traversal in Grammar-Based Compressed Files.

[BibT_eX]

[DOI]

Leszek Gasieniec

,

Roman M. Kolpakov

,

,

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

2004

Temporal logic with predicate abstraction

[BibT_eX]

[DOI]

,

CoRR, 2004

Time Efficient Gossiping in Known Radio Networks.

[BibT_eX]

[DOI]

Leszek Gasieniec

,

,

Proceedings of the Structural Information and Communication Complexity, 2004

Membership and Reachability Problems for Row-Monomial Transformations.

[BibT_eX]

[DOI]

,

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

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

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 2004

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

[BibT_eX]

[DOI]

Oleksiy Kurganskyy

,

Proceedings of the Developments in Language Theory, 2004

2003

Time/Space Efficient Compressed Pattern Matching.

[BibT_eX]

[DOI]

Leszek Gasieniec

,

Fundam. Informaticae, 2003

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

[BibT_eX]

[DOI]

,

Aris Pagourtzis

,

,

Wojciech Rytter

Comput. J., 2003

2002

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

[BibT_eX]

[DOI]

Aris Pagourtzis

,

,

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.

[BibT_eX]

[DOI]

Leszek Gasieniec

,

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

Deterministic Communication in Radio Networks with Large Labels.

[BibT_eX]

[DOI]

Leszek Gasieniec

,

Aris Pagourtzis

,

Proceedings of the Algorithms, 2002

2001

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

[BibT_eX]

[DOI]

Aris Pagourtzis

,

,

Wojciech Rytter

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

Loading...