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.

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.

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 PSL2(Z), the Special Linear group SL2(Z) and the General Linear Group GL2(Z) is solvable in NP. We extend this to prove that the membership problem is decidable in NP for GL2(Z) and for any arbitrary regular expression over matrices from SL2(Z). We then derive that the problems of whether a given finite set of matrices from SL2(Z) or PSL2(Z) generates a group or a free semigroup are both decidable in NP. The previous algorithm for these problems, shown in 2005 by Choffrut and Karhumäki, was 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 the known NP-hard lower bound, this proves that the identity (and thus membership) problem over GL2(Z) is NP-complete, and the group problem and the non-freeness problem in SL2(Z) are NP-complete. Thus the paper answer the long standing open question on the complexity of the membership problem in semigroups generated by matrices from GL2(Z). We develop novel techniques that can be used for solving numerical matrix problems in symbolic form, which are applicable for solving compressed word problems for groups and semigroups, bridging the gap between combinatorial group theory, computational problems on matrices and complexity theory.

Abstract. We consider membership problems for rational subsets of the semigroup of [Formula: see text] matrices over [Formula: see text]. For a semigroup [Formula: see text], the rational subsets [Formula: see text] are defined as the sets accepted by nondeterministic finite automatons whose transitions are labeled by elements of [Formula: see text]. In general, it is undecidable on inputs [Formula: see text] and [Formula: see text] whether [Formula: see text] belongs to [Formula: see text]. Therefore, we restrict our attention to the family [Formula: see text] of flat rational subsets of [Formula: see text] over [Formula: see text], where [Formula: see text] is a subsemigroup of [Formula: see text]. It consists of finite unions of the form [Formula: see text], where [Formula: see text] and [Formula: see text]. Assuming that the membership for [Formula: see text] is decidable, we prove various results when the membership for [Formula: see text] is decidable. If [Formula: see text] is a subgroup of a group [Formula: see text], then we provide a rather general condition when [Formula: see text] is an (effective) relative Boolean algebra. This leads to one of our main results that the emptiness problem for Boolean combinations of sets in [Formula: see text] is decidable. It is possible that such a strong decidability result cannot be pushed any further for groups sitting between [Formula: see text] and [Formula: see text]. To support this possibility, we prove the following dichotomy: If [Formula: see text] is a finitely generated group such that [Formula: see text], then either [Formula: see text] or [Formula: see text] contains an extension of the Baumslag–Solitar group [Formula: see text] of infinite index. It is open whether the membership for rational subsets is decidable in the latter case. For singular matrices, we will show that the membership problem for [Formula: see text] is decidable in doubly exponential time, where [Formula: see text] is the monoid generated by [Formula: see text].

We consider a discrete system of n simple indistinguishable devices, called agents, forming a connected shape SI 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 SI into a given target shape SF 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 SI whose associated graph contains a Hamiltonian path known to them, the agents can form a final straight line SL. The complexity of the transformation is O(nlog2⁡n) moves, which is asymptotically equivalent to that of the best-known centralised transformations.

Abstract The problem of uniformly placing N points onto a sphere finds applications in many areas. For example, points on the sphere correspond to unit quaternions as well as to the group of rotations SO(3) and the online version of generating uniform rotations (known as “incremental generation”) plays a crucial role in a large number of engineering applications ranging from robotics and aeronautics to computer graphics. An online version of this problem was recently studied with respect to the gap ratio as a measure of uniformity. The first online algorithm of Chen et al. was upper-bounded by 5.99 and later improved to 3.69, which is achieved by considering a circumscribed dodecahedron followed by a recursive decomposition of each face. In this paper we provide a more efficient tessellation technique based on the regular icosahedron, which improves the upper-bound for the online version of this problem, decreasing it to approximately 2.84. Moreover, we show that the lower bound for the gap ratio of placing at least three points is $$({1+\sqrt{5}})/2\approx 1.618$$ ( 1 + 5 ) / 2 ≈ 1.618 and for at least four points is no less than 1.726.

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.

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(n2) 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.

The main result of the paper is the first polynomial-time algorithm for ranking bracelets. The time-complexity of the algorithm is O(k^2 n^4), where k is the size of the alphabet and n is the length of the considered bracelets. The key part of the algorithm is to compute the rank of any word with respect to the set of bracelets by finding three other ranks: the rank over all necklaces, the rank over palindromic necklaces, and the rank over enclosing apalindromic necklaces. The last two concepts are introduced in this paper. These ranks are key components to our algorithm in order to decompose the problem into parts. Additionally, this ranking procedure is used to build a polynomial-time unranking algorithm.

Crystal Structure Prediction (CSP) is one of the central and most challenging problems in materials science and computational chemistry. In CSP, the goal is to find a configuration of ions in 3D space that yields the lowest potential energy. Finding an efficient procedure to solve this complex optimisation question is a well known open problem. Due to the exponentially large search space, the problem has been referred in several materials-science papers as “NP-Hard and very challenging” without a formal proof. This paper fills a gap in the literature providing the first set of formally proven NP-Hardness results for a variant of CSP with various realistic constraints. In particular, we focus on the problem of removal: the goal is to find a substructure with minimal potential energy, by removing a subset of the ions. Our main contributions are NP-Hardness results for the CSP removal problem, new embeddings of combinatorial graph problems into geometrical settings, and a more systematic exploration of the energy function to reveal the complexity of CSP. In a wider context, our results contribute to the analysis of computational problems for weighted graphs embedded into the three-dimensional Euclidean space.

The present special issue of Fundamenta Informaticae journal is devoted to the 11th International Workshop on Reachability Problems (

We consider the following variant of the Mortality Problem: given $k\times k$ matrices $A_1, A_2, \dots,A_{t}$, does there exist nonnegative integers $m_1, m_2, \dots,m_t$ such that the product $A_1^{m_1} A_2^{m_2} \cdots A_{t}^{m_{t}}$ is equal to the zero matrix? It is known that this problem is decidable when $t \leq 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 \leq 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 \times 2$ rational matrices by employing powerful tools from transcendence theory such as Baker's theorem and S-unit equations.

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.

This work relates numerical problems on matrices over the rationals to symbolic algorithms on words and finite automata. Using exact algebraic algorithms and symbolic computation, we prove new decidability results for 2 × 2 matrices over Q. Namely, we introduce a notion of flat rational sets: if M is a monoid and N ≤ M is its submonoid, then flat rational sets of M relative to N are finite unions of the form L0g1 L1 ··· gtLt where all Lis are rational subsets of N and gi ∈ M. We give quite general sufficient conditions under which flat rational sets form an effective relative Boolean algebra. As a corollary, we obtain that the emptiness problem for Boolean combinations of flat rational subsets of GL(2, Q) over GL(2, Z) is decidable.

We study the identity problem for matrices, i.e., whether the identity matrix is in a semigroup generated by a given set of generators. In particular we consider the identity problem for the special linear group following recent NP-completeness result for SL(2,Z) and the undecidability for SL(4,Z) generated by 48 matrices. First we show that there is no embedding from pairs of words into 3 x3 integer matrices with determinant one, i.e., into SL{(3,Z)} extending previously known result that there is no embedding into C^{2 x 2}. Apart from theoretical importance of the result it can be seen as a strong evidence that the computational problems in SL{(3,Z)} are decidable. The result excludes the most natural possibility of encoding the Post correspondence problem into SL{(3,Z)}, where the matrix products extended by the right multiplication correspond to the Turing machine simulation. Then we show that the identity problem is decidable in polynomial time for an important subgroup of SL(3,Z), the Heisenberg group H(3,Z). Furthermore, we extend the decidability result for H(n,Q) in any dimension n. Finally we are tightening the gap on decidability question for this long standing open problem by improving the undecidability result for the identity problem in SL{(4,Z)} substantially reducing the bound on the size of the generator set from 48 to 8 by developing a novel reduction technique.

We study the vector ambiguity problem and the vector freeness problem in SL(2, ℤ). Given a finitely generated n × n matrix semigroup S and an n-dimensional vector x, the vector ambiguity problem is to decide whether for every target vector y = Mx, where M ∈ S, M is unique. We also consider the vect or freeness problem which is to show that every matrix M which is transforming x to Mx has a unique factorization with respect to the generator of S. We show that both problems are NP-complete in SL(2, ℤ), which is the set of 2 × 2 integer matrices with determinant 1. Moreover, we generalize the vector ambiguity problem and extend to the finite and k-vector ambiguity problems where we consider the degree of vector ambiguity of matrix semigroups.

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.

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 PSL2(ℤ) and thus the Special Linear group SL2(ℤ) is solvable in NP. From this fact, we can immediately derive that the fundamental problem of whether a given finite set of matrices from SL2(ℤ) or PSL2(ℤ) 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 SL2 (ℤ) are NP-complete.

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 M1,…, Mn and M decides whether M belongs to the semigroup generated by {M1,…, Mn}. 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.

Robot game is a two-player vector addition game played on the integer lattice $\mathbb{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.

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.

and extended versions of the papers selected from the 6th of the Reachability Problems Workshop hosted by the University of Bordeaux, France from 17 till

In this paper we investigate the decidability and complexity of problems related to braid composition. While all known problems for a class of braids with 3 strands, B_3, have polynomial time solutions we prove that a very natural question for braid composition, the membership problem, is NP-hard for braids with only 3 strands. The membership problem is decidable for B_3, but it becomes harder for a class of braids with more strands. In particular we show that fundamental problems about braid compositions are undecidable for braids with at least 5 strands, but decidability of these problems for B_4 remains open. The paper introduces a few challenging algorithmic problems about topological braids opening new connections between braid groups, combinatorics on words, complexity theory and provides solutions for some of these problems by application of several techniques from automata theory, matrix semigroups and algorithms.

federated and organized in parallel by Masaryk University in Brno, Czech Republic.The MFCS symposia, organized since 1972, encourage high-quality research in all branches of theoretical computer science.The broad scope of MFCS provides an opportunity to bring together researchers who do not usually meet at specialized conferences.Computer Science Logic (CSL) is the annual conference of the European Association for Computer Science Logic (EACSL).The conference is intended for computer scientists whose research activities involve logic, as well as for logicians working on issues significant for computer science.

Most computational problems for matrix semigroups and groups are inherently difficult to solve and even undecidable starting from dimension three. The questions about the decidability and complexity of problems for two-dimensional matrix semigroups r

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. John McCarthy in his Elephant programming language proposal suggested exploiting the referring to the past as the main programming primitive. In this paper we study the computational power of such primitive. In order to do that we propose a refined formal model, History Dependent Machine (HDM), 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, HDM can simulate any multicounter machine in real time. Then we show that the computations of HDM may be specified in the extension of propositional linear temporal logic by flexible constants, the abstraction operator and equality. We use then universality of HDM model to show that the above extension with a single flexible constant is not recursively axiomatizable.

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

Summary form only given. In text compression applications, it is important to be able to process compressed data without requiring (complete) decompression. In this context it is crucial to study compression methods that allow time/space efficient access to any fragment of a compressed file without being forced to perform complete decompression. We study here the real-time recovery of consecutive symbols from compressed files, in the context of grammar-based compression. In this setting, a compressed text is represented as a small (a few Kb) dictionary D (containing a set of code words), and a very long (a few Mb) string based on symbols drawn from the dictionary D. The space efficiency of this kind of compression is comparable with standard compression methods based on the Lempel-Ziv approach. We show, that one can visit consecutive symbols of the original text, moving from one symbol to another in constant time and extra O(|D|) space. This algorithm is an improvement of the on-line linear (amortised) time algorithm presented in (L. Gasieniec et al, Proc. 13th Int. Symp. on Fund. of Comp. Theo., LNCS, vol.2138, p.138-152, 2001).

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.

We investigate the relation between fine-grained and coarse-grained distributed computations of a class of problems related to the generic transitive closure problem (TC for short). We choose an intricate systolic algorithm for the TC problem, by Guibas, Kung and Thompson (GKT algorithm for short), as a starting point due to its particularly close relationship to matrix multiplication. The GKT algorithm reduces the TC problem to three successive parallel matrix multiplications. We extract the main ideas of this algorithm, namely different path decompositions related to min-paths and max-paths computations and devise a two-pass parallel algorithm, such that the second pass is purely a triangular matrix multiplication involving exactly $\frac13$ of the total number of elementary operations (multiplying two single elements of the matrix). This is helpful in coarse-grained parallel computations since matrix multiplication is well parallelizable. A novel approach is used and as a first result a more efficient and simpler two-pass fine-grained algorithm is designed. The second result is a non-trivial transformation of this fine-grained algorithm into a coarse-grained (and more practical) version. The full proof of correctness of the transformation, which is presented in the appendices, is quite complex and is the hardest result of the paper. Our algorithms are specially structured to directly show the correspondence between the main fine-grained and the main coarse-grained operations.