# Parameterized complexity of synchronization and road coloring.

1 IntroductionQuestions about synchronization of finite automata have been studied since the early times of automata theory. The basic concept is very natural: For a given machine, we want to find an input sequence that gets the machine to some particular state, no matter in which state the machine was before. Such sequence is called a reset word (i). If an automaton has a reset word, we call it a synchronizing automaton. A need for finding reset words appears in several fields of mathematics and engineering. Classical applications (see [21]) include model-based testing of sequential circuits, robotic manipulation, and symbolic dynamics, but there are also some important connections with information theory [20] and with formal models of biomolecular processes [3].

Two particular problems concerning synchronization have gained some publicity: the Road Coloring Problem and the Cerny conjecture. The first one has been solved by Trahtman [17, 19] in 2008 by proving that the edges of any strongly connected aperiodic directed multigraph with constant out-degree can be colored such that a synchronizing automaton arises. Motivation for this problem comes from symbolic dynamics [1]. The Cerny conjecture remains open since 1971 [4, 5]. It claims that any t-state synchronizing automaton has a reset word of length at most [(t-1).sup.2].

In the practical applications of synchronization one may need to compute a reset word for a given automaton and, moreover, the reset word should be as short as possible. The need to compute a synchronizing labeling for a suitable graph, possibly with a request for a short reset word, may arise as well. It turns out, as we describe below, that such computational problems are typically NP-hard, even under heavy restrictions.

Parameterized Complexity offers various notions and useful tools that has became standard in modern analysis of NP-complete problems. The problems are studied with respect to numerical attributes (parameters) of instances. A multi-parameter analysis considers multiple different parameters and their combinations. In the present paper we close the multi-parameter analyses of canonical problems SYN and SRCP related to synchronization and road coloring. The study of SYN was initiated in 2013 by Fernau, Heggernes, and Villanger [8, 9]. The results about SRCP give complete answers to the questions raised by the second author and Drewienkowski [13, 14].

Since the instances of our problems consist of automata, graphs and word lengths, the natural parameters are: the number t of states (or vertices), the alphabet size 111, and the word length k (see the definitions in Sec. 287 and a summary of the results in Tab. 1 and Tab. 2).

2 Preliminaries

2.1 Automata and synchronization

A deterministic finite automaton is a triple A = (Q, I, [delta]), where Q and I are finite sets and [delta] is an arbitrary mapping Q x I [right arrow] Q. Elements of Q are called states, I is the alphabet. The transition function [delta] is naturally extended to Q x [I.sup.*] [right arrow] Q, still denoted by [delta], slightly abusing the notation. We extend it also by defining

[delta](S, w) = {[delta](s, w) | [delta] [member of] [delta]}

for each [delta] [subset or equal to] Q and w [member of] [I.sup.*]. If an automaton A = (Q, I, [delta]) is fixed, we write

r [??] s

instead of [delta] (r, x) = s.

For a given automaton A = (Q, I, [delta]) we call w [member of] [I.sup.*] a reset word if

[absolute value of [delta](Q,w)] = 1.

If such a word exists, we call the automaton synchronizing. Note that each word having a reset word as a factor is also a reset word.

The Cerny conjecture, a longstanding open problem in automata theory, claims that each synchronizing automaton has a reset word of length at most [([absolute value of Q] - 1).sup.2]. There is a series of automata due to Cerny whose shortest reset words reach this bound exactly [4], but all known upper bounds lie in [OMEGA] ([[absolute value of Q].sup.3]). A tight bound has been established for various special classes of automata, see some of recent advances in [11, 16]. The best general upper bound of the length of shortest reset words is currently the following (ii): Theorem 1 ([12]). Any t-state synchronizing automaton has a reset word of length z(t), where

z(t) [less than or equal to] [[t.sup.3] - t]/6.

It is convenient to analyze synchronization as a process in discrete time. Having an automaton A = (Q, I, [delta]) and a word

w = [x.sub.1] ... [x.sub.[absolute value of w]]

with [x.sub.1], ..., [x.sub.[absolute value of w]] [member of] I fixed, we say that a state [delta] [member of] Q is active at time l [less than or equal to] [absolute value of w] if

s [member of] [delta](Q, [x.sub.1] ... [x.sub.l).

At time 0, before the synchronization starts, all states are active. As we apply the letters, the number of active states may decrease.

It is also very intuitive to consider activity markers. At time 0 there is an activity marker in each state. Whenever a letter x [member of] I is applied, each activity marker in state [delta] [member of] Q moves to [delta] (s, x). The state [delta] may become unmarked or receive incoming markers. A state is active if an only if it has an activity marker.

When the number of active states decreases to 1 at a time l, the synchronization is complete and the word [x.sub.1] ... [x.sub.l] is a reset word of A.

2.2 Road coloring

In this paper directed multigraphs are referred to as graphs. A graph is:

1. aperiodic if the lengths of its cycles do not have any nontrivial common divisor,

2. admissible if it is aperiodic and all its out-degrees are equal,

3. road colorable if its edges can be labeled such that a synchronizing deterministic finite automaton arises.

It is not hard to observe that any road colorable graph is admissible. In 1977 Adler, Goodwyn and Weiss

[1] conjectured that for strongly connected graphs the backward implication holds as well. Their question became known as the Road Coloring Problem and a positive answer was given in 2008 by Trahtman [17, 19]:

Theorem 2 (Road Coloring Theorem). Each strongly connected admissible graph is road colorable.

In the literature it is common to consider only strongly connected graphs since many general claims can be easily reduced to the corresponding claims about strongly connected cases. We do not admit such restriction explicitly, because in the scope of computational problems it does not seem very natural. However, all the results hold with the restriction as well. Especially the NP-completeness proofs have been made slightly more complicated in order to use only strongly connected graphs.

2.3 Parameterized complexity

In most of the paper we do not need to work with a formal definition of a parameterized problem. We see it as a classical decision problem where we consider some special numerical property (parameter) of each input. Parameterized complexity studies the way in which the hardness of an NP-complete problem depends on the parameter. A problem may remain NP-hard even if restricted to instances with a particular value of the parameter, or there may be a polynomial-time algorithm for each such value. In the second case, if the algorithm is the same (uniform) for all the values, the problem is said to lie in the class XP. Moreover, if the time-bounding polynomials for different values are all of the same degree, we get into the class FPT:

A parameterized problem is fixed-parameter tractable (FPT) if there is an algorithm that solves it in time

f(P) x r([absolute value of x]),

where x is the input string, P [member of] N is the parameter of x, r is an appropriate polynomial, and f is any computable function. If there is more than one possible parameter for a problem, one may consider combinations of parameters. A problem is FPT with respect to parameters P, Q if it is decidable in time

f (P,Q) x r([absolute value of x]).

This is typically much less restrictive condition than the previous one, where f depends only on P.

There is a hierarchy of problems (the W-hierarchy) lying in XP but possibly outside FPT. It consists of the classes W[1], W[2], ...:

FPT [subset or equal to] W[1] [subset or equal to] W[2] [subset or equal to] ... [subset] XP. (1)

Since it has been conjectured that all the inclusions are proper, it is common to use W[i]-hardness (with respect to an appropriate type of reduction) as the evidence of lying outside FPT. However, we do not need to define the W-hierarchy here since it is used only to formulate former results, not the new ones (see Tab. 1). See the textbook [6] for the definitions and many other great ideas of parameterized complexity.

A kernel of a parameterized problem is a polynomial-time procedure that transforms any input x with parameter [P.sub.x] to another input y with parameter [P.sub.y] such that both [absolute value of y] and [P.sub.y] are bounded by f ([P.sub.x]), where f is an arbitrary function. Having a kernel is equivalent to lying in FPT. If f is a polynomial, we get a polynomial kernel.

2.4 Studied problems

In this paper we work with two canonical computational problems related to synchronization (SYN) and road coloring (SRCP). The problems are defined as follows:

SYN Input: Automaton A = (Q, I, [delta]), k [member of] N Output: Is there w [omega] [I.sup.*] of length at most k such that [absolute value of [delta](Q, w)] = 1? Parameters: k, [absolute value of], t = [absolute value of I] SRCP Input: Alphabet I, admissible graph G = (Q, E) with out-degrees [absolute value of I], k [member of] N Output: Is there a coloring [delta] such that [absolute value of [delta](Q, w)] = 1 for some w [member of] [I.sup.*] of length at most k? Parameters: k, [absolute value of], t = [absolute value of Q]

We need the following basic facts related to SYN:

Theorem 3 ([4]). There is a polynomial-time algorithm that decides whether a given automaton is synchronizing.

Corollary 1. SYN, if restricted to the instances with k [greater than or equal to] z(t) = [[t.sup.3] - t]/6, is solvable in polynomial time.

Theorem 4 ([7]). Syn is NP-complete, even if restricted to automata with two-letter alphabets.

The results of this paper, as well as the former results of Femau, Heggemes, and Villanger [8, 9] and of the second author and Drewienkowski [13, 14] are summarized by Tables 1 and 2. We have filled all the gaps in the corresponding tables from [8, Sec. 3] and [13, Sec. 6]. This means that the multi-parameter analysis of SYN and SRCP is complete in the sense that NP-complete restrictions are identified and we know, under several standard assumptions, which parameterizations lie in FPT and which of them have polynomial kernels.

3 Parameterized Complexity of SYN

The following lemma, easy to prove using the construction of a power automaton, says that SYN lies in FPT if parameterized by the number of states:

Lemma 1 ([8, 15]). There exists an algorithm that solves SYN in time r(t, 111) x [2.sup.t] for an appropriate polynomial r.

But does there exist a polynomial kernel? In this section we use methods developed by Bodlaender et al. [2] to prove the following:

Theorem 5. If SYN parameterized by the number of states has a polynomial kernel, then PH = [[summation].sup.3.sub.p], where PH denotes the union of the entire polynomial hierarchy.

The claim PH = [[summation].sup.3.sub.p] means that polynomial hierarchy collapses into the third level, which is widely assumed to be false. The key proof method relies on composition algorithms. In order to use them immediately we introduce the formalization of our parameterized problem as a set of string-integer pairs:

[L.sub.SYN] = {(x,t) | x [member of] [[summation].sup.*] encodes an instance of SYN with t [member of] N states},

where [SIGMA] is an appropriate finite alphabet.

3.1 Composition algorithms

An or-composition algorithm for a parameterized problem L [subset or equal to] [[summation].sup.*] x N is an algorithm that

* receives as input a sequence (([x.sub.1], t), ..., ([x.sub.m], t)) with ([x.sub.i]; t) [member of] [[summation].sup.*] x [N.sup.+] for each 1 [less than or equal to] i [less than or equal to] m,

* uses time polynomial in [[summation].sup.m.sub.i=1] [absolute value of [x.sub.i]] + t

* outputs (y, t') [subset or equal to] [[summation].sup.*] x [N.sup.+] with

1. (y, t') [member of] L [??] there is some 1 [less than or equal to] i [less than or equal to] m with ([x.sub.i]; t) [member of] L,

2. t' is polynomial in t.

Let L [subset or equal to] [[summation].sup.*] x [N.sup.+] be a parameterized problem. Its unparameterized version is

[??] = {z#[a.sup.t] |(x,t) [member of] L},

where [??] [not member of] [summation] is a special symbol.

Theorem 6 ([2]). Let L be a parameterized problem having an or-composition algorithm. Assume that its unparameterized version [??] is NP-complete. If L has a polynomial kernel, then PH = [[summation].sup.3.sub.p].

The unparameterized version of [L.sub.SYN] is computationally as hard as the classical SYN, so it is NP-complete. It remains only to describe an or-composition algorithm for [L.sub.SYN], which is done in the remainder of this section.

3.2 Preprocessing

Let the or-composition algorithm receive an input

(([A.sub.l], [k.sub.1]), t), ..., (([A.sub.m], [k.sub.m]),t)

consisting of t-state automata [A.sub.1], ..., [A.sub.m], each of them equipped with a number [k.sub.i]. Assume that the following easy procedures have been already applied:

* For each i = 1, ..., m such that [k.sub.i] [greater than or equal to] z(t), use the polynomial-time synchronizability algorithm from Corollary 1 to decide whether (([A.sub.i], [k.sub.i]), t) [member of] [L.sub.SYN]. If so, return a trivial true instance immediately. Otherwise just delete the i-th member from the sequence.

* For each i = 1, ..., m, add an additional letter [kappa] to [A.sub.i] such that [kappa] acts as the identical mapping: [[delta].sub.i](s, k) = s.

* For each i = 1, ..., m, rename the states and letters of [A.sub.i] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

After that, our algorithm chooses one of the following procedures according to the length m of the input sequence:

* If m [greater than or equal to] [2.sup.t], use the exponential-time algorithm from Lemma 1: denote D = [[summation].sup.m.sub.i=1] "=1 [absolute value of ([A.sub.i], [k.sub.i])] + t, where we add lengths of descriptions of the pairs. Note that D [greater than or equal to] m [greater than or equal to] [2.sup.t] and that D is the quantity used to restrict the running time of or-composition algorithms. By the lemma, in time

[m.summation over (i=1)] r (t, [absolute value of [I.sub.i]]) x [2.sup.t] [less than or equal to] m x r (D, D) x [2.sup.t] [less than or equal to] [D.sup.2] x r (D, D)

we are able to analyze all the m automata and decide if some of them have a reset word of the corresponding length. It remains to output some appropriate trivial instance ((A', k'), t').

* If m < [2.sup.t], put q(m) = [??]log (m + 1)[??]. It follows that q(m) [less than or equal to] t + 2. On the output of the or composition algorithm we put ((A', k'), t'), where A' is the automaton described in the following paragraphs and

d' = z(t) + 1

is our choice of the maximal length of reset words to be found in A'.

3.3 Construction of A' and its ideas

Here we describe the automaton A' that appears in the output of our or-composition algorithm. We set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The letters from [[universal].sup.m.sub.i=1] act on the states 1, ..., t in the following way:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for each [delta] [member of] {1, ...,t}, i [member of] {1, ..., m}, [a.sub.i,j] [member of] [I.sub.i]. In other words, we let all the letters from all the automata [A.sub.1], ..., [A.sub.m] act on the states 1, ..., t just as they did in the original automata. The additional letters act on 1, ..., t simply as well:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for each s, [bar.s] [member of] {1, ..., t}, i[member of]{1,..., m}. The state D is a sink state, which means that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for each y [member of] I'. Note that any reset word of A' has to map all the states of Q' to D.

The remaining 2 x (z(t) + 1) x (q(m) + 1) states form what we call a guard table. Its purpose is to guarantee that:

(C1) Any reset word of A' has to be of length at least k' = z(t) + 1.

(C2) Any reset word w of A' having length exactly z(t) + 1 is of the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

for some [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a reset word of [A.sub.i].

(C3) Any word w

* of length k' = z(t) + 1,

* of the form (2),

* and satisfying [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], is a reset word of A'.

If the guard table manages to guarantee these three properties of A', we are done: It is easy to check that they imply all the conditions given in the definition of a composition algorithm. So, let us define the action of the letters from I' on the states from {0, ..., z(t)} x {0, ..., q(m)} x {T, F}. After that A' will be complete and we will check the properties C1, C2, C3.

The actions of [[alpha].sub.1], ..., [[alpha].sub.m] should meet the following two conditions:

* Any reset word w of length z(t) + 1 has to start with some [[alpha].sub.i].

* After applying the first letter [[alpha].sub.i] there must occur at least z(t) - 1 consecutive letters from [I.sub.i]. Informally, by applying [[alpha].sub.i] we choose the automaton [A.sub.i].

How to do that? The number m may be quite large and each of [[alpha].sub.1], ..., [[alpha].sub.m] needs to have a unique effect. The key tool is what we call activity patterns. Let us work with the set

R = {0, ..., q(m)},

which matches ,,half of a row" of the guard table. Subsets of R correspond in a canonical way to binary representations of numbers 0, ..., [2.sup.q(m)+1] - 1. We will actually represent only the numbers 1,..., m. These does not include any of the extreme values corresponding to the empty set and whole R, because we have m < [2.sup.q(m)+1] - 1. Let the mapping

b : {1, ..., m} [right arrow] [2.sup.R]

assign the corresponding subset of R to a number. For instance, it holds that

b(11) = {0, 1, 3}

because 11 = [2.sup.0] + [2.sup.1] + [2.sup.3]. For each i [member of] {1, ..., m} we define specific pattern functions

rng [[pi].sup.T.sub.i], rng [[pi].sup.F.sub.i]: R [right arrow] R

such that

rng [[pi].sup.T.sub.i] = b(i), rng [[pi].sup.T.sub.i] = R\b(i)

for each i. It is irrelevant how exactly rng [[pi].sup.T.sub.i] and rng [[pi].sup.F.sub.i] are defined. It is sure that they exist, because the range is never expected to be empty. The action of the letters [[alpha].sub.1], ..., [[alpha].sub.m] is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

for each i[member of]{1, ..., m}, h [member of] {0, ..., z(t)}, and p [member of] R.

Note that each [[alpha].sub.i] maps the entire guard table, including row 0, into row 1. In fact, all ,,downward" transitions within the guard table will lead only one row down and the only transitions escaping from the guard table will lead from the bottom row. Thus, any reset word will have length at least k' = z(t) + 1. Moreover, during its application, at time l the rows 0, ..., l - 1 will have to be all inactive. This is a key mechanism that the guard table uses for enforcing necessary properties of short reset words.

Let us define how the letters [a.sub.ij] act on the guard table. Choose any i [member of] {1, ..., m}. The action of [a.sub.i,j] within the guard table does not depend on j. All the letters coming from a single automaton act identically here:

* for the rows h [member of] {1, ..., [k.sub.i]] we set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

* for the remaining rows h [member of] {0} [union] {[k.sub.i] + 1, ..., z(t)] we set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Recall that sending an activity marker along any transition ending in the row 0 is a ,,suicide". A word that does this cannot be a short reset word. So, if we restrict ourselves to the letters from some [I.sub.i], the transitions defined above imply that the forthcoming letter can be [a.sub.i,j] only at times 1, ..., [k.sub.i]. In the following z(t) - [k.sub.i] - 1 steps the only letter from Ii that can be applied is [kappa].

The letter [kappa] maps all the states of the guard table simply one state down, except for the rows 0 and z(t).

Set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for each h [member of] {1, ..., z(t) - 1], and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It remains to describe the actions of the letters [[omega].sub.i], ..., [[omega].sub.t] on the guard table. Set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for each p [member of] R, [delta] [member of] {1, ..., t], and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for each h [member of] {0, ..., z(t) - 1], p [member of] R, and [delta] [member of] {1, ..., t]. Now the automaton A' is complete.

3.4 An example

Consider an input consisting of m = 12 automata [A.sub.1], ..., [A.sub.12], each of them having t = 4 states. Because z(4) = 10 and q(12) = 3, the output automaton A' has 93 states in total. In Fig. 1 all the states are depicted, together with some of the transitions. We focus on the transitions corresponding to the automaton [A.sub.6], assuming that [k.sub.6] = 5.

The action of [[alpha].sub.6] is determined by the fact that 6 = [2.sup.1] + [2.sup.2] and thus

rng = [[pi].sup.T.sub.6] = b(6) = {1, 2}, rng [[pi].sup.F.sub.6] = R\b(6) = {0, 3}.

If the first letter of a reset word is [[alpha].sub.6], when applied, only the states

(1, 1, T), (1, 2, T), (1, 0, F), (1, 3, F)

remain active within the guard table. Now we need to move their activity markers one row down in each of the following z(t) - 1 = 9 steps. The only way to do this is to apply [k.sub.6] = 5 letters of [I.sub.6] and then z(t) - 1 - [k.sub.6] =4 occurrences of [kappa]. Then we are allowed to apply one of the letters [[omega].sub.1], ..., [[omega].sub.t]. But before that time there should remain only one active state [delta] [member of] {1, ..., t}, so that we could use [[omega].sub.s]. The letter [kappa] does not affect the activity within {1, ..., t} so we need to synchronize these states using [k.sub.6] = 5 letters from [I.sub.6].

So, any short reset word of A' starting with [[alpha].sub.6] has to contain a short reset word of [A.sub.6].

3.5 The guard table works

It remains to use the ideas informally outlined in Sec. 3.3 to prove that A' has the properties C1, C2, and C3 from Sec. 3.3.

Proof C1: As it has been said, for each x [member of] I' and each state (h,p, Q), where Q [member of] {T, F} and h [member of] {0,..., z(t) - 1}, it holds that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where h' < h or h' = h + 1. So the shortest paths from the row 0 to the state D have lengths at least z(t) + 1.

Proof C2: We should prove that any reset word w having length exactly z(t) + 1 is of the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a reset word of [A.sub.i]. The starting [[alpha].sub.1] is necessary, because [[alpha].sub.1], ..., [[alpha].sub.m] are the only letters that map states from the row 0 to other rows. Denote the remaining z(t) letters of w by [y.sub.1], ..., [y.sub.z(t)].

Once an [[alpha].sub.i] is applied, only [absolute value of R] = q(m) + 1 active states in the guard table remain. All of them are in the row 1, depending on i. The active states are exactly from

{1} x b(i) x {T} and {1} x R\b(i) x {F},

because this is exactly the range of [[alpha].sub.i] within the guard table. Let us continue by an induction. We claim that for 0 [less than or equal to] [tau] [less than or equal to] [k.sub.i] it holds what we have already proved for [tau] = 0:

1. If [tau] [greater than or equal to] 1, the letter [y.sub.[tau]] lies in [I.sub.i]. Moreover, if [tau] > [k.sub.i], it holds that [w.sub.[tau]] = [kappa].

2. After the application of [y.sub.[tau]] the active states within the guard table are exactly from

{[tau] + 1} x b(i) x {T} and {[tau] + 1} x R\b(i) x {F}.

For [tau] = 0 both claims hold. Take some 1 [less than or equal to] [tau] [less than or equal to] [k.sub.i] and suppose that the claims hold for [tau] - 1. Let us use the second claim for [tau] - 1 to prove the first claim for [tau]. All the states from

{[tau]} x b(i) x {T} and {[tau]} x R\b(i) x {F}

are active. Which letter may appear as [y.sub.T]? The letters [[omega].sub.1], ..., [[omega].sub.t] and [[alpha].sub.1], ..., [[alpha].sub.m] would map all the active states to rows 0 and 1, which is a contradiction. Consider any letter [[alpha].sub.l,j] for l [not equal to] i. It holds that b(i) [not equal to] b(l), so there is some p [member of] R lying in their symmetrical difference. For such p it holds that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

or

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This necessarily activates some state in the row 0, which is a contradiction again. So, [y.sub.[tau]] [member of] [I.sub.i]. Moreover, if [tau] > [k.sub.i], the letters from [I.sub.i]\ {[kappa]} map the entire row [tau] into the row 0, so the only possibility is [y.sub.[tau]] = [kappa].

The letter [y.sub.[tau]] maps all the active states right down to the row [tau] + 1, so the second claim for [tau] holds as well.

Proof C3: It is easy to verify that no,,suicidal" transitions within the guard table are used, so during the application of

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

the activity markers just flow down from the row 1 to the row z(t). Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a reset word of [A.sub.i], there remains only one particular state [delta] within {1, ..., t}. Finally, the letter [[omega].sub.s] is applied that maps [delta] and the entire row z(t) directly to D.

4 Parameterized Complexity of SRCP

4.1 Parameterization by the number of states

We point out that SRCP parameterized by the number of states has a polynomial kernel, so it necessarily lies in FPT.

Theorem 7. There is a polynomial kernel for SRCP parameterized by t = [absolute value of Q].

Proof: The algorithm takes an instance of SRCP, i.e., an alphabet I, an admissible graph [member of] = (Q, E) with out-degrees [absolute value of I], and a number k [member of] N. It produces another instance of size depending only on t = [absolute value of Q]. If k [greater than or equal to] z(t), we just solve the problem using Corollary 1 and output a trivial instance. Otherwise the output instance is denoted by I', G' = (Q', E'), k', where

Q' = Q,

k' = k,

[absolute value of I'] = min {[absolute value of I], t x (z(t) - 1)},

and the algorithm just deletes appropriate edges in order to reduce the out-degree to [absolute value of I']. Let us use a procedure that:

* takes an admissible graph with out-degree d > t x (z(t) - 1)

* for each of its vertices:

--finds an outgoing multiedge with the largest multiplicity (which is at least z(t)),

--deletes one edge from the multiedge.

Clearly the resulting graph has out-degree d - 1. We create the graph G' by repeating this procedure (starting with G) until the out-degree is at most t x (z(t) - 1).

Now we claim that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The upward implication is trivial since any coloring of G' can be extended to [member of] and the appropriate reset word can be still used. On the other hand, let us have a coloring [delta] of [member of] such that [absolute value of [delta](Q, w)] = 1 for a word w of length at most k < z(t), so it uses at most z(t) - 1 letters from I. If we delete from [member of] all the edges labeled by non-used letters, we get a subgraph of G' because during the reduction of edges we have reduced only multiedges having more than z(t) - 1 edges. So we are able to color G' according to the used letters of [member of] and synchronize it by the word w.

Corollary 2. SRCP parameterized by t = [absolute value of Q] lies in FPT.

4.2 Restriction to [absolute value of 1] = 2 and k = 3

Here we prove that SRCP restricted to [absolute value of I] = 2 and k = 3 is decidable in polynomial time. If [member of] = (Q, E) is a graph, by [V.sub.i](q) we denote the set of vertices from which there is a path of length i leading to q and there is no shorter one. For any w [member of] [I.sup.*] by [G.sub.w] we denote the set of graphs with outdegree 2 that admit a coloring [delta] such that [delta](Q, w) = {q} for some q [member of] Q.

Lemma 2. A graph [member of] = (Q, E) lies in [G.sub.aaa] if and only if there is a state q [member of] Q such that (q, q)[member of] E and there is a path of length at most 3 from each r [member of] Q to q.

Proof: If there exists a coloring [delta] with [delta](Q, aaa) = {q}, both claims follow immediately. On the other hand, if the loop (q, q) and all the paths leading to q are colored by a, we obtain a suitable coloring.

Lemma 3. Let [member of] = (Q, E) [member of] [G.sub.abb]\[G.sub.aaa]. Then at least one of the following two conditions holds:

1. There is a vertex q [member of] Q such that each vertex has an outgoing edge leading to [V.sub.2] (q).

2. G [member of] [G.sub.aba].

Proof: Let [member of] = (Q, E) [member of] [G.sub.abb]\[G.sub.aaa]. Thus [member of] admits a coloring [delta] such that

[delta](Q, abb) = {q}

for q [member of] Q.

* If [delta] satisfies q [not member of] [delta](Q, a), each edge labeled by a has to lead to [V.sub.2] (q). Indeed:

--It cannot lead to q due to q [not member of] [delta](Q, a).

--It cannot lead to any r [member of] [V.sub.1] (q) because in such case, using q [member of] [delta](Q, a), it would hold that [delta](r, b) = q and thus q [member of] [delta] (Q, ab). Hence, it would be necessary that [delta] (q, b) = q. According to Lemma 2, a loop on q guarantees that G [member of] [G.sub.aaa], which is a contradiction.

--It cannot lead to [V.sub.3](q), because there is no path of length 2 from [V.sub.3](q) to q.

Thus, the condition (1) holds.

* Otherwise the coloring [delta] satisfies q [member of] [delta](Q, a). Put

W = {s [member of] Q | [delta](s, b) = q}.

Now define another coloring [delta]' by switching the colors of the two edges leaving each state of W. Elsewhere, [delta]' and [delta] coincide. We claim that

[delta]'(Q, aba) = {q}

and so the condition (2) holds. Indeed:

--Take [delta] [member of] [V.sub.3](q). In [delta] there is a path

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3)

Because [delta] [member of] [V.sub.3](q), it holds that t [member of] [V.sub.2](q) and u [member of] [V.sub.1](q). It follows that t [member of] W, u [member of] W and thus in [delta]' there is a path

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

--Take [delta] [member of] [V.sub.2](q). In [delta] there is a path (3).

* If t [member of] [V.sub.2] (q), we get again that t [member of] W, u [member of] W and thus there is a path (4) in [delta]'.

* Otherwise, we have t [member of] [V.sub.1](q). Because G [not member of] [G.sub.aaa], there is no loop on q, thus u [not equal to] q and t [not member of] W. But u [member of] W, so we get a path (4) again.

--Take s [member of] [V.sub.1](q). In [delta]' there is always an edge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], so we need [delta]'(q, ba) = q. Because we assume that q [member of] S(Q, a), there has to be a cycle [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [delta] for some r [member of] [V.sub.1](q). In [delta]' we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

--For [delta] = q we apply the same reasoning as for s [member of] [V.sub.2] (q).

Lemma 4. For each [member of] with outdegree 2 it holds that

G [member of] [G.sub.abb]\ ([G.sub.aba] [union] [G.sub.aaa])

if and only if

* it holds that G [member of] [G.sub.aba] [union] [G.sub.aaa], and

* there is a vertex q [member of] Q such that each vertex has an outgoing edge leading to [V.sub.2] (q).

Proof: The downward implication follows easily from Lemma 3. For the upward one we only need to deduce that G [member of] [G.sub.abb]. We construct the following coloring [delta]:

* The edges leading to [V.sub.2] (q) are labeled by a. If two such edges start in a common vertex, they are labeled arbitrarily.

* The other edges are labeled by b.

This works because from any state s [member of] [V.sub.2](q) there is an edge leading to some t [member of] [V.sub.1](q) and from t there is an edge leading to q. We have labeled both these edges by b. It follows that wherever we start, the path labeled by abb leads to q.

Theorem 8. SRCP with [absolute value of 1] = 2 and k = 3 lies in P.

Proof: Let the algorithm test the membership of a given graph [member of] for the following sets:

1. [G.sub.aaa],

2. [G.sub.aab]\[G.sub.aaa],

3. [G.sub.aba]\[G.sub.aaa],

4. [G.sub.abb]\([G.sub.aba] [union] [G.sub.aaa]).

For the sets 1, 2, 3 the membership is polynomially testable due to the results from [13]. Lemma 4 provides a polynomially testable characterization of the set 4. It is easy to see that a graph [member of] should be accepted if and only if it lies in some of the sets.

4.3 Restriction to [absolute value of I] = 2 and k = 4

Theorem 9. SRCP remains NP-complete if restricted to [absolute value of I] = 2 and k = 4.

Let us perform a reduction from 3-SAT. Consider a propositional formula of the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where

[C.sub.j] = [l.sub.i,1] [disjunction] [l.sub.i,2] [disjunction] [l.sub.i,3]

and

[l.sub.j,k] [member of] {[x.sub.1], ..., [x.sub.n], [bar.[x.sub.1]], ..., [bar.[x.sub.n]]}

for each j [member of] {1, ..., m} and k [member of] {1, 2, 3}.

We construct a directed multigraph [G.sub.[PHI]] = (Q, E) with

[absolute value of Q] = 5m + 3n + 8

states, each of them having exactly two outgoing edges. We describe Q as a disjoint union of the following sets:

Q = [C.sub.1] [union] ... [union] [C.sub.m] [union] [V.sub.1] [union] ... [union] [V.sub.n] [union] D,

where

[C.sub.j] = {[C.sub.j,0], [C.sub.j,1], [C.sub.j,2], [C.sub.j,3], [C.sub.j,4]}, [V.sub.i] = {[x.sub.i], [bar.[x.sub.i]], [W.sub.i]}, D = {[D.sub.0], ..., [D.sub.7]},

for each j [member of] {1, ..., m} and i [member of] {1, ..., n}. The parts [C.sub.j] correspond to clauses, the parts [V.sub.i] correspond to variables. In each [V.sub.i] there are two special states labeled by literals [x.sub.i] and [bar.[x.sub.i]]. All the edges of [G.sub.[PHI]] are defined by Figures 2, 3, 4.

Figure 5 gives the overall picture of [G.sub.[PHI]]. Let us prove that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The upward implication

Suppose that there is a labeling [delta] by letters a (solid) and b (dotted) such that

w = [y.sub.1] ... [y.sub.4] [member of] [{a, b}.sup.4]

satisfies

[absolute value of [delta](Q w)] = 1.

Let a be the first letter of w. By a k-path (resp. k-reachable) we understand a path of length exactly k (resp. reachable by a path of length exactly k).

Lemma 5. The synchronization takes place in [D.sub.4].

Proof: From [D.sub.1] only states from D are 4-reachable. From [D.sub.0] the only states within D that are 4-reachable are [D.sub.2], [D.sub.3], [D.sub.4]. From [C.sub.1,0] only [D.sub.4] is 4-reachable.

Lemma 6. All edges outgoing from states of D are labeled as in Figure 6.

Proof: Since [D.sub.4] is not 3-reachable from [D.sub.0] nor [D.sub.6], all the edges incoming to [D.sub.0] and [D.sub.6] are labeled by b. The remaining labeling follows easily.

Corollary 3. It holds that

w = [aba.sup.2].

Lemma 7. For each j = 1, ..., m we have

[delta]([C.sub.j], 0, ab) [member of] {[x.sub.1] ..., [x.sub.n]: [bar.[x.sub.1]],..., [bar.[x.sub.n]]}.

Proof: None of the other states 2-reachable from [C.sub.j,0] offers a 2-path leading to [D.sub.4].

Lemma 8. There are no j, l [member of] {1, ..., m} and i [member of] {1, ..., n} such that

[delta]([C.sub.j,0] ab) = [x.sub.i]

and

[delta] ([C.sub.l,0], ab) = [bar.[x.sub.i]].

Proof: If both [x.sub.i] and [bar.[x.sub.i]] are active after applying [y.sub.1][y.sub.2] = ab, there have to be 2-paths labeled by [a.sup.2] from both [x.sub.i], [bar.[x.sub.i]] to [D.sub.4]. It is easy to see that it is not possible to find such labeling.

Corollary 4. There is a partial assignment making all the literals

[delta]([C.sub.1,0], ab), [delta]([C.sub.2,0], ab), ..., [delta]([C.sub.m], 0, ab)

satisfied, because none of them is the negation of another. Each clause contains some of these literals.

We are done--the existence of a satisfying assignment is guaranteed.

The downward implication

For a given satisfying assignment we construct a coloring based on the above-mentioned ideas and the example given by Fig. 7.

* For each j, the coloring of edges outgoing from [C.sub.j,0], [C.sub.j,1], [C.sub.j,2] depends on which of the three literals of [C.sub.j] are satisfied by the assignment (the example assigns [x.sub.1] = 1, [x.sub.2] = 0, [x.sub.3] = 0, [x.sub.4] = 1). The 2-path from [C.sub.j,0] labeled by ab should lead to a state labeled by a satisfied literal. The edges outgoing from [C.sub.j,3] and [C.sub.j,4] are always colored in the same way.

* For each i, all the edges outgoing from the states of the [V.sub.i] part are colored in one of two ways depending on the truth value assigned to [x.sub.i].

* The edges outgoing from the states of D admit the only possible coloring.

Note that in our example the edges outgoing from the states of [V.sub.3] could be colored in the opposite way as well. None of the literals [x.sub.3], [bar.[x.sub.3]] is chosen by the coloring to satisfy a clause.

Strong connectivity

If there is a non-negated occurrence of each [x.sub.i] in [PHI]the graph [G.sub.[PHI]] is strongly connected. This assumption can be easily guaranteed by adding tautological clauses like [x.sub.i] [disjunction] [bar.[x.sub.i]] [disjunction] [bar.[x.sub.i]].

5 Further Research: SRCW

Part of the RSCP input consists of a prescribed length of a reset word that should be used in the road coloring. But what if an exact reset word or a set of possible reset words were prescribed? This problem is called SRCW:

SRCW Input: Alphabet I, admissible graph G = (Q, E) with-out degrees [absolute value of I] W [subset or equal to] [I.sup.*] Output: Is there a coloring [delta] such that [absolute value of [delta](Q, w)] = 1 for some w [member of] W?

In [22] we study SRCW with respect to fixed values of both [absolute value of I] and W. For [absolute value of I] = 2, singleton sets W that make the problem NP-complete are characterized. We also study the situation with the additional restriction to strongly connected graphs. We show that the complexity differs in the case [absolute value of I] = 2 and W = {abb}. However, with such restriction the characterization remains incomplete. There are also no results about non-binary alphabets and non-singleton sets W. The current state of art is mostly depicted in Tab. 3.

References

[1] Adler, R., Goodwyn, L., Weiss, B.: Equivalence of topological Markov shifts. Israel Journal of Mathematics 27(1), 49-63 (1977)

[2] Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. Journal of Computer and [delta]ystem Sciences 75(8), 423 434 (2009)

[3] Bonizzoni, P., Jonoska, N.: Regular splicing languages must have a constant. In: Mauri, G., Leporati, A. (eds.) Developments in Language Theory, Lecture Notes in Computer Science, vol. 6795, pp. 82-92. Springer Berlin Heidelberg (2011)

[4] Cerny, J.: Poznamka k homogennym experimentom s konecnymi automatmi. Matematickofyzikalny casopis 14(3), 208-216 (1964)

[5] Cerny, J., Piricka, A., Rosenauerova, B.: On directable automata. Kybernetica 7, 289-298 (1971)

[6] Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer-Verlag (2013), 763 pp.

[7] Eppstein, D.: Reset sequences for monotonic automata. SIAM J. Comput. 19(3), 500-510 (1990)

[8] Fernau, H., Heggernes, P., Villanger, Y.: A multivariate analysis of some DFA problems. In: Dediu, A.H., Martm-Vide, C., Truthe, B. (eds.) Language and Automata Theory and Applications, Lecture Notes in Computer Science, vol. 7810, pp. 275-286. Springer Berlin Heidelberg (2013)

[9] Fernau, H., Heggernes, P., Villanger, Y.: A multi-parameter analysis of hard problems on deterministic finite automata. Journal of Computer and [delta]ystem Sciences 81(4), 747 - 765 (2015)

[10] Gonze, F., Jungers, R.M., Trahtman, A.N.: A note on a recent attempt to improve the pin-frankl bound. CoRR abs/1412.0975 (2014)

[11] Grech, M., Kisielewicz, A.: The Cemy conjecture for automata respecting intervals of a directed graph. Discrete Mathematics & Theoretical Computer Science 15(3), 61-72 (2013)

[12] Pin, J.E.: On two combinatorial problems arising from automata theory. Annals of Discrete Mathematics 17, 535-548 (1983)

[13] Roman, A., Drewienkowski, M.: A complete solution to the complexity of synchronizing road coloring for non-binary alphabets. Information and Computation, in print (2015)

[14] Roman, A.: P-NP threshold for synchronizing road coloring. In: Dediu, A.H., Martm-Vide, C. (eds.) Language and Automata Theory and Applications, Lecture Notes in Computer Science, vol. 7183, pp. 480-489. Springer Berlin Heidelberg (2012)

[15] Sandberg, S.: Homing and synchronizing sequences. In: Broy, M., Jonsson, B., Katoen, J.P., Leucker, M., Pretschner, A. (eds.) Model-Based Testing of Reactive Systems, Lecture Notes in Computer Science, vol. 3472, pp. 5-33. Springer Berlin Heidelberg (2005)

[16] Steinberg, B.: The Cemy conjecture for one-cluster automata with prime length cycle. Theoret. Comput. Sci. 412(39), 5487-5491 (2011)

[17] Trahtman, A.: The road coloring problem. Israel Journal of Mathematics 172(1), 51-60 (2009)

[18] Trahtman, A.: Modifying the upper bound on the length of minimal synchronizing word. In: Owe, O., Steffen, M., Telle, J. (eds.) Fundamentals of Computation Theory, Lecture Notes in Computer Science, vol. 6914, pp. 173-180. Springer Berlin Heidelberg (2011)

[19] Trahtman, A.N.: The road coloring and Cemy conjecture. In: Holub, J., Zdarek, J. (eds.) Proceedings of the Prague Stringology Conference 2008. pp. 1-12. Czech Technical University in Prague, Czech Republic (2008)

[20] Travers, N., Crutchfield, J.: Exact synchronization for finite-state sources. Journal of Statistical Physics 145(5), 1181-1201 (2011)

[21] Volkov, M.: Synchronizing automata and the Cemy conjecture. In: Martm-Vide, C., Otto, F., Fernau, H. (eds.) Language and Automata Theory and Applications, Lecture Notes in Computer Science, vol. 5196, pp. 11-27. Springer Berlin Heidelberg (2008)

[22] Vorel, V., Roman, A.: Complexity of road coloring with prescribed reset words. In: Dediu, A.H., Formenti, E., Martm-Vide, C., Truthe, B. (eds.) Language and Automata Theory and Applications, pp. 161-172. Lecture Notes in Computer Science, Springer International Publishing (2015)

Vojtech Vorel (1) * and Adam Roman (2) ([dagger])

(1) Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic

(2) Institute of Computer Science, Jagiellonian University, Krakow, Poland

* Corresponding author. Email: vorel@ktiml.mff.cuni.cz. Supported by the Czech Science Foundation grant GA1410799S and the GAUK grant No. 52215.

([dagger]) Email: roman@ii.uj.edu.pl. Supported by the Polish Ministry of Science and Higher Education Iuventus Plus grant IP2012 052272.

(i) [delta]ome authors use other terms such as synchronizing word or directing word.

(ii) An improved bound published by Trahtman [18] in 2011 has turned out to be proved incorrectly, see [10].

received 9th July 2014, revised 14th Oct. 1998, accepted 8th Apr. 2015.

Tab. 1: Results of the complete multi-parameter analysis of SYN and SRCP. Diamonds mark the results of the present paper Parameter Parameterized Complexity Polynomial Kernel of SYN of SYN k W[2]-hard [8] -- [absolute value NP-complete for [absolute -- of I] value of I] = 2,3, ... [7] k and [absolute FPT, running time Not unless NP [subset or value of I] [O.sup.*] ([[absolute equal to] coNP/poly [8] value of I].sup.k]) [triv.] t FPT, running time Not unless PH collapses [O.sup.*]([2.sup.t]) [??] [triv.] Parameter Parameterized Complexity Polynomial Kernel of SRCP of SRCP k NP-complete for k = 4, -- 5, ... [13] [absolute value NP-complete for [absolute -- of I] value of I] = 2,3, ... [??] k and [absolute See Tab. 2 -- value of I] t FPT, running time Yes [??] [O.sup.*] ([2.sup. [absolute value of I]]) [??] Tab. 2: Complexity of SRCP restricted to particular values of k and [absolute value of I] k = 2 k = 3 k = 4, 5,... [absolute value of I] = 2 P [14] P [??] NPC [??] [absolute value of I] = 3 P [14] P [13] NPC [14] [absolute value of I] = 4, 5, ... P [14] P [13] NPC [14] Tab. 3: Complexity of SRCW restricted to fixed [absolute value of I], fixed singleton W, and with possible assumption of strong connectivity (S.C.). The results come from [13] and [22]. [absolute value [absolute value of I] = 2 of I] = 3,4, ... general S.C. general S.C. W = {[a.sup.k]} (k [greater P P P P than or equal to] i) W = {[a.sup.k]b} (k [greater P P P P than or equal to] i) W = {abb} NPC P ? ? W = {ava} (v [not member of] NPC NPC [a.sup.*]) other forms of W NPC ?

Printer friendly Cite/link Email Feedback | |

Author: | Vorel, Vojtech; Roman, Adam |
---|---|

Publication: | Discrete Mathematics and Theoretical Computer Science |

Article Type: | Report |

Date: | Jan 1, 2015 |

Words: | 8286 |

Previous Article: | Genus distributions of cubic series-parallel graphs. |

Next Article: | A note on a recent attempt to improve the Pin-Frankl bound. |

Topics: |