Sylvie Davies
email: sylvie.davies@uwaterloo.ca

Michal Hospodár

David R Cheriton

on Star-Free Languages

Keywords: Power, Positive Closure, and Complementation

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The state complexity of a regular language L, sc(L), is the smallest number of states in any deterministic finite automaton (DFA) recognizing the language L. The state complexity of a unary regular operation • is the function from N to N given by n → max{sc(L • ) | sc(L) ≤ n}. The nondeterministic state complexity of a regular language or a unary regular operation is defined analogously using the representation of languages by nondeterministic finite automata (NFAs).

The (nondeterministic) state complexity of star, reversal, square, power, and complementation was examined in [4, 6, 10-12, 14, 18]. Researchers also investigated the complexity of operations on some subregular classes. For example, Câmpeanu et al. [START_REF] Câmpeanu | State complexity of basic operations on finite languages[END_REF] considered finite languages, and Pighizzini and Shallit [START_REF] Pighizzini | Unary language operations, state complexity and Jacobsthal's function[END_REF] studied operational state complexity on unary regular languages.

The class of star-free languages is the smallest class containing finite languages and closed under complementation, union, and concatenation. In 1965, Marcel-Paul Schützenberger [START_REF] Schützenberger | On finite monoids having only trivial subgroups[END_REF] proved that a language is star-free if and only if its syntactic monoid is group-free, that is, it has only trivial subgroups. An equivalent condition is that the minimal DFA of a star-free language is permutationfree, that is, there is no string that induces a non-trivial permutation on any subset of the set of states.

The operational state complexity of basic regular operations on star-free languages represented by DFAs was examined by Brzozowski and Liu [START_REF] Brzozowski | Quotient complexity of star-free languages[END_REF], while Holzer, Kutrib, and Meckel [START_REF] Holzer | Nondeterministic state complexity of star-free languages[END_REF] considered basic operations on star-free languages represented by NFAs. Except for reversal on DFAs, all regular upper bounds have been shown to be met by star-free languages.

In this paper, we continue this research and study the state complexity and nondeterministic state complexity of square, power, positive closure, and complementation on star-free languages. As the main result of this paper, we get nontrivial upper and lower bounds for square on DFAs in Sect. 3. In Sect. 4, we obtain tight upper bounds for positive closure on DFAs and NFAs, and for power on unary DFAs and binary NFAs. Moreover, we present lower and upper bounds for complementation on unary NFAs that are better than in [START_REF] Holzer | Nondeterministic state complexity of star-free languages[END_REF].

Preliminaries

Let Σ be a finite non-empty alphabet of symbols. Then Σ * denotes the set of strings over Σ including the empty string ε. A language is any subset of Σ * .

A nondeterministic finite automaton (NFA) is a 5-tuple A = (Q, Σ, •, s, F ) where Q is a finite set of states, Σ is a finite alphabet, • : Q × Σ → 2 Q is the transition function which is naturally extended to the domain 2 Q × Σ * , s ∈ Q is the initial state, and F ⊆ Q is the set of final states. We say that (p, a, q) is a transition in NFA A if q ∈ p • a. The language accepted by the NFA A is the set

L(A) = {w ∈ Σ * | s • w ∩ F = ∅}.
An NFA A is a deterministic finite automaton (DFA) if |q • a| = 1 for each q in Q and each a in Σ. In a DFA, each symbol a in Σ induces a transformation on the set Q, given by q → q • a. We frequently describe the transitions of DFAs by just describing their induced transformations.

The state complexity of L, sc(L), is the smallest number of states in any DFA for L. The nondeterministic state complexity of L, nsc(L), is defined analogously. It is well known that if a language L is finite with the longest string of length , then sc(L) ≤ + 2 and nsc(L) ≤ + 1.

The reader may refer to [START_REF] Brzozowski | Large aperiodic semigroups[END_REF][START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF][START_REF] Sipser | Introduction to the theory of computation[END_REF][START_REF] Yu | Regular languages[END_REF] for details and all unexplained notions.

Square

In this section, we investigate the square operation on the class of star-free languages represented by DFAs. Let A = (Q, Σ, •, s, F ) be an arbitrary DFA. As is well known, we may construct a DFA B recognizing L(A) 2 as follows:

-The state set of B is Q × 2 Q , where 2 Q is the set of all subsets of Q. -The initial state of B is (s, ∅) if s ∈ F , or (s, {s}) if s ∈ F . -The final state set is F B = {(q, S) | S ∩ F = ∅}.
-The transition function is defined as follows for each a ∈ Σ:

(q, S) a = (q • a, S • a), if q • a ∈ F ; (q • a, S • a ∪ {s}), if q • a ∈ F .
To simplify the notation, we write (q, S)a instead of (q, S) a, and we write qa and Sa instead of q • a and S • a for each q in Q and each subset S of Q.

We will use the following lemma.

Lemma 1. Let q ∈ F and T ⊆ Q. Suppose (q, T ) is reachable via w in B. For each p ∈ T , there is a suffix x of w such that sx = p and f x = q for some f ∈ F .

Proof. Write w = w 1 • • • w k y where w 1 • • • w i is the i-th shortest prefix of w contained in L(A). Let z i = w i+1 • • • w k and z k = ε.
Then (s, ∅)w = (q, T ) = (q, {sz 1 y, sz 2 y, sz 3 y, . . . , sz k y}). Let x be z i y with sz i y = p and let

f = sw 1 • • • w i .
Upper Bound. For each q in Q, define the following set of states:

SCC(q) = {p ∈ Q | ∃x, y ∈ Σ * such that qx = p and py = q}.
The set SCC(q) is called the strongly connected component (SCC) of A containing q; it is the maximal set of states containing q such that for each state p in the set, there are directed paths leading from q to p and from p to q. Of particular importance is the component SCC(s) containing the initial state s.

Proposition 2. Let A be a DFA of a star-free language in which all states are reachable. Consider the number of reachable states in the DFA B for L(A)

(n -1)2 n -2(n -2 -j) -j2 n-i+1 .
The maximum value of these bounds is (n -1)2 n -2(n -2), corresponding to case (3) with either j = 0 or i = n.

Proof. Statement (1) holds true since only states of the form (q, {q}) are reachable. For (2), suppose SCC(s) = {s}. The initial state of B in this case is either (s, ∅) or (s, {s}). Let a be a letter and let sa = q. If q = s then (s, ∅)a = (s, ∅) and (s, {s})a = (s, {s}), so no new states are reached. If q = s, we reach (q, ∅) or (q, {q}) if q is non-final, and we reach (q, {s}) or (q, {q, s}) if q is final. If q = s, then q ∈ SCC(s), so we can never return to a state with s in the first component. Thus all non-initial states with s in the first component are unreachable. Now consider states (q, S) with q = s. If q is non-final, there are at most 2 n reachable states of the form (q, S). If q is final, there are at most 2 n-1 reachable states of the form (q, S), since S must contain s. Let |F | = k, and note:

-If s ∈ F , there are at most (n -k)2 n + (k -1)2 n-1 + 1 reachable states.

-If s / ∈ F , there are at most (n -k -1)2 n + k2 n-1 + 1 reachable states.

Both values are maximized by taking k as small as possible:

-If s ∈ F , we cannot take k = 1 or else we are in case (1) (since then s is the unique final state of automaton A), so taking k = 2 we get the upper bound (n -2)

2 n + 2 n-1 + 1. -If s / ∈ F , taking k = 1 gives (n -2)2 n + 2 n-1 + 1 again.
Now, we consider (3). Let q be a non-final state in SCC(s). Let T be a set that contains SCC(s) \ {q}. We claim that (q, T ) is unreachable.

Suppose for a contradiction that (q, T ) is reachable. Then there is a state (p, U ) and letter a such that (p, U )a = (q, T ). Since q is non-final, we have pa = q and U a = T . Notice that U a contains SCC(s)\{q}, since T contains SCC(s)\{q}. Construct a subset V of U as follows:

for each element u ∈ SCC(s) \ {q}, choose one element v ∈ U such that va = u. Then |V | = |SCC(s) \ {q}|.
If v ∈ V , we have va ∈ SCC(s) \ {q}, so there is a path from v to the initial state s. Since all states of A are reachable, there is also a path from s to v. Therefore v belongs to SCC(s). It follows that

V ⊆ SCC(s). Since |V | = |SCC(s) \ {q}|, we must have V = SCC(s) \ {r} for some state r ∈ SCC(s). Then (SCC(s) \ {r})a = (SCC(s) \ {q}).
We claim that r = p. To see this, first note that p must be in SCC(s). Indeed, there is a path from s to p since all states of A are reachable, and there is a path from p to s since pa = q and q ∈ SCC(s). Now, if r = p, then p ∈ V = SCC(s) \ {r}. But then q ∈ V a, which is impossible since V a = SCC(s) \ {q}. It follows that r = p and thus V = SCC(s) \ {p}.

Thus we have pa = q and (SCC(s) \ {p})a = SCC(s) \ {q}. But this means that a acts as a permutation on SCC(s). Since L(A) is star-free, a must act as the identity on SCC(s). Therefore p = q and V = SCC(s) \ {q}.

This means that if T contains SCC(s) \ {q}, then the state (q, T ) only has immediate predecessors (that is, states from which (q, T ) can be reached in one transition) of the form (q, U ), where U contains a subset V = SCC(s) \ {q}. We claim that either SCC(s) = {s}, or all states (q, T ) with SCC(s) ⊆ T are unreachable. Indeed, consider a path leading from the initial state to (q, T ). If q = s, then (q, T ) is unreachable since every state in the path must have q as the first component. If q = s, then the second component of the initial state which is either (s, ∅) or (s, {s}) must contain SCC(s) \ {s}, and this occurs only if SCC(s) = {s}. If SCC(s) = {s}, we are in case [START_REF] Brzozowski | Large aperiodic semigroups[END_REF], which has been dealt with. Thus if SCC(s) ⊆ T , then (q, T ) is unreachable, as required.

We can also show that if q ∈ SCC(s) is non-final, then the states (q, Q) and (q, Q\{q}) are not reachable. Indeed, suppose we have (p, S)a = (q, Q\{q}). Since q is non-final, we have pa = q and Sa = Q \ {q}. Note that S cannot contain p, since otherwise Sa would contain q. Also, we must have |S| ≥ |Q\{q}|. It follows that S = Q \ {p}. But then pa = q and (Q \ {p})a = Q \ {q}, so a is a permutation of Q and thus the identity. Then p = q and S = Q \ {q}, meaning (p, S) = (q, Q \ {q}). Thus our target state (q, Q \ {q}) can only be reached from itself, so it is unreachable. A similar argument shows that (q, Q) is unreachable. Now we count the number of potentially reachable states in this case. Consider a state (q, S). If q is final, then S must contain s, and so for each final state q we get 2 n-1 potentially reachable states. For each non-final state q, we have an upper bound of 2 n reachable states (q, S). If |F | = k, this gives a total upper bound of (n -k)2 n + k2 n-1 . But we can get a better bound, since we know that if q ∈ SCC(s) is non-final and S contains SCC(s) \ {q}, then (q, S) is not reachable. For each of the j non-final states q ∈ SCC(s), there are 2 n-i+1 unreachable states (q, S) such that S contains SCC(s) \ {q}.

For each of the n -k -j non-final states q ∈ SCC(s), there are 2 unreachable states (q, Q) and (q, Q \ {q}). Subtracting these states gives an upper bound of (n -k)

2 n + k2 n-1 -2(n -k -j) -j2 n-i+1 .
If we plug in k = 2 here, we get the stated upper bound. If we plug in k ≥ 3 we get something smaller than the stated upper bound. However, for k = 1 we get something larger than the stated bound, so we need to do some extra work.

Suppose |F | = k = 1, and set F = {q}. We can assume q = s since otherwise we are in case [START_REF] Brzozowski | Quotient complexity of star-free languages[END_REF]. Since s ∈ F , the initial state of the square DFA is (s, ∅). We claim states (s, S) with q ∈ S are not reachable.

To see this, suppose for a contradiction that a state (s, S) with q ∈ S is reachable. To reach (s, S) we must first pass through some reachable state of the form (q, T ). So there exists a string y such that qy = s and T y = S. Choose p ∈ T such that py = q. Let w be a string leading from the initial state to (q, T ). Then by Lemma 1, there exists a suffix x of w such that sx = p and qx = q. Now sxy = py = q and qxy = qy = s, so the string xy swaps s and q. This is a contradiction, since L(A) is star-free.

So let us take our previous bound of (n-k)2 n +k2 n-1 -2(n-k-j)-j2 n-i+1 , set k = 1, and subtract these new states we have proved to be unreachable. There are 2 n-1 states (s, S) with q ∈ S. However, we have already counted the states (s, Q) and (s, Q \ {s}) as not reachable, so instead of subtracting 2 n-1 we subtract 2 n-1 -2. Thus we get (n-1)

2 n +2 n-1 -2(n-1-j)-j2 n-i+1 -2 n-1 +2 = (n -1)2 n -2(n -2 -j) -j2 n-i+1 , as required.
Lower Bound. For n ≥ 4, we define a function f (n) as follows. Let k = n/2 . For 0 ≤ i ≤ n-1, define d(i) = min{|k-1-i|, |k+1-i|}. Define a function g(n, i) as follows:

g(n, i) =                2 n -2, if i = k; 2 n-1 , if i ∈ {k -1, k + 1}; 2 n -2 k-d(i) d(i) j=1 k+1+d(i) k+1+j , if n is odd, i / ∈ {k -1, k, k + 1}; 2 n -2 k-d(i) d(i) j=1 k+d(i) k+j , if n is even, i < k -1; 2 n -2 k-1-d(i) d(i) j=1 k+1+d(i) k+1+j , if n is even, i > k + 1. (1)
Now set f (n) = n-1 i=0 g(n, i). We claim that f (n) is a lower bound on the state complexity of the square of a star-free language with state complexity n. Based on the results of computational random searches, we conjecture that this lower bound is tight, but we were unable to prove a matching upper bound.

Our witness for this lower bound is the DFA A defined as follows. Fix n ≥ 4 and let Q = {0, 1, . . . , n -1}. A transformation t of Q is monotonic if p ≤ q implies pt ≤ qt for all p, q ∈ Q. Let Σ be the set of all monotonic transformations of Q. By [9, Theorem 2.1], we have |Σ| = 2n-1 n-1 . Let k = n/2 as before. Finally, let A = (Q, Σ, •, k, {k -1, k + 1}) be the DFA where q • t = qt for all t ∈ Σ. Theorem 3. Let n ≥ 4, define A as above, and let B be the DFA for the square L(A) 2 . The number of reachable and pairwise distinguishable states of B is precisely f (n).

Proof. We claim that the function g(n, i) counts the number of reachable states of B with the form (i, S), for i ∈ Q and S ⊆ Q. Thus the total number of reachable states is given by f (n), which takes the sum of the g(n, i) terms for each i ∈ Q. We must prove that the counting function g(n, i) is correct, and also that all of the reachable states we count are pairwise distinguishable.

The initial state of B is (k, ∅). First we show that the states (k, {k -j}) and (k, {k+j}) are reachable for each j ≥ 2 such that the state in question is in Q. From the initial state, apply the transformation (k → k -1) to reach (k -1, {k}). Now apply the transformation which sends k-1 to k, fixes everything below k-1, and sends everything above k -1 to k + j. We reach (k, {k + j}). Symmetrically, from the initial state, apply (k → k + 1) to reach (k + 1, {k}). Then apply the transformation that sends k + 1 to k, fixes everything above k + 1, and sends everything below k + 1 to k -j. We reach (k, {k -j}).

Next, we show that (k, {k-2, k-3, . . . , 0}) and (k, {k+2, k+3, . . . , n-1}) are reachable. Assume we have reached (k, {k -2, k -3, . . . , k -j}) for some j ≥ 2. Apply (k → k + 1) to reach (k + 1, {k, k -2, k -3, . . . , k -j}). Then apply the transformation that fixes 0 and every q ≥ k +2, sends k +1 to k, sends k to k -2, and sends q to q-1 if 1 ≤ q ≤ k-1 . We reach (k, {k-2, k-3, . . . , k-j-1}) and by applying these two transformations repeatedly we reach (k, {k -2, k -3, . . . , 0}). A symmetric argument works for (k, {k + 2, k + 3, . . . , n -1}).

Next, we show the following states are reachable:

(k-1, Q), (k-1, Q\{k-1}), (k + 1, Q), (k + 1, Q \ {k + 1}). From (k, {k -2, k -3, . . . , 0}), apply (k → k -1) to reach (k -1, {k, k -2, k -3, . . . , 0}). Repeatedly apply (k → k + 1 → • • • → n -2 → n -1) to reach (k -1, Q \ {k -1}). Then apply (k → k -1) to reach (k-1, Q).
Symmetrically, we can reach (k+1, Q\{k+1}) and then (k+1, Q).

Next, we describe how to reach states of the form (q, S) where S satisfies certain properties. For each q, we define:

S <q = {p ∈ S | p < q}, S >q = {p ∈ S | p > q}, S q = S ∩ {q}.
Then S is the disjoint union S <q ∪ S q ∪ S >q . We claim that (q, S) is reachable if one of the following conditions holds:

1. n is odd, |S <q | ≤ min{q, k + 1}, and |S >q | ≤ min{n -q -1, k -1}. 2. n is odd, |S <q | ≤ min{q, k -1}, and |S >q | ≤ min{n -q -1, k + 1}. 3. n is even, |S <q | ≤ min{q, k + 1}, and |S >q | ≤ min{n -q -1, k -2}. 4. n is even, |S <q | ≤ min{q, k -1}, and |S >q | ≤ min{n -q -1, k}.
Additionally, if q is a final state (k -1 or k + 1) then S must contain the initial state k.

To see this, first observe that S <q always has size at most q and S >q always has size at most n -q -1; no sets exist which do not satisfy these bounds. Now suppose condition (1) holds; then n is odd and n = 2k + 1. Observe that Q <k+1 has size k + 1 and

Q >k+1 has size n -(k + 1) -1 = 2k + 1 -k -1 -1 = k -1. Since |S <q | ≤ k + 1 and |S >q | ≤ k -1,
there is a monotonic transformation that sends Q <k+1 to S <q and Q >k+1 to S >q ; we can define the transformation as follows: For i in Q <k+1 , map i to the (i + 1)-th smallest element of S <q , or to the largest element of S <q if i + 1 > |S <q |. For i ∈ Q >k+1 , map i to the (i -(k + 1))-th smallest element of S >q , or to the largest element of S >q if i-(k+1) > |S >q |. Finally, k+1 is mapped to q. If S contains q, reach (k+1, Q) and apply this transformation to reach (q, S). Otherwise, reach (k+1, Q\{k+1}) and apply this transformation to reach (q, S).

If condition ( 2), ( 3) or (4) holds, we use symmetric arguments. For condition (2), observe that Q <k-1 has size k -1 and Q >k-1 has size k + 1. Since the condition implies |S <q | ≤ k -1 and |S >q | ≤ k + 1, there is a monotonic transformation that sends Q <k-1 to S <q and Q >k-1 to S >q , defined analogously to the transformation before. For condition [START_REF] Câmpeanu | State complexity of basic operations on finite languages[END_REF],

Q <k+1 has size k + 1, but since n = 2k is even, the set Q >k+1 has size n -(k + 1) -1 = 2k -k -1 -1 = k -2. For condition (4), Q <k-1 has size k -1 and Q >k-1 has size k.
This argument shows that all states (q, S) which satisfy the four conditions described above (and satisfy k ∈ S if q is final) are reachable. Now we count the number of states satisfying these conditions.

Case 1: States of the form (k -1, S). Note that S <k-1 has size at most k -1. If n is odd, then S >k-1 has size at most k + 1. If n is even, then S >k-1 has size at most k. So for all S, either condition (2) or condition (4) is satisfied. Also, since k -1 is final, S must contain the initial state k. Thus every state (k -1, S) with k ∈ S is reachable; there are 2 n-1 such states.

Case 2: States of the form (k + 1, S). One may verify that for all S, either condition (1) or condition (3) is satisfied. Since k + 1 is final, S must contain k. Thus every state (k + 1, S) with k ∈ S is reachable; there are 2 n-1 such states. So there are only two choices for S that do not meet a reachability condition: Q and Q \ {k}. Thus there are 2 n -2 reachable states of the form (k, S).

Case 4: States of the form (q, S), q < k -1. Write q = k -1 -d with d ≥ 1. Then S <q has size at most k-1-d. If n is odd, then S >q has size at most k+1+d.

If n is even, then S >q has size at most k + d. We always have

|S <q | ≤ k + 1. If n is odd, then condition (2) is met as long as |S >q | ≤ k + 1.
If n is even, then condition (4) is met as long as |S >q | ≤ k. Let us count the number of sets S which fail these conditions.

Write S as the disjoint union S <q ∪S q ∪S >q . There are 2 k-1-d choices for S <q and 2 choices for S q . If n is odd, to fail condition (2), we need |S >q | = k + 1 + j for some j with 1 ≤ j ≤ d. For each j, there are k+1+d k+1+j choices for S >q ; to get the total we sum over j. So when n is odd, there are 2 k-d (

d j=1 k+1+d k+1+j ) choices for S.
If n is even, to fail condition (4), we need |S >q | = k + j for some j such that 1 ≤ j ≤ d. For each j, there are k+d k+j choices for S >q . Summing over j, when n is even, there are 2 k-d ( d j=1 k+d k+j ) choices for S. Case 5: States of the form (q, S), q > k + 1. Write q = k + 1 + d with d ≥ 1. Then S <q has size at most k+1+d. If n is odd, then S >q has size at most k-1-d.

If n is even, then S >q has size at most k -2 -d. We always have

|S >q | ≤ k -2. Thus condition (1) (if n is odd) or (3) (if n is even) is met as long as |S <q | ≤ k+1.
We count the number of sets that fail these conditions.

Write S as the disjoint union S <q ∪ S q ∪ S >q . If n is odd, there are 2 k-1-d choices for S >q . If n is even, there are 2 k-2-d choices for S >q . There are two choices for S q . To fail condition (1) or (3), whichever is relevant, we need |S <q | = k + j + 1 for some j with 1 ≤ j ≤ d. For each j, there are k+1+d k+1+j choices. So if n is odd, there are 2 k-d ( d j=1 k+1+d k+1+j ) choices for S. If n is even, there are 2 k-1-d ( d j=1 k+1+d k+1+j ) choices for S. This covers all cases, and taking the sum of all the above counts for each q ∈ Q gives the lower bound f (n) stated earlier.

Finally, we prove distinguishability of all the reached states. We assume that n ≥ 5 here; the case n = 4 can be verified computationally. Distinguishability can be proved using just four monotonic transformations {a, b, c, d}, defined as follows for q ∈ Q:

qa = q + 1 if 0 ≤ q ≤ n -2 and (n -1)a = (n -1), qb = q -1 if 1 ≤ q ≤ n -1 and 0b = 0, qc = 0 if 0 ≤ q ≤ k and qc = q otherwise, qd = n -1 if k ≤ q ≤ n -1 and qd = q otherwise. We claim that it suffices to prove the following statements:

-For each q ∈ Q, there is a string x q that is accepted by q in A, not accepted by any other state of A, and not accepted by any state of B of the form (p, ∅) for p ∈ Q. -For each q ∈ Q, there is a string y q that is accepted by (q, ∅) in B, not accepted by (p, ∅) for p = q, and not accepted by any state of A.

Indeed, let (p, S) and (q, T ) be two distinct states of B. If S = T , then there exists a state r which belongs to the symmetric difference of S and T ; then x r distinguishes the states. If S = T , then p = q, and y p distinguishes the states.

We define x q as follows: If 0 ≤ q ≤ k -1, then x q = a k-1-q d. If q = k, then x q = ac. If k + 1 ≤ q ≤ n -1, then x q = b q-(k+1) c. We define y q as follows: If 0 ≤ q ≤ k, then y q = a k+1-q cac. If k + 1 ≤ q ≤ n -1, then y q = b q-(k+1) cac. Now we verify these strings have the desired properties. Since n ≥ 5, we have n -1 = k + 1, and thus d sends every state of A to a non-final state except for k -1, which it fixes. Similarly, c sends every state of A to a non-final state except for k + 1, which it fixes. It follows easily that x q is accepted by q in A, but rejected in each other state of A. Now consider (p, ∅) in B; observe that for all i ≥ 0, the state (p, ∅)a i does not contain k -1 in its second component. Therefore if q ≤ k -1, then (p, ∅) does not accept x q . A similar argument works if q ≥ k + 1. For q = k, the second component of (p, ∅)a cannot contain k + 1, and it follows x q is not accepted.

Next consider whether (p, ∅) in B accepts y q . Observe that (p, ∅)a k+1-q c contains k in the second component if and only if p = q. Thus (p, ∅)a k+1-q ca contains k + 1 in the second component if and only if p = q. It follows then when q ≤ k + 1, the state (p, ∅) accepts y q if and only if p = q. If q ≥ k + 1, a similar argument applies. Finally, no state of A accepts y q because k is not in the image of a k+1-q c or b q-(k+1) c, but on the other hand, k is the only state of A which accepts ac. This completes the proof.

Power, Positive Closure, and Complementation

Here we consider the k-th power, positive closure, and complementation on starfree and unary star-free languages.

By definition, every finite and every co-finite language is star-free. In the unary case, the minimal DFA for a star-free language must have the cycle of length one, because otherwise the string w = a performs a non-trivial permutation on the states of this cycle. It follows that every unary star-free language is either finite or co-finite. Notice that the binary language {a, b} * a is star-free since its minimal DFA is permutation-free, but it is neither finite nor co-finite.

In the following four theorems, we consider the k-th power and the positive closure on star-free languages represented by DFAs and NFAs.

Theorem 4 (Power on Unary DFAs). Let L be a unary star-free language with sc(L) ≤ n. Then sc(L k ) ≤ k(n -1) + 1 and this bound is tight.

Proof. The upper bound is the same as in the case of unary regular languages [START_REF] Rampersad | The state complexity of L 2 and L k[END_REF]Theorem 3]. For tightness, consider the co-finite language L = a n-1 a * . We have L k = a k(n-1) a * , which is a co-finite language with desired complexity.

Theorem 5 (Power on NFAs). Let n, k ≥ 2. Let L be a star-free language over an alphabet Σ with nsc(L) ≤ n. Then nsc(L k ) ≤ kn, and this bound is tight if |Σ| ≥ 2. In the unary case, a lower bound is k(n -1) + 1.

Theorem 6 (Positive Closure on DFAs). Let n ≥ 6. Let L be a star-free language over an alphabet Σ with sc(L) ≤ n. Then

• sc(L + ) ≤ 2 n-1 + 2 n-2 -1, and this bound is tight if |Σ| ≥ 4;

• if |Σ| = 1, then sc(L + ) ≤ n 2 -7n + 13, and this bound is tight.

Theorem 7 (Positive closure on NFAs). Let L be a star-free language with nsc(L) ≤ n. Then nsc(L + ) ≤ n, and the bound is tight already in the unary case.

Proof. The upper bound is the same as for regular languages. For tightness, consider the co-finite language L = a n-1 a * . Then L + = L, so nsc(L + ) = n.

Next we consider complementation. In [START_REF] Holzer | Nondeterministic state complexity of star-free languages[END_REF]Theorem 11], an upper bound O(n 2 ) and a lower bound (n-1)(n-2) were obtained. We provide a more precise upper bound and a better lower bound in the following theorem.

Theorem 8 (Complementation on Unary NFAs). Let n ≥ 3. Let L be a unary star-free language with nsc(L) ≤ n. Then nsc(L c ) ≤ n 2 -2. There exists a unary star-free language L with nsc(L c ) ≥ (n -1) 2 + 1.

Proof. First, let L be finite. Then the longest string in L is of length at most n-1. Thus L, as well as L c , is accepted by a DFA with n+1 states, so nsc(L c ) ≤ n + 1. Next, let L be co-finite. Recall that if we transform a unary n-state NFA for L to the Chrobak normal form, we get a tail with at most n 2 -2 states and disjoint cycles of length x 1 , x 2 , . . . , x k [START_REF] Geffert | Magic numbers in the state hierarchy of finite automata[END_REF]Theorem 3.5]. The DFA equivalent to this NFA has a tail with at most n 2 -2 states and a single cycle of length lcm(x 1 , x 2 , . . . , x k ). Since L is co-finite, all states in this cycle must be final, so they can be merged into one state. Thus, in the minimal DFA for L, so also for L c , the total number of states is at most n 2 -1. Since the minimal DFA for L c includes a state from which no string is accepted, we can omit it, and we get the desired upper bound. For the lower bound, consider the language L accepted by the NFA shown in Fig. 1. The language L consists of strings of length cn + d(n -1) with c ≥ 1 and d ≥ 0 and the empty string. By [18, Lemma 5.1(ii)], the longest string in L c is of length (n -1) 2 . It follows that nsc(L c ) = (n -1) 2 + 1.

Conclusion

We examined the deterministic and nondeterministic state complexity of square, power, positive closure, and complementation on star-free languages. Our results are summarized in Tables 1 and2 where also the size of alphabet used to describe witnesses is displayed. The tables also show all known results concerning descriptional complexity of basic regular operations on star-free and regular languages. Notice that the deterministic state complexity of square on star-free languages and the nondeterministic state complexity of union, intersection, concatenation, power, and complementation on unary star-free languages remain open.

Case 3 :

 3 States of the form (k, S). Note that S <k has size at most k. If n is odd then S >k has size at most k. If n is even then S >k has size at most k -1. If |S <k | ≤ k -1, then condition (2) or condition (4) is satisfied. If |S <k | = k, then condition (1) or condition (3) is satisfied unless S >k is too large. The only way it can be too large is if n is odd and |S >k | = k, or n is even and |S >k | = k -1. But in both these cases, we have |S <k | + |S >k | = n -1 and thus S <k ∪ S >k = Q \ {k}.

Fig. 1 .

 1 Fig. 1. A lower bound example for complementation on unary star-free languages.

Research supported by the Natural Sciences and Engineering Research Council of Canada under grant No. OGP0000871. Research supported by VEGA grant 2/0132/19 and grant APVV-15-0091.

Table 1. Descriptional complexity of operations on star-free and regular languages.

For the state complexity of square on star-free languages, we have n-1 i=0 g(n, i) ≤ • ≤ (n -1)2 n -2(n -2) where g(n, i) is defined by (1) on p. 5.

Unary star-free

Source Unary regular Source

Table 2. Descriptional complexity of operations on unary star-free and unary regular languages.


Petra Wolf
email: wolfp@uni-trier.de

On the Decidability of Finding a Positive ILP-Instance in a Regular Set of ILP-Instances

Keywords: deterministic finite automaton, regular languages, regular intersection emptiness problem, decidability, integer linear programming

The regular intersection emptiness problem for a decision problem P (intReg(P )) is to decide whether a potentially infinite regular set of encoded P-instances contains a positive one. Since intReg(P ) is decidable for some NP-complete problems and undecidable for others, its investigation provides insights in the nature of NP-complete problems. Moreover, the decidability of the intReg-problem is usually achieved by exploiting the regularity of the set of instances; thus, it also establishes a connection to formal language and automata theory. We consider the intReg-problem for the well-known NP-complete problem Integer Linear Programming (ILP). It is shown that any DFA that describes a set of ILP-instances (in a natural encoding) can be reduced to a finite core of instances that contains a positive one if and only if the original set of instances did. This result yields the decidability of intReg(ILP).

Introduction

The problem Integer Linear Programming (ILP for short) asks whether a given set of inequalities with integer coefficients has an integer solution. ILP is among the first problems for which NP-hardness was shown (it is on Karp's original list of 21 NP-complete problems) and it is of great practical relevance in mathematical optimisation. There is a large number of academic prototypes as well as commercial implementations of ILP-solvers that are applied in various contexts; therefore ILP is arguably of similar importance as the well-known Boolean satisfiability problem. For recent theoretical papers on ILP see, e. g., [START_REF] Eiben | Unary integer linear programming with structural restrictions[END_REF][START_REF] Ganian | The complexity landscape of decompositional parameters for ILP[END_REF].

Linear and Integer Linear Programs are often used to model observations of the real world under the assumption that some properties are present. Important fields of applications are for example image segmentation [START_REF] Lempitsky | Image Segmentation with A Bounding Box Prior[END_REF] and motion segmentation [START_REF] Li | Two-View Motion Segmentation from Linear Programming Relaxation[END_REF]. These models often face uncertainties due to lack of information or measurement errors [START_REF] Hladík | Interval linear programming: A survey[END_REF]. One possibility to handle this problem is to take every possible instance into account, in which the uncertainty is replaced by an actual value and ask whether one of them is solvable. In doing so, we get a potentially infinite set of instances under which we seek a solvable one. For example, suppose we have a system of two inequalities a 11 x 1 + a 12 x 2 ≤ b 1 and a 21 x 1 a 22 x 2 ≤ b 2 with two integer variables x 1 and x 2 and only partial knowledge of the coefficients a 11 , a 12 , b 1 , a 21 , a 22 , b 2 . Due to measurement inaccuracies all we know is that a 11 is a power of 2; a 12 is even and negative; b 1 is positive and less than 100; a 21 is congruent to 3 modulo 29; a 22 is 1 less than an odd power of 2; and b 2 is negative. The described inequalities form an infinite family of inequalities and the described system represents an infinite family S of instances of ILP. Since each coefficient fits a regular pattern, a DFA can describe the encodings of exactly the instances in S.

Compact representations of finite sets of instances have already been considered for other problems. In graph modification, 1 the task is to transform a given graph using a given set of edit operations into a graph of a certain graph-family using as few operations as possible [START_REF] Bodlaender | Graph Modification Problems[END_REF][START_REF] Liu | An Overview of Kernelization Algorithms for Graph Modification Problems[END_REF]. The possible edit operations give rise to an edit distance [START_REF] Gao | A survey of graph edit distance[END_REF] with respect to the set of graphs; thus, the above described task can be seen as checking whether the set of all graphs within a certain distance from the given graph contains a member of the specified graph-family. The same can be done for string-problems where a given string is to be transformed (by using certain operations) into a target string [START_REF] Cormode | The String Edit Distance Matching Problem With Moves[END_REF].

Searching for a positive instance among infinitely many instances of a problem P seems to be a natural generalization of this setting. If we consider regular sets of instances, this task can be formalised as checking whether a given regular language of P -instances (represented by a deterministic finite automaton) and the fixed language of positive P -instances have a non-empty intersection. This was the original viewpoint of the line of research introduced by Güler et al. [START_REF] Güler | Deciding Regular Intersection Emptiness of Complete Problems for PSPACE and the Polynomial Hierarchy[END_REF][START_REF] Wolf | Decidability of the Regular Intersection Emptiness Problem[END_REF], where this problem is called the int Reg -problem of P (or int Reg (P ) for short). 2 The int Reg -problem has independently been studied under the name regular realizability problem RR(L), where the filter language L plays the role of problem P as defined above, i. e., RR(L) = int Reg (L) (see [START_REF] Anderson | Detecting palindromes, patterns and borders in regular languages[END_REF][START_REF] Rubtsov | Regular realizability problems and regular languages[END_REF][START_REF] Tarasov | Orbits of linear maps and regular languages[END_REF][START_REF] Vyalyi | On regular realizability problems[END_REF][START_REF] Vyalyi | On expressive power of regular realizability problems[END_REF][START_REF] Vyalyi | On regular realizability problems for context-free languages[END_REF][START_REF] Rubtsov | Regular realizability problems and models of a generalized nondeterminism[END_REF]). The RR problem appeared when considering models of generalized nondeterminism (GNA) where an auxiliary memory is used as a source of nondeterminism [START_REF] Vyalyi | On models of a nondeterministic computation[END_REF]. For each GNA class there are complete RR(L) problems where the filter language L consists of prefixes of GNA-certificates (or guess words) [START_REF] Vyalyi | On regular realizability problems[END_REF]. That fact already gives RR-problems which are complete under log space reductions for LOG, NLOG, P, NP, PSPACE, EXP, and Σ 1 . This observation motivated the attempt to present with the RR-problem 'a specific class of algorithmic problems that represents complexities of all known complexity classes [. . .] in a unified way' [START_REF] Vyalyi | On expressive power of regular realizability problems[END_REF]. It turned out that RR-problems are universal in the sense that for any problem P , there exists an RR-problem RR(L) with the same complexity (note that P and L are different languages). In [START_REF] Vyalyi | On regular realizability problems for context-free languages[END_REF], instead of focusing on which complexity classes can be covered by an RR-problem, the authors concentrate on contextfree filter languages and present examples for which RR(L) is either P-complete, NLOG-complete or has an intermediate complexity. In [START_REF] Tarasov | Orbits of linear maps and regular languages[END_REF] the decidability of the RR-problem with languages of permutations of binary words as filters have been considered. In this line of research, the filter languages are closely related to computations of specific machine models. As a consequence the regularity of the input language is not exploited at all and the hard part of a problem is coded into regular languages consisting of single words only. In [START_REF] Vyalyi | On expressive power of regular realizability problems[END_REF] the author notes that the presented reductions 'cut off almost all properties of regular languages'.

In [START_REF] Anderson | Detecting palindromes, patterns and borders in regular languages[END_REF], int Reg (L) has been studied for L with low computational complexity, but which describe structural properties of words that have high relevance for combinatorics on words and formal language theory (e.g., set of primitive words, palindromes, etc.). In this regards, (efficient) decision procedures are obtained.

In contrast to these research questions, the line of work initiated in [START_REF] Güler | Deciding Regular Intersection Emptiness of Complete Problems for PSPACE and the Polynomial Hierarchy[END_REF][START_REF] Wolf | Decidability of the Regular Intersection Emptiness Problem[END_REF] focuses on classical (hard) computational problems as filter languages and respective decision procedures heavily take advantage of the regularity of the set of input instances. Investigating the int Reg -problem for NP-complete problems shows that the decidability of their int Reg -problem is not trivial, e. g., int Reg (SAT) is decidable [START_REF] Güler | Deciding Regular Intersection Emptiness of Complete Problems for PSPACE and the Polynomial Hierarchy[END_REF], whereas int Reg (Bounded Tiling) is not [START_REF] Wolf | Decidability of the Regular Intersection Emptiness Problem[END_REF]. 3 This is particularly interesting because the original hardness proofs of SAT and Bounded Tiling are both given by directly encoding Turing-machine computations into a problem instance [START_REF] Cook | The Complexity of Theorem-Proving Procedures[END_REF][START_REF] Van Emde Boas | The Convenience of Tilings[END_REF]. Finding a generic characterization of NP-complete problems with a decidable int Reg -problem is still an open problem. This work continues this line of research and we will focus on the NP-complete integer linear programming problem as the filter language, i. e., we investigate the problem int Reg (ILP).

Our main result is that int Reg (ILP) is decidable. The idea is to transform the given DFA that represents the regular set of instances into a condensed one that accepts a finite set of instances, such that the condensed set contains a positive instance if and only if this is the case for the original set. 4 This is done by first identifying for all pairs of states the set of coefficients that can be read between these two states, and then choosing a finite number of representatives for each such set of coefficients (in a sense, these are the coefficients that are 'most promising' regarding possible solutions). Then, again for all pairs of states, we identify a set of whole inequalities that can be read between these two states and that only have coefficients from the set of 'promising' coefficients constructed before. Finally, we will again choose suitable representatives for those sets of inequalities, from which we will construct the desired condensed automaton. We will also give bounds on the number and length of words accepted by the condensed automaton and, in the conclusions, discuss the chosen encoding and present an alternative encoding. The presented arguments can easily be adapted to proof the decidability of the int Reg -problem for Linear Programming (with integer coefficients). Due to space restrictions some proofs are omitted.

Preliminaries

We assume the reader to be familiar with the basics of formal language theory and the complexity class NP. For a language descriptor A (e. g., regular expressions or automata), L(A) denotes the language described by A. With [n], n ∈ N we denote the set {1, . . . , n}. A deterministic finite automaton (DFA) A is a tuple (Q, Σ, δ, q 0 , F ) where Q is a finite set of states, Σ a finite alphabet, δ : Q × Σ → Q the (partial) transition function, q 0 the start state, and F is the set of final states. The transition function δ extends to the function δ * : Q × Σ * → Q in the usual way. We will only consider partial automata where every state is coaccessible, i. e., from every state, some final state is reachable.

We first give a formal definition of the problem Integer Linear Programming. While the standard-form of ILP varies in different areas, we refer to the definition in [START_REF] Wagner | Computational Complexity[END_REF] where this problem is called LIQ. We will refer to the described problem as ILP. The problem is NP-complete if we ask for solutions in Z [START_REF] Wagner | Computational Complexity[END_REF].

Definition 1 (ILP).

Given: Finite set A of pairs (α, β) where α ∈ Z m and β ∈ Z. Question: Is there an m-tuple

x ∈ Z m such that α • x ≤ β for all (α, β) ∈ A?
The problem will be encoded in the following way. The whole set A will be encoded in one word. For each pair (α, β) the elements of α and the β-value are encoded in binary over {0,1}. Each positive integer will be preceded with a + while each negative integer will be preceded with a -. The integers of α will be separated from β by a ≤ symbol. The inequalities themselves are terminated by $-symbols. Since we want to talk about regular languages of ILP-instances, we aim to have an encoding which is verifiable by a finite automaton. Therefore, we allow the inequalities of an ILP-instance to have different numbers of variables. The assignment of the coefficients to the variables is implicitly made by the order in which the coefficients occur. So, the i-th encoded coefficient in an inequality refers to variable x i and is referenced as the coefficient with index i. As the inequalities of an ILP-instance may have different numbers of coefficients, they are interpreted as filled up with coefficients zero until all inequalities have the same number of coefficients and hence the same number of variables. Alternative encodings are discussed in Section 5. More formally,

L enc := L ([+|-][0|1(0|1) * ]) * ≤ [+|-][0|1(0|1) * ]$ *
is the set of all encoded ILP-instances and with ILP enc we denote the set of all solvable encoded ILP-instances. As an example, consider the following integer linear program and its encoding:

{((5, 1, 0, -7), 15
) , ((0, -8, 1, 0), -4) , ((1, 0, 0, 0), -1)} ,

+ 101 + 1 + 0 -111 ≤ +1111 $ -0 -1000 + 1 ≤ -100 $ + 1 ≤ -1 $ .
Note that coefficients zero can either occur with a + or a -sign. The question we want to investigate is whether the set of solvable ILPinstances, encoded in the above described way, and a regular language, given by an automaton, have a non-empty intersection.

Definition 2 (int Reg (ILP)).

Given: Deterministic finite automaton A. Question: Is L(A) ∩ ILP enc = ∅?

Construction of the Condensed Automaton

We will follow the ideas presented in [START_REF] Güler | Deciding Regular Intersection Emptiness of Complete Problems for PSPACE and the Polynomial Hierarchy[END_REF] of investigating what kinds of loops can occur in the automaton without violating the encoding format, namely loops inside a coefficient, loops over whole coefficients, and loops over whole inequalities. Definition 3. Let A = (Q, Σ, δ, q 0 , F ) be a DFA. We define for all q, q ∈ Q and s ∈ {+, -} the coefficient transition set Λ s q,q and β-transition sets B s q,q as

Λ s q,q = {si | i ∈ {0, 1} * ∧ ∃σ ∈ Σ\{0, 1, $} : δ * (q, si) = q ∧ δ(q , σ) = ∅}. B s q,q = {si | i ∈ {0, 1} * ∧ δ * (q, si) = q ∧ δ(q , $) = ∅}.
Intuitively speaking, these transition sets contain all coefficients and β-values which can be completely read between q and q . Note that automata recognizing the transition sets are easily obtained from the original automata. When q, q and s is clear from the context, then we will simply write Λ and B.

We now want to find a set of representatives reps(Λ) for each coefficient transition set Λ. The set reps(Λ) will contain only the smallest and largest coefficient, which in the following we will denote extreme coefficients, from the set Λ. Since all inequalities are of the form

α 1 x 1 + • • • + α n x n ≤ β,
increasing the absolute value of a positive summand α i x i makes the inequality system harder to be solved, while decreasing it may only enlarge the set of solutions (correspondingly for negative summands). So, we only have to consider the largest and smallest coefficient α i contained in the coefficient transition set. The largest and smallest coefficient will correspond, in combination with a negative and positive x i value, respectively, to the smallest negative and positive summand, respectively. If a coefficient transition set is infinite, it contains coefficients with an arbitrarily large magnitude, which we will represent by the meta-characters +∞ and -∞ in order to indicate that we can replace them with large enough values. Similarly, if a β-transition set B + q,q is infinite, we will use +∞-symbol as a representative (indicating that we can find arbitrary large β-values and therefore such inequalities can be ignored), and for β-transition sets B - q,q we choose the element with the smallest magnitude as representative.

Definition 4. For transition sets Λ s q,q and B s q,q , we define:

reps(Λ + q,q ) := {min(Λ + q,q ), +∞}, if |Λ + q,q | = ∞ {min(Λ + q,q ), max(Λ + q,q )}, otherwise, reps(Λ - q,q ) := {-∞, max(Λ - q,q )}, if |Λ - q,q | = ∞ {min(Λ - q,q
), max(Λ - q,q )}, otherwise,

reps(B + q,q ) := {+∞}, if |B + q,q | = ∞ {max(B +
q,q )}, otherwise, reps(B - q,q ) := {max(B - q,q )}.

Since the transition sets are given by finite automata, it can be checked whether they are finite or infinite. The next step is to identify all inequalities which can be completely read in between two states and that only contain extreme coefficients, i. e., members from reps(Λ) and reps(B) as coefficients and β-values.

Definition 5. Let A = (Q, Σ, δ, q 0 , F ) be a DFA with L(A) ⊆ L enc . For every pair of states q, q ∈ Q we define the inequality transition set Ξ q,q as:

Ξ q,q = {s 1 i 1 s 2 i 2 . . . s k i k ≤ s b j$ | k ∈ N, ∃p 0 , . . . , p k+2 : k =1 s i ∈ reps(Λ s p -1 ,p ) ∧ p 0 = q ∧ δ(p k , ≤) = p k+1 ∧ s b j ∈ reps(B s b p k+1 ,p k+2 ) ∧ δ(p k+2 , $) = q }.
Now we want to pick finitely many representatives for every inequality transition set Ξ q,q . Some sets Ξ contain for every partial solution x an inequality which can be satisfied by an extension of x. 5 For those inequality transition sets, we simply choose $ as the representative to indicate that this transition set does not participate in the problem as we can always find a satisfiable inequality in it. Two types of inequality transition sets have this property. If Ξ q,q contains an inequality with an +∞-symbol as β-value, then an inequality with an arbitrary high actual β-value can be read in between q and q . So, for every value of the left side of the inequality we can read an even larger right side. The other type of Ξ sets are those which contain inequalities with an unbounded number of non-zero coefficients. Recall that the Ξ sets only contain coefficients which are representatives of Λ sets and hence the number of different coefficients in all Ξ sets is finite. Hence, the only reason an Ξ set is infinite is because the number of coefficients in the inequalities can be arbitrarily large. Therefore, those inequality transition sets are exactly the sets which are infinite after we removed all inequalities ending with more than |Q| = n consecutive coefficients zero. By removing more than n consecutive coefficients zero from the end of the sum, we ensure that there is a non-zero coefficient under the last n coefficient. If the set is still infinite we can find inequalities with non-zero coefficients with an arbitrary high index. If the modified inequality transition sets are finite, we simply pick the whole set as the set of representatives. Inequalities with more than n consecutive coefficients zero after the last non-zero coefficient can also be ignored, because there is an equivalent inequality with less than n coefficients zero in the inequality transition set. With this considerations in mind, we define for all states q, q ∈ Q a set of representatives reps(Ξ q,q ) for the inequality transition set Ξ q,q . Definition 6.

Let L Val := L ([+|-] ([0|1(0|1) * ]|∞)) and let L Trash := L((L Val ) * ([+|-]0) >n ≤ L Val $).
For every inequality transition set Ξ q,q we define reps(Ξ q,q ) :=

     {$}, if ∃w ∈ Ξ q,q
which ends with +∞$, or |Ξ q,q \L Trash | = ∞, Ξ q,q \L Trash , otherwise.

Note that there are only finitely many sets reps(Ξ q,q ) which are by construction all of a finite size.

We will now construct a condensed automaton which will have the finitely many inequalities, chosen as a representative, as its alphabet. Definition 7. Let A = (Q, Σ, δ, q 0 , F ) be a deterministic finite automaton with L(A) ⊆ L enc . We define cond(A) := (Q, Σ , δ , q 0 , F ) with the alphabet Σ = q,q ∈Q reps(Ξ q,q ) and δ = {(q, ξ, q ) | ξ ∈ reps(Ξ q,q )}. Lemma 3 will show that we only have to consider simple paths in cond(A).

Correctness of the Condensed Automaton

We will now present several lemmas which in the end will prove that L(A) ∩ ILP enc = ∅ if and only if L (cond(A)) ∩ ILP enc = ∅. With L (cond(A)) we refer to the language L(cond(A)) where the wild-cards ∞ are replaced by actual coefficients. First, we will show that it is sufficient to consider only the largest and smallest coefficient which can be read in between two states. Lemma 1. Let A = (Q, Σ, δ, q 0 , F ) be a DFA, let w ∈ L(A) ∩ ILP enc with solution x and let α ij be the j-th coefficient of the i-th inequality of w. Let

w = w α ij w . If α ij = a ij b ij c ij , b ij = ε,
and δ * (q 0 , w a ij ) = δ * (q 0 , w a ij b ij ), then the following holds:

1. Assume x j ≥ 0 and α ij has a + sign. Let w result from w by replacing α ij with a ij c ij . Then w ∈ L(A) ∩ ILP enc and x is a solution for w . 2. Assume x j ≥ 0 and α ij has a -sign. Let w result from w by replacing α ij with a ij (b ij ) 2 c ij . Then w ∈ L(A) ∩ ILP enc and x is a solution for w . 3. Assume x j ≤ 0 and α ij has a + sign. Let w result from w by replacing α ij with a ij (b ij ) 2 c ij . Then w ∈ L(A) ∩ ILP enc and x is a solution for w . 4. Assume x j ≤ 0 and α ij has a -sign. Let w result from w by replacing α ij with a ij c ij . Then w ∈ L(A) ∩ ILP enc and x is a solution for w .

Next, we will focus on whole inequalities and show that restricting the inequalities in words from L(A) to the above defined representatives does not affect the existence of a solvable ILP-instance in L(A). We already explained before Definition 6 that for every solution vector x we can replace the inequalities with an +∞-symbol as β-value by inequalities with actual β-values, which are satisfied by x. With respect to inequality transition sets containing inequalities with arbitrarily large non-zero coefficients, we will show next how to simultaneously replace such inequalities in a way that the replacements are satisfied by an extension of x. So, if the ILP-instance is solvable without inequalities from sets Ξ which are represented by $-symbols, then we can enlarge the instance and the solution to include those inequalities.

For the next lemma, we want to distinguish the infinite inequality transition sets without an unbounded β-value from the finite ones. Definition 8.

Inf Ξ := {Ξ q,q | reps(Ξ q,q ) = {$} ∧ Ξ q,q ∩ (L (L Val * ≤ +∞$) = ∅)}
Fin Ξ := {Ξ q,q | reps(Ξ q,q ) = {$}}

We will now find alternative representatives for the sets in Inf Ξ such that if an ILP-instance consisting only of inequalities from the sets in Fin Ξ has a solution x, then we can extend the ILP-instance with any combination of alternative representatives of the sets in Inf Ξ , such that x can be extended to a solution of the extended ILP-instance (we shall prove this in Lemma 2). This shows that we can ignore inequalities from the sets in Inf Ξ , i. e., the ones with representative $.

(σ(i)) ← min lex ({w ∈ σ(i) | (i + 1) • n < # ± (w) ≤ (i + 2) • n}).
For each fixed i the assignment of arep(σ(i)) in the above definition can be determined by computing the intersection of two regular sets given by DFAs, yielding a finite language. This finite language can be enumerated in order to find the lexicographical minimal element. The idea is to pick inequalities as alternative representatives which together form a matrix in row echelon form. For every inequality we assign the variable x k with the highest indexed non-zero coefficient α k with a value of which magnitude is large enough, such that the summand α k x k dominates the inequality. An inequality in the sets of Fin Ξ can only consist of up to n = |Q| different coefficients. The definition of arep(Ξ) ensures that the representatives of Ξ ∈ Inf Ξ contain more coefficients than any representative of the finite inequality transition sets. It also ensures that the number of coefficients contained in the representing inequality is strictly monotonously rising with the order σ. Especially, the index of the highest non-zero coefficient of arep(σ(i + 1)) is higher than the index of the highest non-zero coefficient of arep(σ(i)).

Lemma 2. Let w be a solvable ILP-instance consisting only of inequalities from sets in Fin Ξ . Let x be a valid solution of w. Then, for every ILP-instance w consisting of w and additional inequalities from {arep(Ξ) | Ξ ∈ Inf Ξ } the vector x can be extended to a solution x of w .

Proof. Let x = (x 1 , x 2 , . . . , x i ), let m be the number of variables in w , and let var -set(ξ) be a function returning the variables appearing in the inequality ξ with a non-zero coefficient. Let coeff (ξ, y j ) denote the coefficient of variable y j in the inequality ξ, let value(y j ) denote the assigned value x j of the variable y j , and let β(ξ) refer to the right side β of the inequality ξ. Algorithm 1 assigns values to the new variables y i+1 , y i+2 , . . . , y m appearing in w such that x = (x 1 , . . . , x i , x i+1 , . . . , x m ) is a solution of the instance w and works as follows. We go through the inequalities appearing in w which have been chosen as alternative representatives for the sets in Inf Ξ in the same order as when we assigned the representatives. Thus, the number of appearing variables per inequality is rising. In every considered inequality, there is at least one variable which has not appeared in the previously considered inequalities. We assign the new variables with a zero value, except for the variable with the highest index. This variable (MaxVar) gets a value which compensates all the other summands in the inequality. The sign of MaxVar is converse to the sign of its coefficient resulting in a negative summand. We can choose the value of MaxVar freely, since the variable has not appeared in any other inequality we considered earlier. If it appears in any later considered inequality, there will always be at least one new variable in the inequality which has not appeared earlier, and which can again compensate every other summand. It is easy to see that the considered inequality CurIneq is satisfied by the chosen variable assignment. Hence, x = (x 1 , . . . , x i , value(y i+1 ), . . . , value(y m )) is a solution of the ILP-instance w .

Only simple paths in cond(A) have to be considered in order to find a solvable ILP-instance in L (cond(A)). Lemma 3. Let w, w ∈ L enc and w be w without an arbitrary inequality ξ from w. (So, w is w with one inequality less.) If w ∈ ILP enc then w ∈ ILP enc .

We will now show that if there is a solvable ILP-instance in L (cond(A)), then we can replace any $-symbols in this instance by actual inequalities, resulting in a solvable ILP-instance in L(A). On the other hand, if there is a solvable ILP-instance in L(A) the modifications we made on A while constructing cond(A) preserve the existence of a solvable ILP-instance in the obtained language L (cond(A)).

Theorem 1. Let A = (Q, Σ, δ, q 0 , F ) be a deterministic finite automaton with L(A) ⊆ L enc . Then, L(A) ∩ ILP enc = ∅ if and only if L (cond(A)) ∩ ILP enc = ∅.

Proof Sketch. Let w ∈ L(A) ∩ ILP enc . We only keep those inequalities in w which are read between some states q and q on the path labeled with w in A and for which Ξ q,q ∈ Fin Ξ . All other inequalities in w are replaced by $-symbols. Then, wherever possible we pump the coefficients in w up or down, corresponding to the sign of the associated variable in x until we obtain an ILP-instance w in L (cond(A)). It holds that w is also solvable.

Let w ∈ L (cond(A))∩ILP enc . The corresponding ILP-instance in L(cond(A)) only consists of inequalities from Ξ sets in Fin Ξ or $-symbols. We first replace all $symbols which are representatives of Ξ sets in Inf Ξ by alternative representatives from Definition 9. According to Lemma 2 the obtained ILP-instance is still solvable. Then, we replace the leftover $-symbols which are representatives of Ξ sets which contain inequalities with an unbounded β-value. Since we know a solution for the considered ILP-instance, we can pick inequalities with large enough β-value such that the obtained ILP-instance w is satisfied by an extension of the considered solution. In w all $-symbols are replaced by actual inequalities and hence w ∈ L(A). As w is also solvable L(A) ∩ ILP enc = ∅ follows. Now, we are ready to put the pieces together and present our main result. In the following, we give a decision procedure for the int Reg -problem of ILP.

Theorem 2. The problem int Reg (ILP) is decidable.

Proof. Since L enc is regular, we can restrict L(A) to the regular language L(A) ∩ L enc . Let A = (Q, Σ, δ, q 0 , F ) be a deterministic finite automaton with L(A ) = L(A) ∩ L enc . For the automaton A , the Definitions 3 and 4 describe the construction of coefficient transition sets and assigning their representatives. In Definition 5 inequality transition sets are constructed based on those representatives. These inequality transition sets get representatives themselves in Definition 6. In Definition 7 a new automaton cond(A ) is defined, based on the representatives for the inequality transition sets. All those constructions can be computed by an algorithm. Theorem 1 states that L(A ) ∩ ILP enc = ∅ ⇔ L (cond(A )) ∩ ILP enc = ∅. Finally, Lemma 3 tells us that if there is a solvable ILP-instance in L (cond(A )) at all, then there is a solvable ILP-instance w in L (cond(A )) with a corresponding ILP-instance w ∈ L(cond(A )) which can be read on a simple path in cond(A ). The instance w is obtained from w by replacing coefficients with an absolute value above 3|Q|

• (|Q|2 |Q| ) 2|Q|+4 (1 + 2 |Q| )
by ∞-symbols. Since there are only finitely many simple paths in an automaton, and testing a given ILP-instance for solvability can be done in finite time, we can test all words in L (cond(A )) which correspond to labels of simple paths in cond(A ) for membership in ILP enc in finite time. Hence, L(A) ∩ ILP enc = ∅ is decidable.

Conclusion

The number of considered words in L (cond(A)) is bounded by 2 O(|Q| 2 log(|Q|)) . The length of considered words in L(cond(A)) regarding the alphabet Σ of cond(A) is bounded by O(|Q|). Finally, the length of considered words regarding the alphabet Σ of A, meaning that we replace $-and ∞-symbols by actual sub-strings over Σ, is bounded by O(|Q| 7 ). Therefore, we can guess some word in L (cond(A)) and check its membership in ILP enc by solving the represented ILP-instance. Since ILP is NP-complete int Reg (ILP)∈ NP follows. For a given ILP-instance, we can construct a DFA accepting only this instance in polynomial time. Hence int Reg (ILP) is NP-complete.

According to [START_REF] Vyalyi | On regular realizability problems[END_REF], the presented results are stable under applying a lengthpreserving morphism to the encoding scheme. The results are also stable under changing the binary encoding to any base-k encoding. Recall that in order to talk about regular sets of problem-instances, we want to have a problem encoding which can be verified by a deterministic finite automaton. In particular, we can not verify with a DFA that all variables appear in a certain inequality or that the inequalities have the same length. Therefore, we have implicitly filled the inequalities with coefficients zero to ensure the same number of variables per inequality. Note that this forbids an explicit matrix representation of an ILP-instance. Instead of referencing the variables of an inequality implicitly by the number and order of the coefficients we could also use another encoding, where we explicitly name the variable and the coefficient. In this setting multiple occurrences of the same variable would be possible and would be interpreted as a summation of terms. Here, we would define transition sets for coefficients and for variables. We would not pump the number of variables in an inequality but instead pump the label of a variable to make it independent of other variables and inequalities. We would still treat the coefficients in the same way and we would also consider only simple paths. In terms of the 'int Reg -techniques' of [START_REF] Wolf | Decidability of the Regular Intersection Emptiness Problem[END_REF] we would switch from the replacing technique to the separating technique and the int Reg -problem of ILP in this variable-explicit encoding would still be decidable.

Although we considered partial DFAs, the construction also works for partial NFAs. It might be worthwhile to investigate further extensions of int Reg (ILP) such as Boolean combinations of inequalities or quadratic programming.

Definition 9 .

 9 Let σ : [|Inf Ξ |] → Inf Ξ be an arbitrary but fixed ordering of the sets in Inf Ξ . Let n := |Q| and # ± (w) denote the number of signs in an inequality w. The function min lex returns the lexicographical minimal element of a set 6 . For every 1 ≤ i ≤ |Inf Ξ | we define for the inequality transition set σ(i) in Inf Ξ a set of alternative representatives arep as arep

Algorithm 1

 1 Extending solution x of ILP-instance w to solution x of w . AssignedVars ← {y1, . . . , yi} for j ← 1 to |InfΞ | do CurIneq ← arep(σ(j)), ToAssign ← ∅ if CurIneq appears in w then ToAssign ← var -set(CurIneq)\AssignedVars MaxVar ← y k ∈ ToAssign with highest index k for all y ∈ ToAssign\{MaxVar} do value(y) ← 0 end for SumOthCoeff ← y l ∈{var -set(CurIneq)\{MaxVar}} coeff (CurIneq, y l ) • value(y l ) CoeffMaxVar ← coeff (CurIneq, MaxVar), b ← β(CurIneq) value(MaxVar) ← |b -SumOthCoeff| • (-1) CoeffMaxVar |CoeffMaxVar| AssignedVars ← AssignedVars ∪ ToAssign end if end for

A Dagstuhl seminar on 'Graph Modification Problems' was held in

[START_REF] Bodlaender | Graph Modification Problems[END_REF].[START_REF] Bodlaender | Graph Modification Problems[END_REF] Note that this problem is only well-defined if it is clear how P is represented as a language, i. e., we have to define how P -instances are encoded as strings.

LOGSPACE and P also contain problems with undecidable intReg-problem[START_REF] Wolf | Decidability of the Regular Intersection Emptiness Problem[END_REF].

Our construction uses similar ideas as given in[START_REF] Lange | Set automata. In: Combinatorics, Complexity and Logic[END_REF].

An extension v ∈ Z n of v ∈ Z m with n > m coincides with v in all positions i ≤ m.

The function min lex is used to make the definition clear. Any other element of the set could be used as well.

Acknowledgment: The author thanks Markus L. Schmid for proofreading and helpful discussions and is grateful to the anonymous reviewers for their suggestions. The author was partially supported by DFG (FE 560 / 9-1).