Igor Potapov

TCS Journal 2026 Journal Article

Capturing an invisible robber using separators

• Igor Potapov
• Tymofii Prokopenko
• John Sylvester

We study the zero-visibility cops and robbers game, where the robber is invisible to the cops until they are caught. This differs from the classic game where full information about the robber’s location is known at any time. A previously known solution for capturing a robber in the zero-visibility case is based on the path decomposition. We provide an alternative solution based on a separation hierarchy, improving capture time and space complexity without asymptotically increasing the zero-visibility cop number in most cases. In addition, the alternative approach leads to a better bound on the approximate zero-visibility cop number for various classes of graphs, where approximate refers to the restriction to polynomial time computable strategies.

I&C Journal 2025 Journal Article

Collision-free Robot Scheduling

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

In this paper, we investigate the problem of designing schedules for completing a set of tasks at fixed locations with multiple robots in a laboratory. We represent the laboratory as a graph with tasks placed on fixed vertices and robots represented as agents, with the constraint that no two robots may occupy the same vertex at any given timestep. Each schedule is partitioned into a set of timesteps, corresponding to a walk through the graph (allowing for a robot to wait at a vertex to complete a task), with each timestep taking time equal to the time for a robot to move from one vertex to another and each task taking some given number of timesteps during the completion of which a robot must stay at the vertex containing the task. The goal is to determine a set of schedules, with one schedule for each robot, minimising the number of timesteps taken by the schedule taking the greatest number of timesteps within the set of schedules. We show that this problem is NP-complete for both star graphs (for k ≥ 2 robots), and planar graphs (for any number of robots). Finally, we provide positive results for path, cycle, and tadpole graphs, showing that we can find an optimal set of schedules for k robots completing m tasks of equal duration of a path of length n in O ( k m n ), O ( k m n 2 ) time, and O ( k 3 m 4 n ) time respectively.

I&C Journal 2024 Journal Article

The membership problem for subsemigroups of GL 2 ( Z ) is NP-complete

• Paul C. Bell
• Mika Hirvensalo
• Igor Potapov

We show that the problem of determining if the identity matrix belongs to a finitely generated semigroup of 2 × 2 matrices from the General Linear Group GL 2 ( Z ) is solvable in NP. We extend this to prove that the membership problem is decidable in NP for GL 2 ( Z ) and for any arbitrary regular expression over matrices from the Special Linear group SL 2 ( Z ). We show that determining if a given finite set of matrices from SL 2 ( Z ) or the modular group PSL 2 ( Z ) generates a group or a free semigroup are decidable in NP. Previous algorithms, shown in 2005 by Choffrut and Karhumäki, were in EXPSPACE. Our algorithm is based on new techniques allowing us to operate on compressed word representations of matrices without explicit expansions. When combined with known NP-hard lower bounds, this proves that the membership problem over GL 2 ( Z ) is NP-complete, and the group problem and the non-freeness problem in SL 2 ( Z ) are NP-complete. 1

TCS Journal 2023 Journal Article

Distributed transformations of Hamiltonian shapes based on line moves

• Abdullah Almethen
• Othon Michail
• Igor Potapov

We consider a discrete system of n simple indistinguishable devices, called agents, forming a connected shape S I on a two-dimensional square grid. Agents are equipped with a linear-strength mechanism, called a line move, by which an agent can push a whole line of consecutive agents in one of the four cardinal directions in a single time-step. We study the problem of transforming an initial shape S I into a given target shape S F via a finite sequence of line moves in a distributed model, where each agent can observe the states of nearby agents in a Moore neighbourhood. We develop the first distributed connectivity-preserving transformation that exploits line moves. The transformation solves the line formation problem. That is, starting from any shape S I whose associated graph contains a Hamiltonian path known to them, the agents can form a final straight line S L. The complexity of the transformation is O ( n log 2 ⁡ n ) moves, which is asymptotically equivalent to that of the best-known centralised transformations.

TCS Journal 2022 Journal Article

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

• Matthew Connor
• Othon Michail
• Igor Potapov

We study a model of programmable matter systems consisting of n devices lying on a 2-dimensional square grid which are able to perform the minimal mechanical operation of rotating around each other. The goal is to transform an initial shape A into a target shape B. We investigate the class of shapes which can be constructed in such a scenario under the additional constraint of maintaining global connectivity at all times. We focus on the scenario of transforming nice shapes, a class of shapes consisting of a central line L where for all nodes u in S either u ∈ L or u is connected to L by a line of nodes perpendicular to L. We prove that by introducing a minimal 3-node seed it is possible for the canonical shape of a line of n nodes to be transformed into a nice shape of n − 1 nodes. We use this to show that a 4-node seed enables the transformation of nice shapes of size n into any other nice shape of size n in O ( n 2 ) time. We leave as an open problem the expansion of the class of shapes which can be constructed using such a seed to include those derived from nice shapes.

TCS Journal 2022 Journal Article

On efficient connectivity-preserving transformations in a grid

• Abdullah Almethen
• Othon Michail
• Igor Potapov

We consider a discrete system of n devices lying on a 2-dimensional square grid and forming an initial connected shape S I. Each device is equipped with a linear-strength mechanism which enables it to move a whole line of consecutive devices in a single time-step, called a line move. We study the problem of transforming S I into a given connected target shape S F of the same number of devices, via a finite sequence of line moves. Our focus is on designing centralised transformations aiming at minimising the total number of moves subject to the constraint of preserving connectivity of the shape throughout the course of the transformation. We first give very fast connectivity-preserving transformations for the case in which the associated graphs of S I and S F contain a Hamiltonian path. In particular, our transformations make O ( n log ⁡ n ) moves, which is asymptotically equal to the best known running time of connectivity-breaking transformations. Our most general result is then a connectivity-preserving universal transformation that can transform any initial connected shape S I into any target connected shape S F, through a sequence of O ( n n ) moves.

I&C Journal 2022 Journal Article

Optimizing reachability sets in temporal graphs by delaying

• Argyrios Deligkas
• Igor Potapov

A temporal graph is a dynamic graph where every edge is assigned a set of integer time labels that indicate at which discrete time step the edge is available. In this paper, we study how changes of the time labels, corresponding to delays on the availability of the edges, affect the reachability sets from given sources. We introduce control mechanisms for reachability sets that are based on two natural operations of delaying. The first operation, termed merging, is global and batches together consecutive time labels into a single time label in the whole network simultaneously. The second, imposes independent delays on the time labels of every edge of the graph. We provide a thorough investigation of the computational complexity of different objectives related to reachability sets when these operations are used.

MFCS Conference 2022 Conference Paper

The Complexity of Periodic Energy Minimisation

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

The computational complexity of pairwise energy minimisation of N points in real space is a long-standing open problem. The idea of the potential intractability of the problem was supported by a lack of progress in finding efficient algorithms, even when restricted the integer grid approximation. In this paper we provide a firm answer to the problem on ℤ^d by showing that for a large class of pairwise energy functions the problem of periodic energy minimisation is NP-hard if the size of the period (known as a unit cell) is fixed, and is undecidable otherwise. We do so by introducing an abstraction of pairwise average energy minimisation as a mathematical problem, which covers many existing models. The most influential aspects of this work are showing for the first time: 1) undecidability of average pairwise energy minimisation in general 2) computational hardness for the most natural model with periodic boundary conditions, and 3) novel reductions for a large class of generic pairwise energy functions covering many physical abstractions at once. In particular, we develop a new tool of overlapping digital rhombuses to incorporate the properties of the physical force fields, and we connect it with classical tiling problems. Moreover, we illustrate the power of such reductions by incorporating more physical properties such as charge neutrality, and we show an inapproximability result for the extreme case of the 1D average energy minimisation problem.

I&C Journal 2021 Journal Article

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

• Paul C. Bell
• Igor Potapov
• Pavel Semukhin

We consider a variant of the mortality problem: given k × k matrices A 1, …, A t, do there exist nonnegative integers m 1, …, m t such that A 1 m 1 ⋯ A t m t equals the zero matrix? This problem is known to be decidable when t ≤ 2 but undecidable for integer matrices with sufficiently large t and k. We prove that for t = 3 this problem is Turing-equivalent to Skolem's problem and thus decidable for k ≤ 3 (resp. k = 4 ) over (resp. real) algebraic numbers. Consequently, the set of triples ( m 1, m 2, m 3 ) for which the equation A 1 m 1 A 2 m 2 A 3 m 3 equals the zero matrix is a finite union of direct products of semilinear sets. For t = 4 we show that the solution set can be non-semilinear, and thus there is unlikely to be a connection to Skolem's problem. We prove decidability for upper-triangular 2 × 2 rational matrices by employing powerful tools from transcendence theory such as Baker's theorem and S-unit equations.

AAAI Conference 2020 Conference Paper

Optimizing Reachability Sets in Temporal Graphs by Delaying

• Argyrios Deligkas
• Igor Potapov

A temporal graph is a dynamic graph where every edge is assigned a set of integer time labels that indicate at which discrete time step the edge is available. In this paper, we study how changes of the time labels, corresponding to delays on the availability of the edges, affect the reachability sets from given sources. The questions about reachability sets are motivated by numerous applications of temporal graphs in network epidemiology and scheduling problems in supply networks in manufacturing. We introduce control mechanisms for reachability sets that are based on two natural operations of delaying time events. The first operation, termed merging, is global and batches together consecutive time labels in the whole network simultaneously. This corresponds to postponing all events until a particular time. The second, imposes independent delays on the time labels of every edge of the graph. We provide a thorough investigation of the computational complexity of different objectives related to reachability sets when these operations are used. For the merging operation, we prove NP-hardness results for several minimization and maximization reachability objectives, even for very simple graph structures. For the second operation, we prove that the minimization problems are NP-hard when the number of allowed delays is bounded. We complement this with a polynomial-time algorithm for the case of unbounded delays.

TCS Journal 2020 Journal Article

Pushing lines helps: Efficient universal centralised transformations for programmable matter

• Abdullah Almethen
• Othon Michail
• Igor Potapov

In this work, we study a discrete system of entities residing on a two-dimensional square grid. Each entity is modelled as a node occupying a distinct cell of the grid. The set of all n nodes forms initially a connected shape A. Entities are equipped with a linear-strength pushing mechanism that can push a whole line of entities in parallel in a single time-step on one position in a given (one of the four possible) direction of a grid. A target connected shape B is also provided and the goal is to transform A into B via a sequence of line moves. Existing models based on local movement of individual nodes, such as rotating or sliding a single node, can be shown to be special cases of the present model, therefore their (inefficient, Θ ( n 2 ) -time) universal transformations carry over. Our main goal is to investigate whether the parallelism inherent in this new type of movement can be exploited for efficient, i. e. , sub-quadratic worst-case, transformations. This paper provides several solutions for specific and universal centralised transformations in the context of the new model. In particular we first design O ( n log ⁡ n ) -time universal transformation without preserving the connectivity of original shape. Then we focus on transformations which preserve the connectivity of the shape throughout its course and develop an O ( n n ) -time transformation for the apparently hard instance of transforming a diagonal A into a straight line B.

MFCS Conference 2019 Conference Paper

On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond

• Paul C. Bell
• Igor Potapov
• Pavel Semukhin

We consider the following variant of the Mortality Problem: given k x k matrices A_1, A_2, .. ., A_{t}, does there exist nonnegative integers m_1, m_2, .. ., m_t such that the product A_1^{m_1} A_2^{m_2} *. .. * A_{t}^{m_{t}} is equal to the zero matrix? It is known that this problem is decidable when t <= 2 for matrices over algebraic numbers but becomes undecidable for sufficiently large t and k even for integral matrices. In this paper, we prove the first decidability results for t>2. We show as one of our central results that for t=3 this problem in any dimension is Turing equivalent to the well-known Skolem problem for linear recurrence sequences. Our proof relies on the Primary Decomposition Theorem for matrices that was not used to show decidability results in matrix semigroups before. As a corollary we obtain that the above problem is decidable for t=3 and k <= 3 for matrices over algebraic numbers and for t=3 and k=4 for matrices over real algebraic numbers. Another consequence is that the set of triples (m_1, m_2, m_3) for which the equation A_1^{m_1} A_2^{m_2} A_3^{m_3} equals the zero matrix is equal to a finite union of direct products of semilinear sets. For t=4 we show that the solution set can be non-semilinear, and thus it seems unlikely that there is a direct connection to the Skolem problem. However we prove that the problem is still decidable for upper-triangular 2 x 2 rational matrices by employing powerful tools from transcendence theory such as Baker’s theorem and S-unit equations.

TCS Journal 2018 Journal Article

Reachability Problems 2014: Special issue

• Joël Ouaknine
• Igor Potapov
• James Worrell

TCS Journal 2018 Journal Article

Reachability problems: Special issue

• Kim G. Larsen
• Igor Potapov
• Jiří Srba

SODA Conference 2017 Conference Paper

Decidability of the Membership Problem for 2 × 2 integer matrices

• Igor Potapov
• Pavel Semukhin

The main result of this paper is the decidability of the membership problem for 2 × 2 nonsingular integer matrices. Namely, we will construct the first algorithm that for any nonsingular 2 × 2 integer matrices M 1, …, M n and M decides whether M belongs to the semigroup generated by {M 1, …, M n }. Our algorithm relies on a translation of numerical problems on matrices into combinatorial problems on words. It also makes use of some algebraic properties of well-known subgroups of GL(2, Z) and various new techniques and constructions that help to convert matrix equations into the emptiness problem for intersection of regular languages.

MFCS Conference 2017 Conference Paper

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

• Igor Potapov
• Pavel Semukhin

We consider the membership problem for matrix semigroups, which is the problem to decide whether a matrix belongs to a given finitely generated matrix semigroup. In general, the decidability and complexity of this problem for two-dimensional matrix semigroups remains open. Recently there was a significant progress with this open problem by showing that the membership is decidable for 2x2 nonsingular integer matrices. In this paper we focus on the membership for singular integer matrices and prove that this problem is decidable for 2x2 integer matrices whose determinants are equal to 0, 1, -1 (i. e. for matrices from GL(2, Z) and any singular matrices). Our algorithm relies on a translation of numerical problems on matrices into combinatorial problems on words and conversion of the membership problem into decision problem on regular languages.

SODA Conference 2017 Conference Paper

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

• Paul C. Bell
• Mika Hirvensalo
• Igor Potapov

In this paper, we show that the problem of determining if the identity matrix belongs to a finitely generated semigroup of 2 × 2 matrices from the modular group PSL 2 (ℤ) and thus the Special Linear group SL 2 (ℤ) is solvable in NP. From this fact, we can immediately derive that the fundamental problem of whether a given finite set of matrices from SL 2 (ℤ) or PSL 2 (ℤ) generates a group or free semigroup is also decidable in NP. The previous algorithm for these problems, shown in 2005 by Choffrut and Karhumaki, was in EXPSPACE mainly due to the translation of matrices into exponentially long words over a binary alphabet { s, r } and further constructions with a large nondeterministic finite state automaton that is built on these words. Our algorithm is based on various new techniques that allow us to operate with compressed word representations of matrices without explicit expansions. When combined with the known NP -hard lower bound, this proves that the membership problem for the identity problem, the group problem and the freeness problem in SL 2 (ℤ) are NP -complete.

MFCS Conference 2016 Conference Paper

Undecidability of Two-dimensional Robot Games

• Reino Niskanen
• Igor Potapov
• Julien Reichert

Robot game is a two-player vector addition game played on the integer lattice Z^n. Both players have sets of vectors and in each turn the vector chosen by a player is added to the current configuration vector of the game. One of the players, called Eve, tries to play the game from the initial configuration to the origin while the other player, Adam, tries to avoid the origin. The problem is to decide whether or not Eve has a winning strategy. In this paper we prove undecidability of the robot game in dimension two answering the question formulated by Doyen and Rabinovich in 2011 and closing the gap between undecidable and decidable cases.

MFCS Conference 2016 Conference Paper

Vector Reachability Problem in SL(2, Z)

• Igor Potapov
• Pavel Semukhin

The decision problems on matrices were intensively studied for many decades as matrix products play an essential role in the representation of various computational processes. However, many computational problems for matrix semigroups are inherently difficult to solve even for problems in low dimensions and most matrix semigroup problems become undecidable in general starting from dimension three or four. This paper solves two open problems about the decidability of the vector reachability problem over a finitely generated semigroup of matrices from SL(2, Z) and the point to point reachability (over rational numbers) for fractional linear transformations, where associated matrices are from SL(2, Z). The approach to solving reachability problems is based on the characterization of reachability paths between points which is followed by the translation of numerical problems on matrices into computational and combinatorial problems on words and formal languages. We also give a geometric interpretation of reachability paths and extend the decidability results to matrix products represented by arbitrary labelled directed graphs. Finally, we will use this technique to prove that a special case of the scalar reachability problem is decidable.

MFCS Conference 2012 Conference Paper

Mortality for 2×2 Matrices Is NP-Hard

• Paul C. Bell
• Mika Hirvensalo
• Igor Potapov

Abstract We study the computational complexity of determining whether the zero matrix belongs to a finitely generated semigroup of two dimensional integer matrices (the mortality problem). We show that this problem is NP-hard to decide in the two-dimensional case by using a new encoding and properties of the projective special linear group. The decidability of the mortality problem in two dimensions remains a long standing open problem although in dimension three is known to be undecidable as was shown by Paterson in 1970. We also show a lower bound on the minimum length solution to the Mortality Problem, which is exponential in the number of matrices of the generator set and the maximal element of the matrices.

TCS Journal 2012 Journal Article

On algebra of languages representable by vertex-labeled graphs

• Igor Grunsky
• Igor Potapov
• Elena Pryanichnikova

In this paper, we introduce and study an algebra of languages representable by vertex-labeled graphs. The proposed algebra is equipped with three operations: the union of languages, the merging of languages and the iteration. In contrast to Kleene algebra, which is mainly used for edge-labeled graphs, it can adequately represent many properties of languages defined by vertex-labeled graphs and provides a natural translation from vertex-labeled graphs to regular expressions and vice versa.

TCS Journal 2010 Journal Article

On decision problems for parameterized machines

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

In this paper, we investigate various decision problems concerning parameterized versions of some classes of machines. Let C ( s, m, t ) be the class of nondeterministic multitape Turing machine (TM) acceptors with a two-way read-only input, at most s states, at most m read–write worktapes, and at most t symbols in the worktape alphabet, where s, m, t are fixed positive integers. There is no restriction on the cardinality of the input alphabet. We are able to show the emptiness, disjointness, and universe (also called universality) problems to be decidable for C ( s, m, t ). For the class consisting of machines in C ( s, m, t ) that always halt or whose minimal-time accepting computations can be bounded by some recursive function f ( n ) (where n is the input length), the containment and equivalence problems are decidable. These results hold for other machines, e. g. , when the worktapes are pushdown stacks (where on every step, each pushdown can only pop the top of the stack or replace the top of the stack by at most two symbols) or when stacks are counters (where on every step, a counter can be incremented by 1, decremented by 1, or remain unchanged, and can be tested for zero). Our results are the best possible in the sense that not parameterizing one of s, m, t (or, in the case of counter machines, allowing the counters to increment by arbitrary integers that may change from machines to machines) makes the universe problem undecidable. We also give a simple characterization of the languages defined by C ( s, m, t ). Finally, we investigate the applicability of our techniques to machines with multiple input heads or multiple input tapes.

TCS Journal 2008 Journal Article

On undecidability bounds for matrix decision problems

• Paul Bell
• Igor Potapov

In this paper we consider several reachability problems such as vector reachability, membership in matrix semigroups and reachability problems in piecewise linear maps. Since all of these questions are undecidable in general, we work on lowering the bounds for undecidability. In particular, we show an elementary proof of undecidability of the reachability problem for a set of 5 two-dimensional affine transformations. Then, using a modified version of a standard technique, we also prove that the vector reachability problem is undecidable for two (rational) matrices in dimension 11. The above result can be used to show that the system of piecewise linear functions of dimension 12 with only two intervals has an undecidable set-to-point reachability problem. We also show that the “zero in the upper right corner” problem is undecidable for two integral matrices of dimension 18 lowering the bound from 23.

I&C Journal 2008 Journal Article

Reachability problems in quaternion matrix and rotation semigroups

• Paul Bell
• Igor Potapov

We examine computational problems on quaternion matrix and rotation semigroups. It is shown that in the ultimate case of quaternion matrices, in which multiplication is still associative, most of the decision problems for matrix semigroups are undecidable in dimension two. The geometric interpretation of matrix problems over quaternions is presented in terms of rotation problems for the 2- and 3-sphere. In particular, we show that the reachability of the rotation problem is undecidable on the 3-sphere and other rotation problems can be formulated as matrix problems over complex and hypercomplex numbers.

TCS Journal 2007 Journal Article

On the membership of invertible diagonal and scalar matrices

• Paul Bell
• Igor Potapov

In this paper, we consider decidability questions that are related to the membership problem in matrix semigroups. In particular, we consider the membership of a given invertible diagonal matrix in a matrix semigroup and then a scalar matrix, which has a separate geometric interpretation. Both problems have been open for any dimensions and are shown to be undecidable in dimension 4 with integral matrices by a reduction of the Post Correspondence Problem (PCP). Although the idea of PCP reduction is standard for such problems, we suggest a new coding technique to cover the case of diagonal matrices.

MFCS Conference 2007 Conference Paper

Reachability Problems in Quaternion Matrix and Rotation Semigroups

• Paul C. Bell
• Igor Potapov

Abstract We examine computational problems on quaternion matrix and rotation semigroups. It is shown that in the ultimate case of quaternion matrices, in which multiplication is still associative, most of the decision problems for matrix semigroups are undecidable in dimension two. The geometric interpretation of matrix problems over quaternions is presented in terms of rotation problems for the 2 and 3-sphere. In particular, we show that the reachability of the rotation problem is undecidable on the 3-sphere and other rotation problems can be formulated as matrix problems over complex and hypercomplex numbers.

TCS Journal 2007 Journal Article

Time efficient centralized gossiping in radio networks

• Leszek Gąsieniec
• Igor Potapov
• Qin Xin

In this paper we study the gossiping problem (all-to-all communication) in radio networks where all nodes are aware of the network topology. We start our presentation with a deterministic gossiping algorithm that works in at most n units of time in any radio network of size n. This algorithm is optimal in the worst case scenario since there exist radio network topologies, such as lines, stars and complete graphs in which radio gossiping cannot be completed in less than n communication rounds. Furthermore, we show that there does not exist any radio network topology in which the gossiping task can be solved in less than ⌊ log ( n − 1 ) ⌋ + 2 rounds. We also show that this lower bound can be matched from above for a fraction of all possible integer values of n, and for all other values of n we propose a solution which accomplishes gossiping in ⌈ log ( n − 1 ) ⌉ + 2 rounds. Then we show an almost optimal radio gossiping algorithm in trees, which misses the optimal time complexity by a single round. Finally, we study asymptotically optimal O ( D ) -time gossiping (where D is the diameter of the network) in graphs with the maximum degree Δ = O ( D 1 − 1 / ( i + 1 ) log i n ), for any integer constant i ≥ 0 and D large enough.

TIME Conference 2006 Conference Paper

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

• Alexei Lisitsa 0001
• Igor Potapov

Querying its own history is an important mechanism in the computations, especially those interacting with people or other computations such as transaction processing, electronic data interchange. In this paper we study the computational power of referring to the past primitive. To do that we propose a refined formal model, history dependent machine (RDM), which uses querying the history as its sole computational primitive. Our main result may be spelled in general terms as: a model with a single agent wandering around a pool of resources and having ability to check its own history for simple temporal properties has a universal computational power. Moreover, RDM can simulate any multicounter machine in real time. Then we show that the computations of RDM may be specified in the extension of propositional linear temporal logic by flexible constants, the abstraction operator and equality. We use then universality of RDM model to show that the above extension with a single flexible constant is not recursively axiomatizable

MFCS Conference 2005 Conference Paper

Languages Representable by Vertex-Labeled Graphs

• Igor Grunsky
• Oleksiy Kurganskyy
• Igor Potapov

Abstract In this paper we study the properties of undirected vertex-labeled graphs and the limitations on the languages that they represent. As a main result of this paper we define the necessary and sufficient conditions for the languages to be representable by a class of undirected vertex-labeled graphs and its subclasses. We assume that all obtained results and techniques are transferable to the case of undirected edge-labeled graphs and might give us similar results. The simplicity of necessary conditions emphasizes the naturalness of the result. The proof of their sufficiency is quite non-trivial and it is based on a new notion of quasi-equivalence, that is significantly different from Myhill-Nerode equivalence and might not be reduced to it.

TCS Journal 2005 Journal Article

Space efficient search for maximal repetitions

• Leszek Ga¸sieniec
• Roman Kolpakov
• Igor Potapov

We study here a problem of finding all maximal repetitions in a string of length n. We show that the problem can be solved in time O ( n log n ) in the presence of constant extra space and general (unbounded) alphabets. Subsequently we show that in the model with a constant size alphabet the problem can be solved in time O ( n ) with a help of o ( n ) extra space. Previously best known algorithms require linear additional space in both models.

TIME Conference 2005 Conference Paper

Temporal Logic with Predicate lambda-Abstraction

• Alexei Lisitsa 0001
• Igor Potapov

A predicate linear temporal logic LTL/sub /spl lambda/=/ without quantifiers but with predicate /spl lambda/-abstraction mechanism and equality is considered. The models of LTL/sub /spl lambda/=/ can be naturally seen as the systems of pebbles (flexible constants) moving over the elements of some (possibly infinite) domain. This allows to use LTL/sub /spl lambda/=/ for the specification of dynamic systems using some resources, such as processes using memory locations, mobile agents occupying some sites, etc. On the other hand we show that LTL/sub /spl lambda/=/ is not recursively axiomatizable and, therefore, fully automated verification of LTL/sub /spl lambda/=/ specifications via validity checking is not, in general, possible. The result is based on computational universality of the above abstract computational model of pebble systems, which is of independent interest due to the range of possible interpretations of such systems.

MFCS Conference 2004 Conference Paper

Membership and Reachability Problems for Row-Monomial Transformations

• Alexei Lisitsa 0001
• Igor Potapov

Abstract In this paper we study the membership and vector reachability problems for labelled transition systems with row-monomial transformations. We show the decidability of these problems for row-monomial martix semigroups over rationals and extend these results to the wider class of matrix semigroups. After that we apply our methods to reachability problems for a class of transition systems which turn out to be equivalent to specific counter machines.