We study finite semigroups of n × n matrices with rational entries. Such semigroups provide a rich generalization of transition monoids of unambiguous (and, in particular, deterministic) finite automata. In this paper we determine the maximum size of finite semigroups of rational n × n matrices, with the goal of shedding more light on the structure of such matrix semigroups. While in general such semigroups can be arbitrarily large in terms of n, a classical result of Schützenberger from 1962 implies an upper bound of 2^{𝒪(n² log n)} for irreducible semigroups, i.e., the only subspaces of ℚⁿ that are invariant for all matrices in the semigroup are ℚⁿ and the subspace consisting only of the zero vector. Irreducible matrix semigroups can be viewed as the building blocks of general matrix semigroups, and as such play an important role in mathematics and computer science. From the point of view of automata theory, they generalize strongly connected automata. Using a very different technique from that of Schützenberger, we improve the upper bound on the cardinality to 3^{n²}. This is the main result of the paper. The bound is in some sense tight, as we show that there exists, for every n, a finite irreducible semigroup with 3^{⌊ n²/4 ⌋} rational matrices. Our main result also leads to an improvement of a bound, due to Almeida and Steinberg, on the mortality threshold. The mortality threshold is a number 𝓁 such that if the zero matrix is in the semigroup, then the zero matrix can be written as a product of at most 𝓁 matrices from any subset that generates the semigroup.

The period of a strongly connected digraph is the greatest common divisor of the lengths of all its cycles. The period of a digraph is the least common multiple of the periods of its strongly connected components. These notions play an important role in the theory of Markov chains and the analysis of powers of nonnegative matrices. While the time complexity of computing the period is well-understood, little is known about its space complexity. We show that the problem of computing the period of a digraph is NL -complete, even if all its cycles are contained in the same strongly connected component. However, if the digraph is strongly connected, we show that this problem becomes L -complete. For primitive digraphs (that is, strongly connected digraphs of period one), there always exists a number m such that there is a path of length exactly m between every two vertices. We show that computing the smallest such m , called the exponent of a digraph, is NL -complete. The exponent of a primitive digraph is a particular case of the index of convergence of a nonnegative matrix, which we also show to be computable in NL , and thus NL -complete.

Several reachability problems in finite automata, such as completeness of NFAs and synchronisation of total DFAs, correspond to fundamental properties of sets of nonnegative matrices. In particular, the two mentioned properties correspond to matrix mortality and ergodicity, which ask whether there exists a product of the input matrices that is equal to, respectively, the zero matrix and a matrix with a column of strictly positive entries only. The case where the input automaton is strongly connected (that is, the corresponding set of nonnegative matrices is irreducible) frequently appears in applications and often admits better properties than the general case. In this paper, we address the existence of such properties from the computational complexity point of view, and develop a versatile technique to show that several NL-complete problems remain NL-complete in the strongly connected case. In particular, we show that deciding if a binary total DFA is synchronising is NL-complete even if it is promised to be strongly connected, and that deciding completeness of a binary unambiguous NFA with very limited nondeterminism is NL-complete under the same promise.

A zero-one matrix is a matrix with entries from {0, 1}. We study monoids containing only such matrices. A finite set of zero-one matrices generating such a monoid can be seen as the matrix representation of an unambiguous finite automaton, an important generalisation of deterministic finite automata which shares many of their good properties. Let 𝒜 be a finite set of n×n zero-one matrices generating a monoid of zero-one matrices, and m be the cardinality of 𝒜. We study the computational complexity of computing the minimum rank of a matrix in the monoid generated by 𝒜. By using linear-algebraic techniques, we show that this problem is in NC and can be solved in 𝒪(mn⁴) time. We also provide a combinatorial algorithm finding a matrix of minimum rank in 𝒪(n^{2 + ω} + mn⁴) time, where 2 ≤ ω ≤ 2.4 is the matrix multiplication exponent. As a byproduct, we show a very weak version of a generalisation of the Černý conjecture: there always exists a straight line program of size 𝒪(n²) describing a product resulting in a matrix of minimum rank. For the special case corresponding to complete DFAs (that is, for the case where all matrices have exactly one 1 in each row), the minimum rank is the size of the smallest image of the set of states under the action of a word. Our combinatorial algorithm finds a matrix of minimum rank in time 𝒪(n³ + mn²) in this case.

Abstract The recent years have seen remarkable progress in establishing the complexity of the reachability problem for vector addition systems with states (VASS), equivalently known as Petri nets. Existing work primarily considers the case in which both the VASS as well as the initial and target configurations are part of the input. In this paper, we investigate the reachability problem in the setting where the VASS and the final configuration are fixed and only the initial configuration is variable. We show that fixed VASS fully express arithmetic with counting on initial segments of the natural numbers. It follows that there is a very weak reduction from any fixed such number-theoretic predicate (e.g. square-freeness or “ $$N_1$$ N 1 is the number of primes smaller than $$N_2$$ N 2 ”) to reachability in fixed VASS where configurations are presented in unary. If configurations are given in binary, we show that there is a fixed VASS with five counters whose reachability problem is PSPACE-hard.

Given a finite set 𝒜 of square matrices and a square matrix B, all of the same dimension, the membership problem asks if B belongs to the monoid ℳ(𝒜) generated by 𝒜. The rank one problem asks if there is a matrix of rank one in ℳ(𝒜). We study the membership and the rank one problems in the case where all matrices are upper triangular matrices over the Boolean semiring. We characterize the computational complexity of these problems, and identify their PSPACE-complete and NP-complete special cases. We then consider, for a set 𝒜 of matrices from the same class, the problem of finding in ℳ(𝒜) a matrix of minimum rank with no zero rows. We show that the minimum rank of such matrix can be computed in linear time.We also characterize the space complexity of this problem depending on the size of 𝒜, and apply all these results to the ergodicity problem asking if ℳ(𝒜) contains a matrix with a column consisting of all ones. Finally, we show that our results give better upper bounds for the case where each row of every matrix in 𝒜 contains at most one non-zero entry than for the general case.

International audience

Abstract We study a problem of scheduling n jobs on machines of two types: in‐house machines and third‐party machines. Scheduling on in‐house machines incurs no additional costs, while using third‐party machines implies costs depending on their number and the time of usage. Each job has a fixed time interval for being processed which can be divided and allocated among several machines, as long as there is only one machine processing the job at any time. No machine can process more than one job at a time. Jobs can be rejected, and they are of different importance that is reflected in the weight of each job. The objective is to find a subset of the jobs and the number of third‐party machines for any period of time so that the accepted jobs can be feasibly scheduled, the total weight of the accepted jobs is maximized, and the total machine usage costs does not exceed a given upper bound. We also study a similar problem in which the objective is to maximize the total time at which at least one job is processed. Both problems are encountered in situations in which certain activities with given start and completion times have to be serviced by human operators. Examples are air traffic control and the monitoring safe vehicle unloading. Other examples are the employment of subcontractors in agriculture, construction or transportation. We will present NP‐hardness proofs, polynomial and pseudo‐polynomial optimal algorithms and an approximation algorithm for these problems and their special cases. These problems admit graph‐theoretical interpretations associated with finding independent sets and a proper vertex coloring in interval graphs.

We generalize the notions of the degree and composition from uniquely decipherable codes to arbitrary finite sets of words. We prove that if X = Y∘Z is a composition of finite sets of words with Y complete, then d(X) = d(Y) ⋅ d(Z), where d(T) is the degree of T. We also show that a finite set is synchronizing if and only if its degree equals one. This is done by considering, for an arbitrary finite set X of words, the transition monoid of an automaton recognizing X^* with multiplicities. We prove a number of results for such monoids, which generalize corresponding results for unambiguous monoids of relations.

We study the problems of finding a shortest synchronizing word and its length for a given prefix code. This is done in two different settings: when the code is defined by an arbitrary decoder recognizing its star and when the code is defined by its literal decoder (whose size is polynomially equivalent to the total length of all words in the code). For the first case for every epsilon > 0 we prove n^(1 - epsilon)-inapproximability for recognizable binary maximal prefix codes, Theta(log n)-inapproximability for finite binary maximal prefix codes and n^(1/2 - epsilon)-inapproximability for finite binary prefix codes. By c-inapproximability here we mean the non-existence of a c-approximation polynomial time algorithm under the assumption P != NP, and by n the number of states of the decoder in the input. For the second case, we propose approximation and exact algorithms and conjecture that for finite maximal prefix codes the problem can be solved in polynomial time. We also study the related problems of finding a shortest mortal and a shortest avoiding word.

We study extremal and algorithmic questions of subset and careful synchronization in monotonic automata. We show that several synchronization problems that are hard in general automata can be solved in polynomial time in monotonic automata, even without knowing a linear order of the states preserve d by the transitions. We provide asymptotically tight bounds on the maximum length of a shortest word synchronizing a subset of states in a monotonic automaton and a shortest word carefully synchronizing a partial monotonic automaton. We provide a complexity framework for dealing with problems for monotonic weakly acyclic automata over a three-letter alphabet, and use it to prove NP-completeness and inapproximability of problems such as FINITE AUTOMATA INTERSECTION and the problem of computing the rank of a subset of states in this class. We also show that checking whether a monotonic partial automaton over a four-letter alphabet is carefully synchronizing is NP-hard. Finally, we give a simple necessary and sufficient condition when a strongly connected digraph with a selected subset of vertices can be transformed into a deterministic automaton where the corresponding subset of states is synchronizing.

We study a scheduling problem for a container block, in which there are incoming containers only. Container placement is served by two non‐passing stacking cranes based at the opposite sides of the container block. The same time is required for any crane to move between two adjacent bays of the container block and the same different time is required for any crane to perform any down‐and‐up operation related to container lifting at the pick‐up point or container lowering at the storage point. Containers are assigned to the cranes according to one of the following policies: (1) two fixed sequences policy where a container processing sequence is given for each crane, (2) dedicated crane policy where containers are preassigned to the cranes, (3) one fixed, one arbitrary sequence policy where a container processing sequence is given for one crane and it can be arbitrary for the other crane, (4) flexible policy where any container can be assigned to any crane at any time, and (5) global fixed sequence policy where the container sequence is given and the relative processing order of containers in this sequence must be preserved by any crane. The objective is to minimize the completion time of the latest operation. We show that the problem is polynomially solvable for policy 1 and, if the number of containers to be placed in the same bay is no more than a half of all containers, for policy 4. It is NP‐hard in the strong sense for policies 2 and 3. Approximation algorithms with guaranteed absolute and relative deviations from the optimum are devised for policies 4 and 5. The results translate for the case of outgoing containers only.