Igor Potapov

According to our database1, Igor Potapov authored at least 84 papers between 2001 and 2020.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
Pushing lines helps: Efficient universal centralised transformations for programmable matter.
Theor. Comput. Sci., 2020

On decidability and complexity of low-dimensional robot games.
J. Comput. Syst. Sci., 2020

The K-Centre Problem for Necklaces.
CoRR, 2020

On Efficient Connectivity-Preserving Transformations in a Grid.
CoRR, 2020

On the Hardness of Energy Minimisation for Crystal Structure Prediction.
Proceedings of the SOFSEM 2020: Theory and Practice of Computer Science, 2020

Decidability of membership problems for flat rational subsets of GL(2, Q) and singular matrices.
Proceedings of the ISSAC '20: International Symposium on Symbolic and Algebraic Computation, 2020

Optimizing Reachability Sets in Temporal Graphs by Delaying.
Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020

2019
Vector and scalar reachability problems in SL(2, Z).
J. Comput. Syst. Sci., 2019

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

On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond.
Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

Polygon Approximations of the Euclidean Circles on the Square Grid by Broadcasting Sequences.
Proceedings of the Discrete Geometry for Computer Imagery, 2019

Towards Uniform Online Spherical Tessellations.
Proceedings of the Computing with Foresight and Industry, 2019

2018
Reachability Problems 2014: Special issue.
Theor. Comput. Sci., 2018

Reachability problems: Special issue.
Theor. Comput. Sci., 2018

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

Reachability Problems for One-Dimensional Piecewise Affine Maps.
Int. J. Found. Comput. Sci., 2018

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

De Bruijn graphs and powers of 3/2.
CoRR, 2018

On the Identity Problem for the Special Linear Group and the Heisenberg Group.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Reachability Problems in Nondeterministic Polynomial Maps on the Integers.
Proceedings of the Developments in Language Theory - 22nd International Conference, 2018

2017
Weighted automata on infinite words in the context of Attacker-Defender games.
Inf. Comput., 2017

Composition problems for braids: Membership, Identity and Freeness.
CoRR, 2017

Matrix Semigroup Freeness Problems in SL (2, \mathbb Z).
Proceedings of the SOFSEM 2017: Theory and Practice of Computer Science, 2017

Decidability of the Membership Problem for 2 × 2 integer matrices.
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.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Membership Problem in GL(2, Z) Extended by Singular Matrices.
Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

2016
Preface.
Fundam. Inform., 2016

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

Reachability Problems for PAMs.
Proceedings of the SOFSEM 2016: Theory and Practice of Computer Science, 2016

Insertion-Deletion Systems over Relational Words.
Proceedings of the Reachability Problems - 10th International Workshop, 2016

Pattern formations with broadcasting automata model.
Proceedings of the Eighth Workshop on Non-Classical Models of Automata and Applications, 2016

Vector Reachability Problem in SL(2, Z).
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Undecidability of Two-dimensional Robot Games.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015
On Robot Games of Degree Two.
Proceedings of the Language and Automata Theory and Applications, 2015

2014
Broadcasting Automata and Patterns on Z^2.
CoRR, 2014

On Undecidability of Counter Reachability Games in Dimension One.
CoRR, 2014

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

Preface.
Fundam. Inform., 2013

Composition Problems for Braids.
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.
Theor. Comput. Sci., 2012

Geometric computations by broadcasting automata.
Nat. Comput., 2012

On the Computational Complexity of Matrix Semigroup Problems.
Fundam. Inform., 2012

Discrete Discs and Broadcasting Sequences.
Proceedings of the Unconventional Computation and Natural Computation, 2012

Mortality for 2×2 Matrices Is NP-Hard.
Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

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

Geometric Computations by Broadcasting Automata on the Integer Grid.
Proceedings of the Unconventional Computation - 10th International Conference, 2011

Planarity of Knots, Register Automata and LogSpace Computability.
Proceedings of the Language and Automata Theory and Applications, 2011

2010
On decision problems for parameterized machines.
Theor. Comput. Sci., 2010

On the Undecidability of the Identity Correspondence Problem and its Applications for Word and Matrix Semigroups.
Int. J. Found. Comput. Sci., 2010

A measure of state transition of collective of stateless automata in discrete environment
CoRR, 2010

2009
On the Computational Power of Querying the History.
Fundam. Inform., 2009

On Descriptional Complexity of the Planarity Problem for Gauss Words
CoRR, 2009

Automata on Gauss Words.
Proceedings of the Language and Automata Theory and Applications, 2009

The Identity Correspondence Problem and Its Applications.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

2008
On undecidability bounds for matrix decision problems.
Theor. Comput. Sci., 2008

Reachability Problems in Low-Dimensional Iterative Maps.
Int. J. Found. Comput. Sci., 2008

Matrix Equations and Hilbert's Tenth Problem.
IJAC, 2008

Reachability problems in quaternion matrix and rotation semigroups.
Inf. Comput., 2008

Preface.
Electron. Notes Theor. Comput. Sci., 2008

Periodic and Infinite Traces in Matrix Semigroups.
Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

2007
Time efficient centralized gossiping in radio networks.
Theor. Comput. Sci., 2007

On the membership of invertible diagonal and scalar matrices.
Theor. Comput. Sci., 2007

Deterministic Communication in Radio Networks with Large Labels.
Algorithmica, 2007

Computation in One-Dimensional Piecewise Maps.
Proceedings of the Hybrid Systems: Computation and Control, 10th International Workshop, 2007

2006
In time alone: on the computational power of querying the history.
Proceedings of the 13th International Symposium on Temporal Representation and Reasoning (TIME 2006), 2006

Lowering Undecidability Bounds for Decision Questions in Matrices.
Proceedings of the Developments in Language Theory, 10th International Conference, 2006

On a Maximal NFA Without Mergible States.
Proceedings of the Computer Science, 2006

2005
Space efficient search for maximal repetitions.
Theor. Comput. Sci., 2005

Computation in One-Dimensional Piecewise Maps and Planar Pseudo-Billiard Systems.
Proceedings of the Unconventional Computation, 4th International Conference, 2005

Temporal Logic with Predicate lambda-Abstraction.
Proceedings of the 12th International Symposium on Temporal Representation and Reasoning (TIME 2005), 2005

Languages Representable by Vertex-Labeled Graphs.
Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

On the Membership of Invertible Diagonal Matrices.
Proceedings of the Developments in Language Theory, 9th International Conference, 2005

Real-Time Traversal in Grammar-Based Compressed Files.
Proceedings of the 2005 Data Compression Conference (DCC 2005), 2005

2004
Temporal logic with predicate abstraction
CoRR, 2004

Time Efficient Gossiping in Known Radio Networks.
Proceedings of the Structural Information and Communication Complexity, 2004

Membership and Reachability Problems for Row-Monomial Transformations.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

From Post Systems to the Reachability Problems for Matrix Semigroups and Multicounter Automata.
Proceedings of the Developments in Language Theory, 2004

On the Computation Power of Finite Automata in Two-dimensional Environments.
Proceedings of the Developments in Language Theory, 2004

2003
Time/Space Efficient Compressed Pattern Matching.
Fundam. Inform., 2003

Coarse-Grained Parallel Transitive Closure Algorithm: Path Decomposition Technique.
Comput. J., 2003

2002
Observations on Parallel Computation of Transitive and Max-Closure Problems.
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.
Proceedings of the Foundations of Information Technology in the Era of Networking and Mobile Computing, 2002

Deterministic Communication in Radio Networks with Large Labels.
Proceedings of the Algorithms, 2002

2001
PVM Computation of the Transitive Closure: The Dependency Graph Approach.
Proceedings of the Recent Advances in Parallel Virtual Machine and Message Passing Interface, 2001


  Loading...