Hermann Gruber

Digraph Complexity Measures and Applications in Formal Language Theory †

Keywords: regular expression, star height, digraph, cycle rank, ordered coloring, vertex ranking MSC: 68Q45 (primary), 68Q25, 05C20 (secondary), F2.2 Nonnumerical Algorithms and Problems, G2.2 Graph Theory

We investigate structural complexity measures on digraphs, in particular the cycle rank. This concept is intimately related to a classical topic in formal language theory, namely the star height of regular languages. We explore this connection, and obtain several new algorithmic insights regarding both cycle rank and star height. Among other results, we show that computing the cycle rank is NP-complete, even for sparse digraphs of maximum outdegree 2. Notwithstanding, we provide both a polynomial-time approximation algorithm and an exponential-time exact algorithm for this problem. The former algorithm yields an O((log n) 3/2 )-approximation in polynomial time, whereas the latter yields the optimum solution, and runs in time and space O * (1.9129 n ) on digraphs of maximum outdegree at most 2.

Regarding the star height problem, we identify a subclass of the regular languages for which we can precisely determine the computational complexity of the star height problem. Namely, the star height problem for bideterministic languages is NP-complete, and this holds already for binary alphabets. Then we translate the algorithmic results concerning cycle rank to the bideterministic star height problem. We thus obtain a polynomial-time approximation algorithm, as well as a reasonably fast exact exponential algorithm for the bideterministic star height problem.

Introduction

In the theory of undirected graphs, structural complexity measures for graphs, such as treewidth and pathwidth, have gained an important role, both from a structural and an algorithmic viewpoint, see e.g. [START_REF] Diestel | Graph Theory[END_REF][START_REF] Fedor | Exact Exponential Algorithms[END_REF]. However, networks arising in some domains are more adequately modeled as having directed edges. Therefore in recent years, attempts have been made to lift such measures and parts of the theory of undirected graphs to the case of digraphs. Several recent works show that, while there often exist partial analogues to the undirected case, the picture for digraphs is much more involved [START_REF] Barát | Directed path-width and monotonicity in digraph searching[END_REF][START_REF] Berwanger | The DAG-width of directed graphs[END_REF][START_REF] Ganian | On digraph width measures in parameterized algorithmics[END_REF][START_REF] Kreutzer | Digraph decompositions and monotonicity in digraph searching[END_REF][START_REF] Ali | D-Width: A more natural measure for directed tree width[END_REF]. We discuss some of these measures, relate them to each other, and investigate their algorithmic aspects. Interestingly, we are able to show that all these complexity measures bound each other within a factor logarithmic in the order of the digraph, thus paralleling the case of undirected graphs [START_REF] Hans | Approximating treewidth, pathwidth, frontsize, and shortest elimination tree[END_REF]. We focus in particular on the cycle rank, a digraph complexity measure originally motivated by studies in formal languages [START_REF] Eggan | Transition graphs and the star height of regular events[END_REF]. Apparently, there is a renewed interest in this measure, as witnessed by recent research efforts [START_REF] Alpert | Rank numbers of grid graphs[END_REF][START_REF] Bar-Noy | Ordered coloring grids and related graphs[END_REF][START_REF] Ganian | On digraph width measures in parameterized algorithmics[END_REF][START_REF] Hunter | LIFO-search on digraphs: A searching game for cycle-rank[END_REF][START_REF] Lampis | On the algorithmic effectiveness of digraph decompositions and complexity measures[END_REF].

We obtain the following results on computing the cycle rank: The decision version of the problem is NP-complete, and this remains true for graphs of maximum outdegree at most 2. Previously, the problem was known to be NP-complete on undirected symmetric digraphs of unbounded degree, see [START_REF] Hans | Rankings of graphs[END_REF]. On the positive side, we design a polynomial-time O((log n) 3/2 )-approximation algorithm, as well as an exact exponential algorithm algorithm computing the cycle rank of digraphs. If the given digraph is of bounded outdegree, the latter algorithm runs in time and space O * ((2 -ε) n ), where n is the order of the digraph, and ε is a constant depending on the maximum outdegree.

For unbounded outdegree, the running time is still O * (2 n ), whereas for maximum outdegree 2, we even attain a bound of O * (1.9129 n ). As a further application, we also obtain an exact algorithm for the directed feedback vertex set problem on digraphs of maximum outdegree 2, which runs within the same time bound.

Then we present applications to the theory of regular expressions. The star height of a regular language is defined as the minimum nesting depth of stars needed in order to describe that language by a regular expression. Already in the 1960s, Eggan [START_REF] Eggan | Transition graphs and the star height of regular events[END_REF] raised the question whether the star height can be determined algorithmically. It was not until 25 years later that Hashiguchi found a rather complicated decidability proof [START_REF] Hashiguchi | Algorithms for determining relative star height and star height[END_REF]. Even today, the best known algorithm has doubly exponential running time, and is arguably still impractical [START_REF] Daniel | On the complexity of the relative inclusion star height problem[END_REF]. Therefore, we study the complexity of the star height problem when restricted to a subclass of the regular languages. We show that the star height problem for bideterministic languages is NP-complete, and this remains true when restricted to binary alphabets. Furthermore, we present both an efficient approximation algorithm and an exact exponential algorithm for this problem. The key to these results are the corresponding algorithms for the cycle rank of digraphs mentioned above; also the above mentioned bounds carry over to this application in formal language theory.

The paper is organized as follows: After this introduction, we recall in Section 2 some basic notions from graph theory and from automata theory. We study structural properties of the cycle rank of digraphs in Section 3. Section 4 is devoted to algorithmic aspects of cycle rank. Afterward, we apply these findings in Section 5 to the star height problem on bideterministic languages. We complete the paper in Section 6 by showing possible directions for further research. accompanying an exponential. More precisely, for functions f (n) and g(n), we write f

(n) = O * (g(n)) if f (n) = O g(n) • (log g(n)) k for some nonnegative constant k. For example, we have 2 n •n 3 = O * (2 n ).

Digraphs

We assume familiarity with basic notions in graph theory, as contained in [START_REF] Diestel | Graph Theory[END_REF], so we only fix the notation and give a few specialized definitions below. A digraph G = (V, E) consists of a finite set of vertices V and a set of edges E ⊆ V 2 .

We refer to an edge of the form (v, v) as a loop; A digraph without loops is called loop-free.

The outdegree of a vertex v is defined as the number of vertices u such that (u, v) ∈ E. The total degree of v is defined as the number of distinct vertices u having

(u, v) ∈ E or (v, u) ∈ E.
If the edge relation of a digraph G is symmetric, we say G is an (undirected) graph. By taking the symmetric closure of the edge relation of a digraph, we obtain its undirected counterpart-of course, this is a many-to-one correspondence.

For a subset of vertices U ⊆ V , let G[U ] denote the sub(di)graph induced by U , which is obtained by restricting the vertex set of G to U and redefining the edge set E appropriately. In this context, we will often use G -U as a shorthand for

G[V \ U ] and G -v for G[V \ {v}]. A subset of vertices U ⊆ V
is strongly connected if for every pair of distinct vertices u and v in U , there is both a path from u to v and a path from v to u, and both of these paths visit only vertices from U . Maximal strongly connected subsets of V are called strongly connected components; a strongly connected subset S is nontrivial if the subdigraph G[S] induced by S contains at least one edge (note that this includes the case S = {v} if v has a loop). A digraph is acyclic if all of its strongly connected components are trivial.

Formal Languages

As with digraphs, we only recall some basic notions in formal language and automata theory-for a thorough treatment, the reader might want to consult a textbook such as [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF]. In particular, let Σ be a finite alphabet and Σ * the set of all words over the alphabet Σ, including the empty word λ. The length of a word w is denoted by |w|, where |λ| = 0. A (formal) language over the alphabet Σ is a subset of Σ * .

The regular expressions over an alphabet Σ are defined recursively in the usual way: (i) ∅, λ, and every letter a with a ∈ Σ is a regular expression; and when r 1 and r 2 are regular expressions, then (r 1 + r 2 ), (r 1 • r 2 ), and (r 1 ) * are also regular expressions. The language defined by a regular expression r, denoted by L(r), is defined as follows:

L(∅) = ∅, L(λ) = {λ}, L(a) = {a}, L(r 1 + r 2 ) = L(r 1 ) ∪ L(r 2 ), L(r 1 • r 2 ) = L(r 1 ) • L(r 2 )
, and L(r * 1 ) = L(r 1 ) * . For a regular expression r over Σ, the star height, denoted by h(r), is a structural complexity measure inductively defined by: h(∅) = h(λ) = h(a) = 0, h(r 1 • r 2 ) = h(r 1 + r 2 ) = max (h(r 1 ), h(r 2 )), and h(r * 1 ) = 1 + h(r 1 ). The star height of a regular language L, denoted by h(L), is then defined as the minimum star height among all regular expressions describing L.

It is well known that regular expressions are exactly as powerful as finite automata, i.e., for every regular expression one can construct an equivalent (deterministic) finite automaton and vice versa, see [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF]. Finite automata are defined as follows: A nondeterministic finite automaton (NFA) is a 5-tuple A = (Q, Σ, δ, q 0 , F ), where Q is a finite set of states, Σ is a finite set of input symbols, δ :

Q × Σ → 2 Q is (i)
For convenience, parentheses in regular expressions are sometimes omitted and the concatenation is simply written as juxtaposition. The priority of operators is specified in the usual fashion: concatenation is performed before union, and star before both product and union.

the transition function, q 0 ∈ Q is the initial state, and F ⊆ Q is the set of accepting states. The language accepted by the finite automaton A is defined as

L(A) = { w ∈ Σ * | δ(q 0 , w) ∩ F = ∅ }, where δ is nat- urally extended to a function Q × Σ * → 2 Q . A nondeterministic finite automaton A = (Q, Σ, δ, Q 0 , F )
is deterministic, for short a DFA, if |δ(q, a)| ≤ 1, for every q ∈ Q and a ∈ Σ. In this case we simply write δ(q, a) = p instead of δ(q, a) = {p}. Two (deterministic or nondeterministic) finite automata are equivalent if they accept the same language.

A deterministic finite automaton is bideterministic, if it has a single final state, and if the NFA obtained by reversing all transitions and exchanging the roles of initial and final state is again deterministicnotice that, by construction, this NFA in any case accepts the reversed language. A regular language L is bideterministic if there exists a bideterministic finite automaton accepting L. These languages form a proper subclass of the regular languages [START_REF] Angluin | Inference of reversible languages[END_REF].

Cycle Rank of Digraphs

Cycle Rank and Directed Elimination Forests

Originally suggested in the 1960s by Eggan and Büchi in the course of investigating the star height of regular languages [START_REF] Eggan | Transition graphs and the star height of regular events[END_REF], the cycle rank is probably one of the oldest structural complexity measures on digraphs. In this section, we delve into the structural foundations of cycle rank.

Definition 1 The cycle rank of a directed graph G = (V, E), denoted by r(G), is inductively defined as follows: If G is acyclic, then r(G) = 0. If G is strongly connected and E = ∅, then r(G) = 1 + min v∈V { r(G -v) }.
If G is not strongly connected, then r(G) equals the maximum cycle rank among all strongly connected components of G.

We note that the requirement E = ∅ in the above definition allows to differentiate between acyclic digraphs and (otherwise acyclic) digraphs with loops. We also remark that the cycle rank can be equivalently defined using decompositions, compare [START_REF] Mcnaughton | The loop complexity of regular events[END_REF]: Definition 2 A directed elimination tree for a nontrivially strongly connected digraph G = (V, E) is a rooted tree T = (T , E) having the following properties:

a) T ⊆ V × 2 V , and if (x, X) ∈ T , then x ∈ X.
b) The root of the tree is (v, V ) for some v ∈ V . c) There is no pair of distinct vertices of the form (x, X) and (y, X) in the forest.

d) If (x, X) is a node in T , and G[X]-x has j ≥ 0 nontrivial strongly connected components Y 1 , . . . , Y j , then (x, X) has exactly j children of the form (y 1 , Y 1 ), . . . (y j , Y j ) for some y 1 , . . . , y j ∈ V . A directed elimination forest for a digraph G with k ≥ 0 nontrivial strongly connected components C 1 , . . . C k , is a rooted forest consisting of directed elimination trees for G[C i ], 1 ≤ i ≤ k.
Figure 1 illustrates this concept by an example. It is shown in [START_REF] Mcnaughton | The loop complexity of regular events[END_REF] that the minimum height among all directed elimination forests for G equals the cycle rank of G. Interestingly, the concept of elimination forests was rediscovered in the context of sparse matrix factorization, see [START_REF] Schreiber | A new implementation of sparse Gaussian elimination[END_REF] for the undirected case and [START_REF] Stanley | The theory of elimination trees for sparse unsymmetric matrices[END_REF] for the directed case.

A B C D (A, {A, B, C, D}) (C, {B, C, D}) (B, {B}) (D, {D})
Fig. 1: An example digraph G, and a directed elimination tree for it.

Cycle Rank and other Digraph Complexity Measures

We compare the cycle rank with two other structural complexity measures, namely weak separator number and directed pathwidth. The first measure is a generalization of separator number (see e.g. [START_REF] Hans | Approximating treewidth, pathwidth, frontsize, and shortest elimination tree[END_REF][START_REF] Gruber | On balanced separators, treewidth, and cycle rank[END_REF][START_REF] Robertson | Graph minors. II. Algorithmic aspects of tree-width[END_REF]) to digraphs:

Definition 3 Let G = (V, E) be a digraph and let U ⊆ V be a set of vertices. A set of vertices S is a weak balanced separator for U if every strongly connected component of G[U \ S] contains at most 1 2 |U \ S| vertices.
The weak separator number of G, denoted by s(G), is defined as the maximum size, taken over all subsets U ⊆ V , among the minimum weak balanced separators for U .

We illustrate this definition in the following example.

Example 4 Consider the digraph G in Figure 1. Removing the vertex B results in a digraph with strongly connected components {A} and {C, D}. Since |{C, D}| ≤ 1 2 (4 -1) , the singleton set {B} forms a weak balanced separator. Also, each induced subdigraph of G has a weak balanced separator of size 1, so s(G) ≤ 1. On the other hand, we must have s(G) ≥ 1, since G contains cycles of length greater than 1. Some readers will feel that the above definition is a bit contrived because of the ceiling operator • . But this is an essential detail, as it guarantees that a digraph with a weak balanced separator of size k will always admit a weak balanced separator of size k + 1.

In order to relate weak separator number and cycle rank, we need the following recurrence: For integers k, n ≥ 1, let R k (n) be given by the recurrence

R k (n) = k + R k n -k 2 , with R k (r 0 ) = r 0 for r 0 ≤ k.
Lemma 5 Let G be a loop-free digraph with n vertices and weak separator number at most k. Then

r(G) ≤ R k (n) -1.
Proof: We generalize a proof given in [START_REF] Gruber | On balanced separators, treewidth, and cycle rank[END_REF] to the case of digraphs. Let G be the digraph obtained from G by adding self-loops to each vertex. Then r G = r(G) + 1, so we may prove instead that

r G ≤ R k (n).
We prove the statement by induction on the order n of G . The base cases n ≤ k of the induction are easily seen to hold, since the cycle rank of a digraph is always bounded above by its order.

For the induction step, assume n > k. As already mentioned, if G admits a weak balanced separator of size at most k, then it also has a weak balanced separator of size exactly k. Let X be such a separator. Denote the strongly connected components of G -X by C 1 , . . . , C p . Then r G ≤ k + r G -X , and by definition of cycle rank,

r G -X ≤ max 1≤i≤p r G [C i ] .
As X is a weak balanced separator, we have

|C i | ≤ n-k 2 for 1 ≤ i ≤ p.
Hence, we can apply the induction hypothesis to obtain

max 1≤i≤p r G [C i ] ≤ R k ( n -k 2 ).
Putting these pieces together, we have r

G ≤ k + R k ( n-k 2
), as desired. 2

The recurrence R k (n) is studied in [START_REF] Gruber | On balanced separators, treewidth, and cycle rank[END_REF], where also the inequality

R k (n) ≤ k • log(n/k) is derived. (ii)
We thus have the following bound:

Corollary 6 Let G be a loop-free digraph with n vertices and weak separator number at most k. Then

r(G) ≤ k • log(n/k) -1. 2
This inequality is sharp already in the undirected case, see [START_REF] Gruber | On balanced separators, treewidth, and cycle rank[END_REF]. Previously, a looser bound comparing cycle rank to a similar notion of weak balanced separators was given in [START_REF] Gruber | Finite automata, digraph connectivity, and regular expression size[END_REF]. It is easy to see that Corollary 6 improves upon the previous bound.

We turn to the comparison with directed pathwidth. That measure was introduced by Reed, Seymour and Thomas (cf. [START_REF] Barát | Directed path-width and monotonicity in digraph searching[END_REF]) as a generalization of pathwidth to digraphs.

Definition 7 For a digraph G = (V, E), a directed path decomposition of G is a sequence W 1 W 2 • • • W r of subsets of V , called bags, such that a) each vertex is contained in at least one bag, b) W i ∩ W k ⊆ W j
for all i < j < k, and c) for each edge (u, v) ∈ E, there is a bag containing both endpoints, or there exist i, j with i < j such that the tail u is in W i and the head v is in W j .

The width of a directed path decomposition is defined as the maximum cardinality among all bags minus 1.

The directed pathwidth is defined as the minimum width among all directed path decompositions for G.

For algorithmic constructions, it is often useful to work with a certain normal form of directed path decompositions. A directed path decomposition is normal, if adjacent bags may differ in at most one vertex, and it is easy to transform a directed path decomposition into a normal one. We return to our running example to illustrate these concepts. (ii) Here log denotes the binary logarithm. One can show in general that, in a normal directed path decomposition, there exists a pair of adjacent bags "somewhere in the middle", whose intersection forms a weak balanced separator.

Without loss of generality, one can assume that, if W i and W i+1 are adjacent bags for 1 ≤ i < n, then W i = W i+1 , and thus W i ∩ W i+1 ≤ dpw(G). Altogether, this yields the following relation between weak balanced separator number and directed pathwidth:

Lemma 9 Let G be a digraph. Then s(G) ≤ dpw(G). 2
How does cycle rank relate to directed pathwidth? We can answer this using directed elimination forests.

Lemma 10 Let G be a digraph. Then dpw(G) ≤ r(G).

Proof: We prove by induction that each directed elimination forest of height k for G can be transformed into a directed path decomposition for G of width at most k.

If k = 0, then G is acyclic, and thus clearly admits a directed path decomposition of width 0.

For the induction step, assume the directed elimination forest for G has roots (x 1 , C 1 ), (x 2 , C 2 ),. . . , (x r , C r ), with the strongly connected components C i in topological order. Let

G i = G[C i ] -x i .
Then G i has cycle rank at most k -1. By induction assumption, each digraph G i admits a directed path decomposition of width at most k -1. By adding the vertex x i to each bag in the respective decomposition for G i , we obtain a directed path decomposition for G[C i ]. Concatenating the r individual directed path decompositions while respecting the above topological order, we obtain a directed path decomposition of width at most k for G, as desired.

2

Altogether, we have derived the following chain of inequalities:

Theorem 11 Let G be a loop-free digraph with n vertices and weak separator number k. Then

k ≤ dpw(G) ≤ r(G) ≤ k • log(n/k) -1.
Quite a few more structural complexity measures on digraphs were studied recently, such as directed tree-width, DAG-width, and Kelly-width. As detailed in [START_REF] Kintali | Approximation algorithms for directed width parameters[END_REF], each of these measures is bounded below by a function that is linear in the weak separator number (iii) . On the other hand, all of those are bounded above by the directed pathwidth (cf. [START_REF] Kintali | Approximation algorithms for directed width parameters[END_REF]), so Theorem 11 will also serve for comparing them with cycle rank, and with weak separator number.

More precisely, put the elements of S in arbitrary order. Then for given s in S, let X denote the set of vertices occurring before s. Assuming we have already computed a directed elimination forest for G[W ∪ X], we now show how to extend this to a forest for G[W ∪ X ∪ s]. Initially, the set X is empty, and we proceed for each s until X = S. Let The recursion terminates as soon as the size of W decreases below β(log n) 3/2 . In this case, simply return an (arbitrary) directed elimination forest for G[W ].

Here, the number β is a fixed, suitably chosen, constant coming from the analysis below. This completes the description of the algorithm.

It remains to analyze the above algorithm. It is readily checked that the algorithm returns an elimination forest for G. For the performance guarantee, those recursive calls that simply partition the graph into strongly connected components do not add to the height of the resulting forest; if we restrict our attention to these recursive calls that compute a suitable vertex subset S, the depth of the recursion tree is O(log n). At each such step, we can find in polynomial time a suitable set S of size at most βk √ log n, where k is the directed pathwidth of G, and β is some known constant (cf. [START_REF] Kintali | Approximation algorithms for directed width parameters[END_REF]Corollary 2.25]). The recursion terminates with an elimination forest of height at most β • (log n) 3/2 . Thus the overall height is bounded by

β • k • log n • O(log n) + β • (log n) 3/2 = O(k • (log n) 3/2 ),
where k is the directed pathwidth of G. By Lemma 10, we have k ≤ r(G). In this way, we have a polynomial-time O((log n) 3/2 )-approximation for cycle rank. 2

The above performance guarantee matches the best previous result known for the undirected case [START_REF] Agarwal | o( ( log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems[END_REF]. For other digraph complexity measures, such as D-width and directed pathwidth, approximation algorithms in a similar vein were recently given in [START_REF] Kintali | Approximation algorithms for directed width parameters[END_REF].

Exact Computation

In certain circumstances, an approximation guarantee within a factor O((log n) 3/2 ) may not suffice. Thus we also take a look at exact algorithms for computing the cycle rank.

The naïve algorithm for determining cycle rank according to Definition 1 entails inspecting n! possibilities on a graph with n vertices. While one may not expect a polynomial-time algorithm, we can still do much better: Theorem 14 The cycle rank of an n-vertex digraph can be computed in time and space O * (2 n ).

Proof: We show how the characterization of the cycle rank of a digraph G = (V, E) in terms of the directed elimination forests from Definition 2 can be turned into a dynamic programming scheme. We only consider the case G itself is nontrivially strongly connected-otherwise, we obtain the cycle rank by taking the minimum among the cycle ranks of the nontrivial strongly connected components of G. For a nontrivial strongly connected subset of vertices X ⊆ V and a vertex x ∈ X, let r(x, X) denote the minimum height among all elimination forests for G with root (x, X). Then r(G) = min v∈V r(v, V ), so it suffices to design an algorithm computing r(v, V ) for each v ∈ V . By inspecting Definition 2, we obtain the recurrence

r(x, X) = 1 if G[X] -x is acyclic 1 + max Y min y∈Y r(y, Y ) otherwise (1)
Here Y runs over all nontrivial strongly connected components of G[X] -x (of which there can be at most |X| -1). Using the classic trick of memoization (see [START_REF] Fedor | Exact Exponential Algorithms[END_REF]), this recurrence can be easily transformed into a dynamic programming scheme with memoization that runs in time |S| • n O (1) , where S ⊆ 2 V is the set of strongly connected subsets of the digraph G.

2
The reader is invited to try out this algorithm for the digraph depicted in Figure 1. The bottleneck in the algorithm is the requirement of computing and storing the cycle rank for all elements of S, namely of the family of strongly connected subsets in the input digraph. For a complete digraph, we have |S| = 2 n . But this bound can no longer be reached for digraphs of bounded maximum outdegree. For undirected graphs of maximum degree d, a nontrivial bound on the number of (weakly) connected subsets was established recently in [START_REF] Björklund | The traveling salesman problem in bounded degree graphs[END_REF]. As it turns out, their bound allows the following generalization to the theory of digraphs, in that the original proof carries over with obvious modifications:

Lemma 15 Let G be a digraph of order n with maximum outdegree at most d. Then the number of strongly connected subsets of V is at most γ n + n, with γ = (2 d+1 -1) 1/(d+1) . In particular, for d = 2, we have γ . = 1.9129. 2

On digraphs of bounded outdegree, we thus obtain the following improved bound on the running time of the above algorithm:

Theorem 16 Let G be a digraph of order n with constant maximum outdegree d. Then the cycle rank of G can be computed in time and space O * ((2 -ε) n ), where ε is a constant depending on d. In particular, for digraphs of maximum outdegree 2, the cycle rank can be computed in time and space O * (1.9129 n ). 2

It seems that Lemma 15 has a host of algorithmic consequences. For illustration, recall that a vertex subset S ⊆ V of a digraph G is a directed feedback vertex set, if removing S from G leaves an acyclic digraph. Off the cuff, we can devise an exact algorithm for minimum directed feedback vertex set on sparse digraphs.

Theorem 17 Let G be a digraph of order n with constant maximum outdegree d. Then a minimum directed feedback vertex set of G can be computed in time and space O * ((2 -ε) n ), where ε is a constant depending on d. In particular, for digraphs of maximum outdegree 2, a minimum directed feedback vertex set can be computed in time and space O * (1.9129 n ).

Proof: By duality, the task of enumerating all minimal directed feedback vertex sets is equivalent to enumerating all maximal acyclic subsets, that is, maximal vertex subsets that induce a directed acyclic graph. Here, "minimal" and "maximal" are meant with respect to set inclusion.

Since there is an algorithm enumerating all minimal directed feedback vertex sets (or, equivalently, all maximal acyclic subsets) with polynomial delay [START_REF] Schwikowski | On enumerating all minimal solutions of feedback problems[END_REF], it only remains to derive a combinatorial bound on the number of such sets. A strongly connected subset S ⊂ V in G is called a minimal strongly connected subset, if S contains a vertex v such that S -v is an acyclic subset. Clearly, in this case, S -v is a maximal acyclic subset. Thus, each minimal strongly connected subset S will give rise to at most |S| ≤ n maximal acyclic subsets; and each maximal acyclic subset can be obtained in this way from a minimal strongly connected subset. Thus the total number of maximal acyclic subsets in G is at most n times the number of (minimal) strongly connected subsets in G. The result now follows with Lemma 15.

2

The above running time appears reasonable if we consider the following facts: First, even on digraphs of maximum outdegree at most 2, the problem is NP-complete [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]Problem GT7]. Second, the fastest known exact algorithm for digraphs of unbounded outdegree [START_REF] Razgon | Computing minimum directed feedback vertex set in O * (1.9977 n )[END_REF] runs in time O * (1.9977 n ). Even for digraphs of maximum total degree at most 4, the best previous result [START_REF] Venkatesh Raman | Efficient exact algorithms through enumerating maximal independent sets and other techniques[END_REF] was a running time of O * (1.945 n ). Observing that maximum total degree at most 4 implies maximum indegree at most 2 or maximum outdegree at most 2, our algorithm is both faster than the one given in [START_REF] Venkatesh Raman | Efficient exact algorithms through enumerating maximal independent sets and other techniques[END_REF], and encompasses a larger class of digraphs. Third, easy examples show that digraphs with outdegree 2 can have at least 1.4142 n minimal directed feedback vertex sets [START_REF] Schwikowski | On enumerating all minimal solutions of feedback problems[END_REF].

Star Height of Regular Expressions

As it turns out, the cycle rank of digraphs is intimately related to structural and descriptional complexity aspects of regular expressions. The star height of a regular language L, denoted by h(L), is defined as the minimum nesting depth of stars in any regular expression describing L. The following relation between star height and the cycle rank of nondeterministic finite automata (NFAs) was shown already in the seminal paper on star height [START_REF] Eggan | Transition graphs and the star height of regular events[END_REF].

Theorem 18 (Eggan's Theorem) Let L be a regular language. Then h(L) = min{ r(A) | A is an NFA accepting L }.

Here, r(A) denotes the cycle rank of the digraph underlying the transition structure of A.

As an aside, Eggan's Theorem was recently used to obtain a powerful lower bound technique for the minimum required length of regular expressions for a given regular language:

Lemma 19 (Star Height Lemma, [START_REF] Gruber | Finite automata, digraph connectivity, and regular expression size[END_REF]) Let L be a regular language. If L admits a regular expression of length n, then n ≥ 2 Ω(h(L)) .

The gist of the proof is that each regular expression can be converted into an equivalent NFA of comparable size, but whose transition structure is only poorly connected. The result then follows using Eggan's Theorem. In [START_REF] Gruber | Finite automata, digraph connectivity, and regular expression size[END_REF], this method was used to prove the unexpected result that complementing regular languages can cause a doubly-exponential blow-up in the minimum required regular expression length.

Of course, the minimum in Eggan's Theorem is taken over infinitely many NFAs, and indeed for more than two decades, it was unknown whether there exists an algorithm deciding the STAR HEIGHT problem: given a deterministic finite automaton (DFA) A and an integer k, determine whether the star height of L(A) is at most k, a question raised in [START_REF] Eggan | Transition graphs and the star height of regular events[END_REF]. Although the problem is now known to be decidable, the best known upper bound (iv) to date is EXPSPACE [START_REF] Daniel | On the complexity of the relative inclusion star height problem[END_REF]. To the best of our knowledge, nontrivial lower bounds are known only for the case where the input is specified succinctly, as an NFA: Determining the star height of a language specified as an NFA is PSPACE-hard [START_REF] Harry | Computational parallels between the regular and context-free languages[END_REF]. Yet, as illustrated in [START_REF] Harry | Computational parallels between the regular and context-free languages[END_REF], a large multitude of natural questions about the language accepted by a given NFA is PSPACE-hard, whereas the corresponding questions often become computationally easy if a DFA is given. Therefore, such a hardness result renders more service to understanding the effect of succinct input descriptions than to understanding the computational nature of the core problem at hand. That is why we deliberately stick to the convention to specify the input as a DFA.

Here we settle the complexity of the star height problem for a subclass of the regular languages, namely the bideterministic languages. The decision problem BIDETERMINISTIC STAR HEIGHT is defined as follows: Given a bideterministic finite automaton A and an integer k, decide whether the star height of L(A) is at most k.

Bideterministic finite automata have the special property that the star height problem of bideterministic languages boils down to determining the cycle rank of a digraph. The following theorem is proved in [START_REF] Mcnaughton | The loop complexity of pure-group events[END_REF]:

Theorem 20 (McNaughton's Theorem) Let L be a bideterministic language, and let A be the minimal trim (i.e., without a dead state) DFA accepting L. Then h(L) = r(A).

On the positive side, the algorithmic results from the previous section easily translate to a formal language setup using McNaughton's Theorem. For approximating STAR HEIGHT, we have to resort to Eggan's Theorem, giving only an O(n)-approximation. In the bideterministic case, we have the following counterpart to Theorem 13: Theorem 21 The BIDETERMINISTIC STAR HEIGHT problem admits a polynomial-time approximation within a factor of O((log n) 3/2 ).

2

We also have a natural counterpart to Theorem 16:

Theorem 22 Let A be a bideterministic finite automaton with n states over an input alphabet of size k.

Then the star height of L(A) can be computed exactly, in time and space O * ((2 -ε) n ), where ε is a constant depending on k. In particular, for the case of binary input alphabets, the star height can be computed in time and space O * (1.9129 n ). 2

On the negative size, also the NP-hardness result for CYCLE RANK translates to its language-theoretic counterpart. Moreover, we show that already the case of binary input alphabets is that hard:

Theorem 23 The BIDETERMINISTIC STAR HEIGHT problem is NP-complete, and this still holds when restricted to bideterministic automata over binary input alphabets.

Proof: We first show NP-completeness for the case of unbounded alphabet size, and then provide a polynomial-time reduction to the case of binary alphabets.

For membership in NP, we use McNaughton's Theorem (Theorem 20) to reduce the problem to CY-CLE RANK, and the latter is in NP by Theorem 12.

To establish NP-hardness, we reduce from the problem of determining for a strongly connected digraph G = (E, V ) and an integer k whether the cycle rank is at most k, which is NP-hard by Theorem 12. For a vertex v in V , define

L(G, v) = { w ∈ E * | w is a walk in G starting and ending in v }.
A deterministic finite automaton A accepting L(G, v) has V as set of states and for each edge (x, y) ∈ E a transition labeled (x, y) from x to y. The start and only accepting state is v. It is readily verified that A accepts L(G, v), is bideterministic, and that A is the minimal trim DFA for this language. By construction, r(A) = r(G), and r(A) = h(L) by Theorem 20. This completes the NP-completeness proof for unbounded alphabet size.

We turn to the case of binary alphabets. Given an instance (A, k) of BIDETERMINISTIC STAR HEIGHT, we construct in polynomial time a bideterministic finite automaton B over the alphabet {a, b}, such that the star height of B equals the star height of A. Assume the input alphabet of A is Σ = {a 1 , a 2 , . . . , a r }. The automaton B will accept the homomorphic image of L(A) under the homomorphism ρ : Σ → {a, b} given by ρ(a i ) = a i b r+1-i , for 1 ≤ i ≤ r. It is known [START_REF] Mcnaughton | The loop complexity of regular events[END_REF] that ρ preserves star height, that is, for every regular language L, the image of L under ρ is of the same star height as L. It remains to construct, in polynomial time, a bideterministic automaton B accepting ρ(L(A)): automaton B will have the states of A, plus some extra states. For each state q copied from A, we add r states q + 1 , q + 2 , . . . q + r and r more states q - 1 , q - 2 , . . . q - r to the state set of B. The transition relation of B is given by requiring that whenever there is a transition p ai → q in A, then B admits the sequence of transitions

p a → p + 1 a → p + 2 • • • a → p + i b → q - r-i b → • • • q - 2 b → q - 1 b → q.
There are no other transitions in B. By construction, B accepts ρ(L(A)). It is easily verified that if A is bideterministic, then so is B. 2

Returning again to CYCLE RANK, we observe that the digraph underlying a bideterministic automaton over a binary alphabet always has maximum outdegree at most 2 and maximum total degree at most 4. The correspondence given by McNaughton's Theorem between bideterministic automata and digraphs yields the following consequence:

Corollary 24 The CYCLE RANK problem restricted to digraphs of maximum outdegree at most 2 and total degree at most 4 remains NP-complete. 2

Conclusion

In this work, we explored measures for the complexity of digraphs, and their applications. We paid particular attention to the cycle rank of digraphs and its relation to other digraph complexity measures, as well as its connection to the star height of regular languages. A tabular summary of our main algorithmic results is given in the Appendix. Regarding cycle rank, the undirected case seems to be much better understood than the general case. An intriguing open question is whether the cycle rank problem is fixed-parameter tractable. This is known to be true on undirected graphs, see [START_REF] Hans | Rankings of graphs[END_REF].

Regarding the star height problem, the picture is even less clear. The main problem, namely the decidability status, has been settled for more than 20 years. Still, the computational complexity of this problem is not well understood. From the viewpoint of a computational complexity, we studied the "easiest hard case", and showed that (the non-succinct version of) this problem is NP-hard. Currently the best upper bound [START_REF] Daniel | On the complexity of the relative inclusion star height problem[END_REF] is EXPSPACE. Tightening the eminent gap between these bounds is certainly a challenging theme for further research.

Example 8

 8 Consider again the digraph G in Figure 1. The sequence {A, B} {B, C} {D} forms a directed path decomposition, and the sequence {A, B} {B} {B, C} {C} ∅ {D} forms a normal directed path decomposition for G. Furthermore, observe that the intersection of the two adjacent bags {B} and {B, C} forms a weak balanced separator.

  C 1 , . . . C p denote those strongly connected components of the digraph G[W ∪X] for which G[W ∪{s}∪ i C i ] is strongly connected, and let D 1 , . . . , D r denote the remaining strongly connected components in G[W ∪ X]. The elimination forest for G[W ∪ X] contains an elimination tree for each G[C i ], and for each G[D i ]. Make up a new root (s, X ∪ {s}), and attach the directed elimination trees for the digraphs G[C i ] as children to that new root. This gives a directed elimination tree for G[W ∪ {s} ∪ i C i ]. The union of this tree with the directed elimination trees for the strongly connected components D 1 , . . . , D r yields a directed elimination forest for G[W ∪ X ∪ s]. This completes the description of the subroutine for extending the forest.

(iii) The notion used in[START_REF] Kintali | Approximation algorithms for directed width parameters[END_REF] corresponds to our notion of weak separator number up to a constant factor.

(iv) The noted upper bound holds more generally for a given NFA if also an NFA accepting the complement language is provided as part of the input. Recall that complementing a DFA does not affect its size, whereas complementing an NFA can cause an exponential blow-up in the required number of states[START_REF] Holzer | Nondeterministic descriptional complexity of regular languages[END_REF].

Acknowledgements

The author would like to thank Markus Holzer for carefully reading an earlier draft of this paper, and for providing some valuable suggestions. Also thanks to the referee and to the editor for some useful hints.

Computational Aspects of Cycle Rank

Computational Complexity

We turn to algorithmic questions. First, we classify the computational complexity of the decision problem CYCLE RANK: Given a digraph G and an integer k, determining whether the cycle rank of G is at most k.

Theorem 12

The CYCLE RANK problem is NP-complete, and this still holds when requiring that the input digraph is strongly connected.

Proof: Membership in NP can be seen by the equivalent definition using directed elimination forests: Let G = (V, E) denote the given digraph. Every directed elimination forest for G contains at most |V | tree vertices, and each tree vertex is of size is at most |V |. A nondeterministic polynomial-time bounded Turing machine can guess such a witness, and then verify that it indeed constitutes a directed elimination forest of height at most k for G.

For NP-hardness, we use a corresponding result known for the undirected case. Given a symmetric loop-free digraph G, it is easy to see (e.g. by [START_REF] Nešetřil | Tree-depth, subgraph coloring and homomorphism bounds[END_REF]Lem. 2.2]) that an undirected elimination forest of height k + 1 in the sense of [START_REF] Hans | Approximating treewidth, pathwidth, frontsize, and shortest elimination tree[END_REF][START_REF] Nešetřil | Tree-depth, subgraph coloring and homomorphism bounds[END_REF] corresponds to a directed elimination forest of height k in our sense (the term +1 accounts for the slightly different notion of height used in [START_REF] Nešetřil | Tree-depth, subgraph coloring and homomorphism bounds[END_REF]). However, determining the minimum height among all undirected elimination forests is NP-complete, also for (strongly) connected undirected graphs [START_REF] Hans | Approximating treewidth, pathwidth, frontsize, and shortest elimination tree[END_REF].

2

Using tools from formal language theory, we will prove later that NP-hardness still holds for digraphs of maximum outdegree at most 2 and of maximum total degree at most 4.

Approximate Computation

How do we cope with this negative result? One possibility is to look for an approximate solution. Indeed, it is known that for undirected graphs, the cycle rank problem admits an input-dependent polynomial-time approximation algorithm [START_REF] Hans | Approximating treewidth, pathwidth, frontsize, and shortest elimination tree[END_REF]. In the following, we devise a more general approximation algorithm, which also addresses the case of unsymmetric digraphs. The basic pattern of our algorithm is divide-and-conquer along separators.

Theorem 13

The CYCLE RANK problem admits a polynomial-time approximation within a factor of O((log n) 3/2 ).

Proof:

The following recursive procedure computes a directed elimination forest for the induced subgraph G[W ], where W ⊂ V is passed as parameter to the procedure.

If G[W ] consists of several strongly connected components, apply the procedure recursively to each of these; The union of these results gives a directed elimination forest for G Bad news. NP-complete (Thm. 12). Problem is NP-hard already for digraphs of maximum outdegree 2 and maximum total degree 4 (Cor. 24); NP-hard also for some classes of undirected graphs (e.g., bipartite and cobipartite) [START_REF] Hans | Rankings of graphs[END_REF].

DIRECTED FEEDBACK VERTEX SET

Instance. A digraph G and an integer k.

Question. Does G admit a directed feedback vertex set of cardinality at most k?

Good news. For digraphs with maximum outdegree at most 2, exact solution can be computed in time O * (1.9129 n ) (Thm. 17); and in time O * (1.9977 n ) for unbounded outdegree [START_REF] Razgon | Computing minimum directed feedback vertex set in O * (1.9977 n )[END_REF]. Problem is fixed-parameter tractable [START_REF] Chen | A fixed-parameter algorithm for the directed feedback vertex set problem[END_REF].

Bad news. NP-complete, already for digraphs of maximum outdegree 2 [16, Problem GT7].

BIDETERMINISTIC STAR HEIGHT

Instance. A bideterministic finite automaton A and an integer k.

Question. Is the star height of L(A) at most k?

Good news. Approximable within O((log n)

STAR HEIGHT

Instance. A deterministic finite automaton A and an integer k.

Question. Is the star height of L(A) at most k?

Good news. Problem is decidable [START_REF] Hashiguchi | Algorithms for determining relative star height and star height[END_REF]. Exact solution can be computed within exponential space and doubly exponential time [START_REF] Daniel | On the complexity of the relative inclusion star height problem[END_REF].

Bad news. NP-hard, already for binary alphabets (Thm. 23). Problem is PSPACE-hard if input given by an nondeterministic finite automaton in place of a deterministic one [START_REF] Harry | Computational parallels between the regular and context-free languages[END_REF].


Ben Seamone
email: bseamone@math.carleton.ca

Brett Stevens

Sequence variations of the 1-2-3 Conjecture and irregularity strength

Keywords: edge weighting, vertex colouring, 1-2-3 Conjecture

conjectured that, for any connected graph G on at least three vertices, there exists an edge weighting from {1, 2, 3} such that adjacent vertices receive different sums of incident edge weights. Bartnicki, Grytczuk, and Niwcyk (2009) made a stronger conjecture, that each edge's weight may be chosen from an arbitrary list of size 3 rather than {1, 2, 3}. We examine a variation of these conjectures, where each vertex is coloured with a sequence of edge weights. Such a colouring relies on an ordering of E(G), and so two variations arise -one where we may choose any ordering of E(G) and one where the ordering is fixed. In the former case, we bound the list size required for any graph. In the latter, we obtain a bound on list sizes for graphs with sufficiently large minimum degree. We also extend our methods to a list variation of irregularity strength, where each vertex receives a distinct sequence of edge weights.

Introduction and Brief Survey

A graph G = (V, E) will be simple and loopless unless otherwise stated. Throughout, we write [k] for the set {1, 2, . . . , k}. An edge k-weighting, w, of G is a an assignment of a number from [k] to each e ∈ E(G), that is w : E(G) → [k]. Karoński, Łuczak, and Thomason [START_REF] Karoński | Edge weights and vertex colours[END_REF] conjectured that, for every graph without a component isomorphic to K 2 , there is an edge 3-weighting such that any two adjacent vertices have different sums of incident edge weights. If an edge k-weighting gives rise to such a proper vertex colouring, we say that the weighting is a vertex colouring by sums. We will denote by χ e Σ (G) the smallest value of k such that a graph G has an edge k-weighting which is a vertex colouring by sums (this notation is a slight modification of that proposed by Győri and Palmer in [START_REF] Győri | A new type of edge-derived vertex coloring[END_REF]). We say that a graph G is nice if no component is isomorphic to K 2 . We may express Karoński, Łuczak, and Thomason's conjecture (frequently called the "1-2-3 Conjecture") as follows:

Ben Seamone and Brett Stevens 1-2-3 Conjecture (Karoński, Łuczak, Thomason [START_REF] Karoński | Edge weights and vertex colours[END_REF]). If G is nice, then χ e Σ (G) ≤ 3.

One may also obtain a vertex colouring from an edge k-weighting by considering the products, sets, or multisets of incident edge weights. The smallest k for which a graph G has an edge k-weighting which is a proper vertex colouring by products, sets or multisets will be denoted χ e Π (G), χ e s (G) and χ e m (G), respectively. The best known bounds for these graph parameters are, for any nice graph G, χ e Σ (G) ≤ 5 [START_REF] Kalkowski | Vertex-coloring edge-weightings: towards the 1-2-3conjecture[END_REF], χ e m (G) ≤ 4 [START_REF] Addario-Berry | Vertex colouring edge partitions[END_REF], χ e Π (G) ≤ 5 [START_REF] Skowronek-Kaziów | 1,2 conjecture -the multiplicative version[END_REF], and χ e s (G) = log 2 χ(G) + 1 [START_REF] Győri | A new type of edge-derived vertex coloring[END_REF]. It is shown in [START_REF] Addario-Berry | Vertex colouring edge partitions[END_REF] that if δ(G) ≥ 1000, then χ e m (G) ≤ 3. In [START_REF] Addario-Berry | Degree constrained subgraphs[END_REF] it is shown that, asymptotically almost surely, χ e Σ (G) ≤ 2. One may also allow each vertex to receive a weight from [k], in addition to the edge weights; such weightings of G are called total k-weightings. Vertex colourings via total weightings are obtained by considering the weights of the edges incident to a vertex as well as the vertex's weight itself. The smallest k for which a graph G has a total k-weighting which is a proper vertex colouring by sums, products, sets or multisets is denoted χ t Σ (G), χ t Π (G), χ t s (G) and χ t m (G), respectively. The following conjecture motivates the study of total weightings and vertex colouring by sums:

1-2 Conjecture (Przybyło, Woźniak [START_REF] Przybyło | On a 1,2 conjecture[END_REF]). For every graph G, χ t Σ (G) ≤ 2.

Clearly, any upper bound on an edge k-weighting parameter is an upper bound on its corresponding total k-weighting parameter. The best known improvements on the bounds above are, for an arbitrary graph G, χ t Σ (G) ≤ 3 [START_REF] Kalkowski | A note on the 1,2-conjecture[END_REF] (in fact, only vertex weights 1 and 2 are required) and χ t Π (G) ≤ 3 [START_REF] Skowronek-Kaziów | 1,2 conjecture -the multiplicative version[END_REF]. Clearly both χ t Σ (G) and χ t Π (G) are upper bounds on χ t m (G), so we have that χ t m (G) ≤ 3 as well. All of the above graph colouring parameters have natural list generalizations. Rather than choosing a weight from [k] for each edge (vertex), one must choose a weight for each edge (vertex) from a set of k arbitrary real numbers independently assigned to each edge (vertex). We call such weightings edge k-listweightings and total k-list-weightings (in the case where vertex weights are included). Given a graph G, the smallest k such that any assignment of lists of size k to E(G) permits an edge k-list-weighting which is a vertex colouring by sums is denoted ch e Σ (G); each of the parameters above generalizes similarly. The following conjecture proposes a stronger version of the 1-2-3 Conjecture:

List 1-2-3 Conjecture (Bartnicki, Grytczuk, Niwcyk [4]). If G is a nice graph, then ch e Σ (G) ≤ 3.
It is shown in [START_REF] Seamone | On weight choosability and additive choosability numbers of graphs[END_REF][START_REF] Seamone | Derived Colourings of Graphs[END_REF] that ch e Σ (G) ≤ 2∆(G) + 1 for any nice graph G. However, there is no known integer K such that ch e Σ (G) ≤ K for any nice graph G. Bartnicki et al. [START_REF] Bartnicki | Weight choosability of graphs[END_REF] establish that ch e Σ (G) ≤ 3 if G is complete, complete bipartite, or a tree. The analogous problem for digraphs is also solved in [START_REF] Bartnicki | Weight choosability of graphs[END_REF] and [START_REF] Khatirinejad | Digraphs are 2-weight choosable[END_REF]. In the former, a constructive method is used to show that ch e Σ (D) ≤ 2 for any digraph D; the latter provides an alternate proof using algebraic methods.

The multiset version of the 1-2-3 Conjecture is a natural relaxation of the requirement that adjacent vertices receive distinct sums. This paper is concerned with a further relaxation of the multiset version, where one requires that adjacent vertices receive distinct sequences (given some reasonable method of constructing a sequence from weights of incident edges). In Section 2, we introduce the problem of colouring V (G) by sequences of weights from incident edges. In Section 3, we study colouring by sequences with the requirement that every vertex receives a distinct sequence rather than only adjacent vertices; this is a variation of a well studied parameter known as the irregularity strength of a graph. Wherever possible, we study the stronger "list versions" of these weighting problems.

Vertex Colouring by Sequences

We must first define how to induce a sequence of weights from an edge weighting. Let E(G) = {e 1 , e 2 , . . . , e m } be the edge set of a graph G, ≺ a total order on E(G), and let w : E(G) → S be an edge weighting of G. For a vertex v ∈ V (G), let I v = {i : e i v}. A colouring of V (G) from w by sequences is obtained by constructing a sequence for each v ∈ V (G) by taking the multiset {{w(e i ) : i ∈ I v }} and ordering the elements according to w(e i ) ≺ w(e j ) if and only if e i ≺ e j .

For example, consider C 5 with vertices and edges labelled as in Figure 1: We will consider two edge orderings of this graph and attempt to properly colour the vertices by sequences for each using only two edge weights.

v 4 v 3 e 3
If the edges are ordered e 1 ≺ e 2 ≺ e 3 ≺ e 4 ≺ e 5 , then there is an edge 2-weighting w : E(C 5 ) → {a, b} which is a proper colouring by sequences, given in Table 1:

Weighting Colouring w(e 1 ) = a c(v 1 ) = aa w(e 2 ) = b c(v 2 ) = ab w(e 3 ) = a c(v 3 ) = ba w(e 4 ) = b c(v 4 ) = ab w(e 5 ) = a c(v 5 ) = ba
Tab. 1: An edge 2-weighting that properly colours V (C5) by sequences However, for the ordering e 1 ≺ e 3 ≺ e 5 ≺ e 2 ≺ e 4 , the vertex colours given by a weighting w are c(v 1 ) = w(e 1 )w(e 5 ), c(v 2 ) = w(e 1 )w(e 2 ), c(v 3 ) = w(e 3 )w(e 2 ), c(v 4 ) = w(e 3 )w(e 4 ), c(v 5 ) = w(e 5 )w(e 4 ).

In order to have a proper colouring, w(e 5 ) = w(e 2 ),

(1) w(e 1 ) = w(e 3 ),

(2) w(e 2 ) = w(e 4 ),

(3) w(e 3 ) = w(e 5 ).

(

) 4
If w is a weighting with only two edge weights, then inequalities (1) and (3) imply that w(e 4 ) = w(e 5 ), while ( 2) and ( 4) imply that w(e 1 ) = w(e 5 ). Together, this forces c(v 1 ) = c(v 5 ), and hence C 5 cannot be properly vertex coloured by sequences with two edge weights for the ordering e 1 ≺ e 3 ≺ e 5 ≺ e 2 ≺ e 4 .

Hence, the order of the edges plays a significant role in vertex colouring by sequences. As such, we consider the following two problems: Problem 1. Given a graph G, what is the smallest value of k such that there is an edge k-weighting of G which gives a proper colouring of V (G) by sequences for some ordering of E(G)? Problem 2. Given a graph G, what is the smallest value of k such that there is an edge k-weighting of G which gives a proper colouring of V (G) by sequences for every ordering of E(G)? These parameters will be called χ e σ * (G) and χ e σ (G), respectively. For the list-weighting variations, ch e σ * (G) and ch e σ (G) will be used.

Colouring by sequences for some E(G) ordering

The case when one is free to choose an "optimal" ordering of the edges of a graph G is the easier of the two problems to analyze. In this section, Problem 1 is solved completely for edge weightings and total weightings for graphs and multigraphs. We begin with the simple case of cycles.

Proposition 2.1.

If n ≥ 3, ch e σ * (C n ) = 2.
Proof:

The n = 3 case is trivial. Let n ≥ 4, V (C n ) = {v 1 , . . . , v n }, and E(C n ) = {v i v i+1 : 1 ≤ i ≤ n} with index addition taken mod n. Let e i = v i v i+1 .
For each i = 1, . . . , n, let L ei be a set of 2 elements. Choose w(e 2 ) ∈ L e2 and w(e n ) ∈ L en such that w(e 2 ) = w(e n ). For each i = 3, . . . , n -1, let w(e i ) ∈ L ei \ {w(e i-1 )} and let w(e 1 ) ∈ L e1 \ {w(e n-1 )}. The resulting vertex colouring by sequences is proper.

The prefix of length t of a sequence a

1 a 2 • • • a n is the subsequence a 1 a 2 • • • a t . A vertex colouring by sequences, c, is prefix distinguishing if, for any uv ∈ E(G) with d(u) ≥ d(v) ≥ 2, c(v) is not the prefix of c(u); in other words, if c(v) = a 1 a 2 • • • a k and c(u) = b 1 b 2 • • • b l for some l ≥ k, then there exists an index i, 1 ≤ i ≤ k, such that a i = b i .
Clearly any prefix distinguishing vertex colouring by sequences is also a proper vertex colouring. By proving a stronger statement about prefix distinguishing colourings by sequences, one can show that ch e σ * (G) ≤ 2 for every nice graph G. Note that we use |S| to denote the length of a sequence S. Theorem 2.2. Let G be a nice connected graph and for each e ∈ E(G) let L e be a set of two real numbers. There is an ordering of E(G) and values w(e) ∈ L e , e ∈ E(G), such that w is a prefix distinguishing vertex colouring by sequences.

Proof: We prove the statement by induction on |V

(G)|. The theorem is true if |V (G)| = 3; assume |V (G)| ≥ 4. Let d = δ(G), let x ∈ V (G) be a vertex of minimum degree, and let G = G -x (note that no component of G is isomorphic to K 2 ).
For various values of d, it will be shown that an edge weighting w which gives a prefix distinguishing vertex colouring by sequences of G , say c , can be extended to G. Let w and c denote the extended edge weighting and vertex colouring of G, respectively. In each case we consider, the ordering of the edges of E(G ) which gives c is extended by appending the edges incident to x to the end of the ordering (and hence, the weights of these edges to the ends of the colours of vertices in N G (x)).

Suppose d = 1, and let To obtain a similar result for a total k-weighting of a graph G, create a new graph H by adding a leaf to each v ∈ V (G) and assigning the new leaf edge incident to v the list L v . Applying Theorem 2.2 to H gives an ordering of the vertices and edges of G and a total k-list-weighting of G which colours V (G) by sequences. Hence, we have the following corollary: Corollary 2.4. For any graph G, ch t σ * (G) ≤ 2. Theorem 2.2 also easily extends to multigraphs. We call a multigraph nice if it has no loopless connected component with exactly two vertices.

N G (x) = {y}. If d G (y) = 1,
Theorem 2.5. If M is a nice, loopless multigraph, then there is an ordering of E(M ) such that, for any assignment of lists of size 2 to the edges of M , there exists an edge 2-list-weighting w which gives a prefix distinguishing vertex colouring by sequences.

Proof: Let G be the underlying simple graph of M and apply Theorem 2.2 to G; denote by c the resulting colouring of G. The edges of E(M ) \ E(G) will be assigned to the end of the ordering of E(G). For every

uv ∈ E(M ) such that d G (u) ≥ d G (v) ≥ 2, any assignment of weights to edges in E(M ) \ E(G) preserves the prefix distinguishing vertex colouring. Consider x ∈ V (G) with d G (x) = 1. If d M (x) = 1
as well, then any assignment of weights to the remaining edges will preserve the prefix-distinguishing vertex colouring. If d M (x) ≥ 2, then let e ∈ E(M ) \ E(G) be incident to x and let y be the other end of e. Choosing w(e) different from the second entry in c(y) preserves the prefix-distinguishing vertex colouring.

The following corollary follows in the same manner as Corollary 2.4.

Corollary 2.6. If M is a nice multigraph, then there is an ordering of E(M ) ∪ V (M ) such that, for any assignment of lists of size 2 to the edges and vertices of M , there exists a total 2-list-weighting w which gives a prefix distinguishing vertex colouring by sequences.

Colouring by sequences for any E(G) ordering

We now turn our attention to the problem of determining χ e σ (G), χ t σ (G), ch e σ (G), and ch t σ (G) for a graph G. Each bound is clearly bounded above by its multiset counterpart (i.e. χ e σ (G) ≤ χ e m (G)). In general, it is not clear for which graphs these bounds are tight. For any graph G, χ t σ (G) ≤ 3. We make the following conjectures, in light of the conjectures stated in the opening section:

Conjecture 1. If G is a nice graph then ch e σ (G) ≤ 3. Conjecture 2. For any graph G, ch t σ (G) ≤ 2.
Conjectures 1 and 2 are verified here for d-regular graphs of sufficiently large degree and for general graphs with δ(G) sufficiently large in terms of ∆(G).

We begin with a few necessary definitions. For a set of events {A i : i ∈ I} in a probability space and a subset K ⊆ I, define A K := i∈K A i and A K := i∈K A i . Let J ⊆ I \ {i}. The event A i is mutually independent of the set of events {A i : i ∈ J} if, for every set J ⊆ J,

P(A i ∩ A J ) = P(A i ) × P(A J ),
or, equivalently, P(A i A J ) = P(A i ).

The main tool which will be used is the well known and powerful Lovász Local Lemma.

Lovász Local Lemma (Erdős, Lovász [START_REF] Erdős | Problems and results on 3-chromatic hypergraphs and some related questions[END_REF]). Let {A i : i ∈ I} be events in a probability space, and for each A i let J i ⊆ I be a set of indices such that A i is mutually independent of {A j : j / ∈ J i ∪ {i}}. If there exist real numbers 0 < x i < 1 for each i ∈ I such that P(A i ) < x i j∈Ji (1 -x j ), then

P A I ≥ i∈I (1 -x i ) > 0.
For an event A i , the set J i indicated in the Lovász Local Lemma is called the dependency set of A i . If the maximum size of a dependency set, taken over all A i , is D, then setting x i = 1 D+1 in the Lovász Local Lemma for each i ∈ I gives the symmetric version of the Local Lemma.

Symmetric Local Lemma (Spencer [START_REF] Spencer | Asymptotic lower bounds for Ramsey functions[END_REF]). Let {A i : i ∈ I} be a set of events in a probability space, and for each A i let J i ⊆ I be a set of indices such that A i is mutually independent of {A j : j / ∈ J i ∪ {i}}. If |J i | ≤ D for all i ∈ I and P(A i ) < 1 e(D+1) for all i ∈ I, then P A I > 0.

Let {A e : i ∈ E(G)} be a set of events in a probability space which are indexed by the edge set of a graph G. We say that an edge e ∈ E(G) is covered by the event A uv if e is incident to either u or v, and uncovered otherwise.

By applying the Symmetric Local Lemma, a bound for the list variation of Problem 2 can be obtained:

Theorem 2.8. Let G be a graph with minimum degree δ and maximum degree ∆.

If δ > log 3 (2∆ 2 -2∆ + 1) + 2 then ch e σ (G) ≤ 3.
Proof: For each e ∈ E(G), let L e be a list of 3 elements associated with e. Fix an arbitrary ordering of E(G). Choose w(e) randomly from L e with uniform probability and let c(u) denote the resulting sequence of weights of edges incident to u ∈ V (G). For an edge uv ∈ E(G), let A uv denote the event that c(u) = c(v); we see that P(A uv ) ≤ 1/3 δ-1 . Let J uv ⊂ E(G) \ {uv} be the set of edges where j ∈ J uv if and only if A j covers uv or an edge incident to u or v, and j = uv; A uv is independent of {A e : e / ∈ J uv ∪ {uv}} since no edge incident to uv will have a weight determined by an event A e with e / ∈ J uv . Hence,

D = max{|J e | : e ∈ E(G)} ≤ 2(∆ -1) + 2(∆ -1) 2 = 2∆(∆ -1).
By the Symmetric Local Lemma, the result holds if

1 3 δ-1 < 1 e(2∆(∆ -1) + 1)
,

which is satisfied if δ > log 3 (2∆ 2 -2∆ + 1) + 2.
If two adjacent vertices have distinct degrees, then their associated sequences will certainly differ. Hence, regular graphs are of particular interest. The following corollary is easily obtained from Theorem 2.8.

Corollary 2.9. If G is a d-regular graph, d ≥ 6, then ch e σ (G) ≤ 3. A similar argument gives ch e σ (G) ≤ 4 if G is 5-regular, ch e σ (G) ≤ 5 if G is 4-regular, and ch e σ (G) ≤ 6 if G is 3-regular.
We now consider total weightings. Since the List 1-2 Conjecture implies that two weights should suffice for a proper colouring by sums, we consider total 2-list-weightings. The upper bound on the probability of a bad event is 1/2 δ rather than 1/3 δ-1 ; the following bounds are obtained by similar arguments as those used to prove Theorem 2.8 and Corollary 2.9.

Theorem 2.10. Let G be a graph with minimum degree δ(G) = δ and maximum degree

∆(G) = ∆. If δ > log 2 (e(2∆ 2 -2∆ + 1)), then ch t σ (G) ≤ 2. In particular, if G is d-regular for d ≥ 9, then ch t σ (G) ≤ 2.
Finally, we examine ch e σ (M ) and ch t σ (M ) for a multigraph M . An application of the Local Lemma shows that as long as the maximum edge multiplicity is no more than the minimum degree less a logarithmic term in terms of maximum degree, then the bounds in Conjectures 1 and 2 can be obtained for multigraphs.

Theorem 2.11. Let M be a loopless multigraph with maximum edge multiplicity µ(G) = µ, minimum degree δ(G) = δ, and maximum degree ∆(G) = ∆.

(1) If µ < δ -1 -log 3 (2∆ 2 -2∆ + 1), then ch e σ (M ) ≤ 3.

(

) If µ < δ -1 2 -log 2 (2∆ 2 -2∆ + 1), then ch t σ (M ) ≤ 2. 2
Proof: (1) Let L e be a list of 3 elements associated with the edge e. Fix an arbitrary ordering of E(G).

For an edge e, choose its weight w(e) randomly from L e with uniform probability. Let c(u) denote the resulting sequence of weights of edges incident to u ∈ V (G). For an edge e = uv, let A e denote the event that c(u

) = c(v) If u, v ∈ V (G)
are adjacent vertices, and l is the number of edges between them, then

P(A uv ) ≤ 1/k δ-l ≤ 1/k δ-µ .
The size of the dependency set J e is the number of adjacent pairs of vertices from which one vertex is of distance at most one from u or v, and hence the maximum size of a dependency set is D ≤ 2∆(∆ -1).

By the Symmetric Local Lemma, the first result holds if

1 3 δ-µ < 1 e(2∆(∆ -1) + 1)
.

(2) Applying the same argument to a random list total weighting from lists of size 2, we need to satisfy the following inequality:

1 2 δ-µ+1 < 1 2∆(∆ -1) + 1)
.

By considering edge k-weightings rather than edge k-list-weightings one can reduce the size of a bad event's dependency set in graphs with no short cycles, and hence obtain improved bounds.

Given an ordering of the edges of a graph G, denote by e u i the i th edge incident to u with respect to the ordering of E(G). A set of events K ⊆ {A e : e ∈ E(G) \ {uv}} leaves the edge uv ∈ E(G) open if at least one of {e u i , e v i } \ {uv} is left uncovered by K for each 1 ≤ i ≤ max{deg(u), deg(v)}. Lemma 2.12. Let G be a graph with ordered edge set E(G) = {e 1 , . . . , e m }. Let w : E(G) → [k] be a random edge k-weighting where, for each e ∈ E(G), w(e) is chosen with uniform probability from [k]; denote by c(u) the resulting sequence of edge weights associated with u ∈ V (G). For an edge uv ∈ E(G), let A uv be the event that c(u) = c(v). If there exists a set of events K ⊆ {A e : e ∈ E(G) \ {uv}} such that K leaves uv open, then A uv is mutually independent of K.

Proof: It suffices to prove that P(A uv K) = P(A uv ), since any proper subset of K leaves more edges adjacent to uv uncovered than does

K. If deg(u) = deg(v), then P(A uv ) = P(A uv K) = 0.
Assume deg(u) = deg(v) = d and suppose that, for some i, uv = e u i = e v i . Clearly

P(A uv ) = 1 k d-1 . Let U = {j : e u j is uncovered by K} \ {uv} V = {j : e v j is uncovered by K} \ {uv}. Since uv is left open by K, U ∪ V = [d] \ {i}. It follows that P(A uv K) = 1 k |U | k |U ∩V | k |V | = 1 k |U | 1 k |V \U | = 1 k |U ∪V | = 1 k d-1 = P(A uv ).
If uv = e u r = e v s for some r = s, then

P(A uv ) = 1 k d-2 × k k 3 = 1 k d . Again, let U = {j : e u j is uncovered by K} \ {uv} (5)
and

V = {j : e v j is uncovered by K} \ {uv}. ( 6
)
Since uv is left open by A K , r ∈ V and s ∈ U , and so

P(A uv K) = 1 k |U \{s}| k |U ∩V \{r,s}| k |V \{r}| P w(uv) = w(e u r ) = w(e v s ) = 1 k |U |\{s} 1 k |V \U \{r}| 1 k 2 = 1 k |U ∪V \{r,s}| 1 k 2 = 1 k d-2 × 1 k 2 = P(A uv ).
Note the need for an edge k-weighting rather than an edge k-list-weighting in Lemma 2.12; it provides equality between P(A uv ) and 1 k d-1 when uv = e u i = e v i for some index i, which is required to show that P(A uv K) = P(A uv ). Theorem 2.13. Let G be a graph with minimum degree δ(G) = δ and maximum degree ∆(G) = ∆ and girth at least 5. If δ > log 3 (∆ 2 -∆ + 1) + 2 then χ e σ (G) ≤ 3.

Proof: Fix an arbitrary ordering of E(G) and for an edge e, choose its weight w(e) randomly from {1, 2, 3} with uniform probability. Let c(u) denote the resulting sequence of weights of edges incident to u ∈ V (G).

For an edge uv ∈ E(G), let A uv denote the event that c(u) = c(v). Let J(uv) be the set of edges of distance at most 1 from u not incident to v, and let L(uv) = E(G) \ J(uv) \ {uv}. Since the girth of G is at least 5, the distance from u to any end of an edge is L(uv) is at least 2. This implies that all edges incident to u except uv are left uncovered by the events {A l : l ∈ L(uv)} := K uv , and hence uv is left open by K uv . By Lemma 2.12, this implies that A uv is mutually independent of K uv ; let J uv = J(uv) be the dependency set for A uv . Since the maximum size of a dependency set is

D = max{|J e | : e ∈ E(G)} ≤ (∆ -1) + (∆ -1) 2 = ∆(∆ -1), by the Symmetric Local Lemma the result holds if 1 3 δ-1 < 1 e(∆(∆ -1) + 1)
,

which is satisfied if δ > log 3 (∆ 2 -∆ + 1) + 2.
A (d, g)-graph is a d-regular graph with girth g. Theorem 2.13 implies that, for most (d, g)-graphs, three edge weights suffice for adjacent vertices to receive distinct sequences. Proof: If d = 3, then G is 3-colourable (by Brook's Theorem). In [START_REF] Karoński | Edge weights and vertex colours[END_REF] it is shown that if G is complete or 3-colourable then χ e Σ (G) ≤ 3, and so certainly χ e σ (G) ≤ 3. If d ≥ 5, then d > log 3 (d 2 -d + 1) + 2, and so we may apply Theorem 2.13.

Recall that χ e m (G) ≤ 3 if δ(G) ≥ 1000. As such, the only graphs for which it remains to show that χ e σ (G) ≤ 3 holds are those with small minimum degree (at most 1000) and comparatively large maximum degree (Ω(3 δ(G)/2 )).

The other theorems from this section have similar relaxations.

Theorem 2.15. Let G be a graph with minimum degree δ(G) = δ, maximum degree ∆(G) = ∆, and girth at least 5. If δ > log 2 (e(∆ 2 -∆ + 1)), then χ t σ (G) ≤ 2. In particular, if G is d-regular for d ≥ 7, then χ t σ (G) ≤ 2. Theorem 2.16. Let M be a loopless multigraph with maximum edge multiplicity µ(G) = µ, minimum degree δ(G) = δ, maximum degree ∆(G) = ∆, and girth at least 5.

(1) If µ < δ -1 -log 3 (∆ 2 -∆ + 1), then χ e σ (M ) ≤ 3.

(

) If µ < δ -1 2 -log 2 (∆ 2 -∆ + 1), then χ t σ (M ) ≤ 2. 2

Sequence irregularity strength

The irregularity strength of a graph G is the smallest integer k such that G has an edge k-weighting giving every vertex in G a distinct sum of incident edge weights. This well studied graph parameter was introduced by Chartrand et al. in [START_REF] Chartrand | Irregular networks[END_REF] where it was denoted s(G). In keeping with our notation, we denote the irregularity strength of G as s e Σ (G). Many variations of irregularity strength have been studied, including (but not limited to) requiring all vertices to receive distinct multisets, products, or sets of incident edge weights rather than distinct sums. These parameters are called the multiset irregularity strength, product irregularity strength and set irregularity strength, and they are denoted s e m (G), s e Π (G), and s e s (G) respectively. Note that a graph must be nice for these parameters to be well defined. Kalkowski, Karoński, and Pfender [START_REF] Kalkowski | A new upper bound for the irregularity strength of graphs[END_REF] show that s e Σ (G) ≤ 6n/δ for every nice graph G. Aigner et al. [START_REF] Aigner | Irregular assignments and vertex-distinguishing edge-colorings of graphs[END_REF] show that if G is a d-regular graph d ≥ 2, then s e m (G) ≤ (5e(d + 1)!n) 1/d . Burris and Schelp [START_REF] Burris | Vertex-distinguishing proper edge-colourings[END_REF] show that s e s (G) ≤ C ∆ max{n

1/i i : 1 ≤ i ≤ ∆(G)}
, where C ∆ is a constant relying only on ∆ and n i denotes the number of vertices of degree i in G (in fact, their edge weighting gives a proper edge-colouring as well). Only partial results are known for s e Π (G). The specific sequence irregularity strength of G, denoted s e σ * (G), is the smallest k such that there exists an ordering of E(G) and an edge k-weighting of G such every vertex receives a distinct induced sequence of incident edge weights. The general sequence irregularity strength of G, denoted s e σ (G), is the smallest k such that for every ordering of E(G) there exists an edge k-weighting of G such every vertex receives a distinct induced sequence of incident edge weights.

Each "irregularity strength type" parameter has the usual natural list variant -rather than each edge receiving a weight from {1, 2, . . . , k}, each is weighted from its own independently assigned list of k weights. The general sequence list-irregularity strength of a graph G is denoted ls e σ (G); the other parameters are extended similarly. As with the 1-2-3 Conjecture variations, one could weight the vertices of G as well as the edges; the corresponding parameters have "t" in place of "e" in the superscript (e.g. ls t σ (G) for total list-weightings which distinguish vertices by sequences for any ordering of E(G)).

Let M G := max{ n

1/i i : 1 ≤ i ≤ ∆(G)}.
Clearly s e σ * (G) ≥ M G , since any valid weighting from {1, 2, . . . , k} must satisfy k d ≥ n d for each degree d. We make the following conjectures, which motivates the results that follow:

Conjecture 3. If G is a nice graph, then s e σ (G) = M G . Conjecture 4. If G is a nice graph, then ls e σ (G) = M G .
The aforementioned bound on s e s (G) shows that there is a constant C such that s e σ * (G) ≤ s e σ (G) ≤ CM G . The bound on s e m (G) stated above gives a similar result for d-regular graphs. In fact, it follows quite easily from the proof details of Aigner et al. [START_REF] Aigner | Irregular assignments and vertex-distinguishing edge-colorings of graphs[END_REF] that their bound holds for ls e m (G). By directly considering colouring by sequences, these bounds can be further improved. For an edge e = uv, let A e denote the event that c(u) = c(v). By the same argument in the proof of Theorem 2.8, P(A e ) ≤ 1/k d-1 . For a non-adjacent pair of vertices p = {u, v}, P(A p ) ≤ 1/k d where A p is the event that c(u) = c(v).

The size of a dependency set J e for an edge e = uv is the number of edges of distance at most one from e plus the number of nonadjacent pairs of vertices containing u, v, or a neighbour of u or v; in other words, the total number of pairs of vertices containing at least one vertex in N (u) ∪ N (v). Hence,

|J e | ≤ n 2 - n -2d 2 = d(2n -2d -1).
Similarly, the size of J p is

|J p | ≤ n 2 - n -2d -2 2 = (d + 1)(2n -2d -3).
The probability of a bad event A ∈ {A e , A p : e ∈ E(G), p ∈ (V (G) × V (G)) \ E(G)} is As with our results on ch e σ (G) and ch t σ (G), these theorems generalize to graphs with arbitrary maximum and minimum degrees. In particular, we can show that there is a constant bound on general sequence list irregularity strength for graphs with sufficiently large minimum degree. As a consequence, there is a constant bound on general sequence list irregularity strength for graphs with sufficiently large minimum degree. The result follows by Theorem 3.3.

P(A) ≤ 1 k d-
Finally, we extend our irregularity strength results to multigraphs; the proof follows similarly to that of Theorem 2.11. (2) if µ < δ -log k (2e(∆ + 1)(n -∆)) + 1, then ls t σ (M ) ≤ k.

5 Fig. 1 :

 51 Fig. 1: A labelled 5-cycle

  let z be the neighbour of y in G and choose w(xy) ∈ L xy different from the second entry in c (z). Otherwise, d G (y) ≥ 2 and so, since c is prefix distinguishing, any choice of w(xy) ∈ L xy gives a prefix distinguishing colouring of V (G). Suppose d = 2. If G is a cycle, then the result follows by Proposition 2.1. Assume G is not a cycle. One may choose x such that one of its neighbours has degree at least 3 in G; call this neighbour y 1 . Let y 2 denote the other neighbour of x. There are two forbidden values of c(x) given by the length 2 prefixes of c (y 1 ) and c (y 2 ). If d G (y 2 ) = 1, let z denote the neighbour of y 2 in G and choose w(xy 2 ) ∈ L xy2 different from the second entry in c (z). There are then at least three possible colours for c(x), and so at least one permissible choice of w(xy 1 ) ∈ L xy1 . Suppose that d G (y 2 ) ≥ 2. There are at least four possible colours for c(x), and so at least one permissible choice of w(xy 1 ) ∈ L xy1 and w(xy 2 ) ∈ L xy2 , and hence at least two permissible choices which give the desired c. Suppose d ≥ 3, and let N G (x) = {y 1 , . . . y d }. Order E(G) beginning with the edges of E(G ) as ordered by the induction hypothesis, and adding xy 1 ≺ . . . ≺ xy d to the end of the ordering. Since c is prefix distinguishing in G , any choices of w(xy i ) ∈ L xyi , i = 1, . . . , d, will be prefix distinguishing in G except perhaps between x and some y i . Since δ(G ) ≥ d -1, the length of each sequence c (y i ) is at least d -1. Forbid x from receiving the same (d -1)-prefix as any of y 1 , y 2 , . . . , y d . There are 2 d-1 choices for the weights of xy 1 , . . . xy d-1 , and hence for the prefix of length d -1 of c(x). Since d ≥ 3, it follows that 2 d-1 > d and hence at least one (d -1)-prefix does not conflict with any of the (d -1)-prefixes of the colours assigned to y 1 , y 2 , . . . , y d . Any choice of xy d ∈ L xy d completes the weighting. Corollary 2.3. If G is a nice graph, then ch e σ * (G) ≤ 2.

  For example, χ e σ (C 3 ) = 2 and χ e m (C 3 ) = 3, whereas χ e σ (C 4 ) = χ e m (C 4 ) = 2 and χ e σ (C 5 ) = χ e m (C 5 ) = 3. The following proposition follows from two bounds stated in the introduction -χ e m (G) ≤ 4 for every nice graph and χ t Σ (G) ≤ 3 for every graph. Proposition 2.7. If a graph G is nice then χ e σ (G) ≤ 4.

Corollary 2 . 14 .

 214 If G is a (d, g)-graph with d = 4 and g ≥ 5, then χ e σ (G) ≤ 3.

Theorem 3 . 1 .

 31 If G is a nice d-regular graph, then ls e σ (G) ≤ (2e(d + 1)(n -d))1/d-1 .Proof: Fix an arbitrary ordering of E(G). Let L e be a set of size k = (2e(d + 1)(n -d))1/d-1associated with the edge e; choose its weight w(e) randomly from L e with uniform probability. Let c(u) denote the resulting sequence of weights of edges incident to u ∈ V (G).

Theorem 3 . 2 .

 32 e |, |J p |} + 1) , and so the result holds by the Symmetric Local Lemma. A bound for total list weightings is similarly obtained: For any d-regular graph G, d ≥ 2, ls t σ (G) ≤ (2e(d + 1)(n -d)) 1/d .

Theorem 3 . 3 .

 33 If G is a graph with minimum degree δ(G) = δ and maximum degree ∆(G) = ∆, thenls e σ (G) ≤ (2e(∆ + 1)(n -∆)) 1/δ-1 , and ls t σ (G) ≤ (2e(∆ + 1)(n -∆)) 1/δ .

Corollary 3 . 4 .

 34 Let n, k ∈ Z + . If G is a graph on n vertices with minimum degree δ(G) = δ > c log n for large enough c = c(k), then ls e σ (G) ≤ k.Proof: Choose c so that c log n ≥ log k e 2 (n + 1) 2 + 1 +1. Note that the function f (∆) = (∆+1)(n-∆) is maximized when ∆ = 1 2 (n -1), and so(∆ + 1)(n -∆) ≤ 1 4 (n + 1) 2 . Since δ(G) > log k e 2 (n + 1) 2 + 1 + 1, k δ-1 > e 2 (n + 1) 2 + 1 =⇒ k > (2e(∆ + 1)(n -∆)) 1/δ-1 =⇒ k ≥ (2e(∆ + 1)(n -∆)) 1/δ-1 .

Theorem 3 . 5 .

 35 Let M be a loopless multigraph with maximum edge multiplicity µ(G) = µ, minimum degree δ(G) = δ, and maximum degree ∆(G) = ∆. For any positive integer k,(1) if µ < δ -log k (2e(∆ + 1)(n -∆)), then ls e σ (M ) ≤ k.

Acknowledgements

The authors express their gratitude to their respective funding agencies -Carleton University, the Natural Sciences and Engineering Research Council of Canada, and the Ontario Ministry of Research and Innovation. We also thank the referees for their helpful suggestions.


Anne Lacroix
email: a.lacroix@ulg.ac.be

Narad Rampersad
email: narad.rampersad@gmail.com

Automaticity of Primitive Words and Irreducible Polynomials

Keywords: automaticity, primitive word, unbordered word, irreducible polynomial

If L is a language, the automaticity function AL(n) (resp. NL(n)) of L counts the number of states of a smallest deterministic (resp. non-deterministic) finite automaton that accepts a language that agrees with L on all inputs of length at most n. We provide bounds for the automaticity of the language of primitive words and the language of unbordered words over a k-letter alphabet. We also give a bound for the automaticity of the language of base-b representations of the irreducible polynomials over a finite field. This latter result is analogous to a result of Shallit concerning the base-k representations of the set of prime numbers.

Introduction

Automaticity is a measure of how close a non-regular language is to being regular. We can approximate a non-regular language L by considering a regular language L such that the words of length at most n in L are exactly the words of length at most n in L . The automaticity of L is the number of states of a smallest deterministic finite automaton accepting some approximation L . Non-deterministic automaticity can be defined similarly. Automaticity was first introduced by Trakhtenbrot [START_REF] Trakhtenbrot | On an estimate for the weight of a finite tree[END_REF] and later by Karp [START_REF] Karp | Some bounds on the storage requirements of sequential machines and Turing machines[END_REF]. Shallit and Breitbart [START_REF] Shallit | Automaticity I: Properties of a measure of descriptional complexity[END_REF] wrote a survey of the basic results concerning automaticity known at the time.

In the first part of this article we give bounds for the non-deterministic automaticity of the language of primitive words and the language of unbordered words. A word is primitive if it is not a power of a smaller word. A word is unbordered if it has no non-trivial period. The language of primitive words has been well-studied (see the survey by Lischke [START_REF] Lischke | Primitive words and roots of words[END_REF], for example). It is not difficult to show that the language of primitive words is not regular, but it is a long-standing open problem to show that this language is not context-free. It is also not difficult to show that the language of unbordered words is not regular. For a proof that this language is not context-free see [START_REF] Rampersad | Inverse star, borders, and palstars[END_REF].

In the second part we give a bound on the automaticity of the set of irreducible polynomials over a finite field. The set of base-k representations of the prime numbers is not a regular language for any base k. Shallit [START_REF] Shallit | Automaticity IV: Sequences, sets, and diversity[END_REF] gave a lower bound on the automaticity of the set of prime numbers in any base. We consider the same problem in the setting of polynomials over a finite field. Given a fixed non-constant polynomial b, one can also define the base-b representation for such polynomials (see for example [START_REF] Rigo | Syntactical and automatic properties of sets of polynomials over finite fields[END_REF]). Rigo and Waxweiler [START_REF] Rigo | Logical characterization of recognizable sets of polynomials over a finite field[END_REF] proved that the set of base-b representations of the irreducible polynomials is again a non-regular language for any base b. We obtain our bound for the automaticity using arguments similar to those of [START_REF] Shallit | Automaticity IV: Sequences, sets, and diversity[END_REF].

There is an interesting connection between primitive words and irreducible polynomials over a finite field. The number of primitive words of length n over an alphabet of size q is

d|n µ(d)q n/d , ( 1
)
where µ is the Möbius function (see [START_REF] Lothaire | Combinatorics on Words[END_REF]Section 1.3]). Similarly, the number of monic irreducible polynomials of degree n over the finite field with q elements is

1 n d|n µ(d)q n/d .
This is equal to the number of equivalence classes of primitive words of length n under the conjugacy relation x ∼ y if x is a cyclic shift of y. For an explicit bijection between the set of irreducible polynomials and the set of primitive necklaces, see [13, Section 7.6.2].

Definitions

Let L ⊆ Σ * . A language L is an n-th order approximation to L if

L ∩ Σ ≤n = L ∩ Σ ≤n .
We define the automaticity A L (n) of a language L to be the number of states of a smallest DFA accepting some n-th order approximation to L. Similarly, the nondeterministic automaticity N L (n) of a language L is the number of states of a smallest NFA accepting some n-th order approximation to L. Let x, y ∈ Σ * . We say that x and y are n-similar for L if for all z ∈ Σ * with |xz|, |yz| ≤ n, we have xz ∈ L if and only if yz ∈ L. If x and y are not n-similar, then they are n-dissimilar for L.

Theorem 1 ( [START_REF] Kaneps | Minimal nontrivial space complexity of probabilistic one-way Turing machines[END_REF]) Let L ⊆ Σ * . For all n ≥ 0, A L (n) is the maximum possible cardinality of a set of pairwise n-dissimilar words for L.

Example 2 Let L = {0 n 1 n : n ≥ 0}. Then A L (n) ≥ m+1 for n = 2m, 2m+1
, since {ε, 0, 00, . . . , 0 m } is a set of pairwise 2m-dissimilar words for L. To see this, consider 0 j and 0 k for 0 ≤ j < k ≤ n. Then

0 j 1 j ∈ L and 0 k 1 j / ∈ L.
Let U be a finite set of words. We say that U is a set of uniformly n-dissimilar words for L if for each x ∈ U there exists z such that

Automaticity of primitive and unbordered words

Let k ≥ 2 be an integer. A word y is a k-power if y can be written as y = x k for some non-empty word x. If y cannot be so written for any k ≥ 2, then y is primitive.

Bordered words are generalizations of powers. We say a word x is bordered if there exist words u, v, w ∈ Σ + such that x = uv = wu. In this case, the word u is said to be a border for x. Otherwise, x is unbordered.

Let w = w 0 • • • w -1 and let p < . The word w has a period p if w i = w i+p for all 0 ≤ i ≤ -p -1. Note that a word is unbordered if it has no period.

We recall the notation O(•) and Ω(•). Let f and g be functions from N to R. The function f is O(g) if there exist C > 0 and n 0 such that for all n > n 0 we have

f (n) ≤ C • g(n). The function f is Ω(g) if there exist C > 0 and n 0 such that for all n > n 0 we have f (n) ≥ C • g(n).
Theorem 4 Let ε > 0 be a real number. The nondeterministic automaticity of the set Q k of primitive words over the alphabet

Σ k = {0, . . . , k -1} is N Q k (n) ≥ β k k n/2 + O((k + ε) n/4 ),
where β k is a constant that depends only on k.

Proof: For n ≥ 0, we will define a set of uniformly n-dissimilar words as follows. Let

D n = {w ∈ Σ n/2 k : w is unbordered }.
To show that the words in D n are uniformly n-dissimilar, let x, y ∈ D n , x = y. Observe that xx is not primitive, but yx is, for if yx were not primitive, then yx = z for some word z and some ≥ 3. In this case |yx|/ is a period of y, and hence y is bordered, which contradicts the definition of D n .

Guibas and Odlyzko [4, Theorem 7.2] gave the following formula for the size of D n (see also [START_REF] Nielsen | A note on bifix-free sequences[END_REF]): there exists a constant β k such that

|D n | = β k k n/2 + O((k + ε) n/4 ).
By Theorem 3 we have

N Q k (n) ≥ |D n |, which is the desired result. 2
Note that Guibas and Odlyzko gave an explicit formula for the β k , which permits one to calculate β k to any desired degree of accuracy. For example, if k = 2, we have β 2 = 0.26771654 • • • .

Next we give an upper bound on the nondeterministic automaticity of Q k .

Theorem 5 For n ≥ 0,

N Q k (n) ≤ 2k 3/2 (k -1)( √ k -1) k n/2 + n 3 k n/3
Proof: For each n ≥ 0 we construct a deterministic automaton that accepts all words of length at most n in the complement of Q k . The automaton is constructed as follows. First consider the language of square words (2-powers) of length i. We can construct an automaton accepting this language by first constructing the complete k-ary tree with k i/2 leaves so that each path from the root to a leaf is labeled by a different word of length i/2. We then make a copy of this tree, but reflected, so that the arrows are directed away from the leaves towards the root of the tree. The leaves of the first tree are identified with the leaves of the second tree. This construction is illustrated in Figure 1, which shows the automaton accepting all binary squares of length 6. In the figure, dotted lines connect states to be identified, and transitions not shown go to a sink state.

The left tree has

k (i/2)+1 -1 k -1
states, so the automaton for the squares of length i has at most

2 k (i/2)+1 -1 k -1 states.
For each d > 2, to accept d-powers of length i we simply construct a tree with k i/d leaves so that each path from the root to a leaf is labeled by a different d-power of length i. This tree has at most ik i/d states.

To create the automaton accepting all non-primitive words of length i, we can combine all of these automata, sharing edges and transitions whenever possible. The resulting automaton has at most

2 k (i/2)+1 -1 k -1 + d|i d>2 ik i/d ≤ 2k k -1 k i/2 + d|i d>2 ik i/d ≤ 2k k -1 k i/2 + d|i d>2 ik i/3 ≤ 2k k -1 k i/2 + i 2 k i/3
states. We can therefore can construct an automaton accepting all non-primitive words of length at most n using at most

n i=1 2k k -1 k i/2 + i 2 k i/3 ≤ 2k k -1 n i=1 k i/2 + n i=1 i 2 k i/3 ≤ 2k k -1 k (n+1)/2 - √ k √ k -1 + n i=1 i 2 k i/3 ≤ 2k k -1 k (n+1)/2 - √ k √ k -1 + n 3 k n/3 ≤ 2k 3/2 (k -1)( √ k -1) k n/2 + n 3 k n/3
states. Since this automaton is deterministic, the automaton accepting Q k has at most this many states as well. 2

Next we consider the language of unbordered words.

Theorem 6 Let ε > 0. The nondeterministic automaticity of the set UB k of unbordered words over the alphabet

Σ k is N U B k (n) = Ω((k -ε) n/2 ).
Proof: For each ε > 0 there exists j such that the number of words of length m over a k-letter alphabet that avoid 1 j is Ω((k -ε) m ) (see for example the analysis given in the section "Longest runs" starting on p. 308 of [START_REF] Flajolet | Analytic Combinatorics[END_REF]). Fix such a j. For n ≥ 2(j + 2) we define

D n = {0w01 j : |w| = n/2 -(j + 2
) and w does not contain 1 j }.

To show that the words in D n are uniformly n-dissimilar, let x, y ∈ D n , x = y. Since x, y ∈ D n , there exist w 1 and w 2 such that x = 0w 1 01 j and y = 0w 2 01 j .

Clearly xx is bordered; however, xy is not bordered. Suppose to the contrary that xy has a border b. Since b is a non-empty prefix of xy, it must begin with 0; since it is also a suffix, it must end with 1 j . However xy contains only one occurrence of 1 j apart from the occurrence at the end. It follows that b = x, and since b is also a suffix of xy and |x| = |y|, we must also have b = y. Thus x = y, which is a contradiction.

Since

|D n | = Ω((k -ε) n/2-(j+2) ) = Ω((k -ε) n/2
), we have the result by Theorem 3. 2

Irreducible polynomials

In this section we consider the automaticity of the language of representations of irreducible polynomials over a finite field with respect to some base b.

Let F be a field with q elements. Let F[X] be the polynomial ring over F. If f ∈ F[X] we denote its degree by deg f . Let B be an integer and let F[X] <B denote the set of polynomials over F of degree strictly less than B. If b is a fixed non-constant polynomial, then any polynomial f can be written uniquely as

f = i=0 c i b -i , c 0 = 0,
where each c i has degree less than deg b.

We define a function Ψ : F[X] <B → F B by Ψ(f ) := (0, . . . , 0

B-N -1 , F 0 , . . . , F N ) if f = F 0 X N + • • • + F N . The word [f ] b := Ψ(c )Ψ(c -1 ) • • • Ψ(c 0
) over the alphabet F B is the brepresentation of f . By convention, the representation of the zero polynomial is ε. Given a b-representation w ∈ (F B ) * , we denote its value in F[X] by w b . Note that we have chosen to write f starting with the least significant "digit" and ending with the most significant "digit".

A set T ⊆ F[X] is b-recognizable if the language [T ] b = {[f ] b : f ∈ T } ⊆ (F B ) *
is regular. Rigo and Waxweiler [START_REF] Rigo | Logical characterization of recognizable sets of polynomials over a finite field[END_REF] proved that for any base b, the set of irreducible polynomials over F is not b-recognizable. Let T ⊂ F[X] and let b be a non-constant polynomial. The b-automaticity of T is denoted by A b T (n) and is defined as the automaticity

A b L (n) of the language L = {[f ] b : f ∈ T }.
Theorem 7 There exists a constant B such that the set S of monic irreducible polynomials over F has b-automaticity A b S (n) ≥ q Bn /Bn + O(q Bn/2 /Bn).

The main tool for the proof of this theorem is the following result of Hsu [START_REF] Hsu | The distribution of irreducible polynomials in F q [t][END_REF]Corollary 3.4].

Theorem 8 Let a and m be polynomials over F such that (a, m) = 1. Let #S N (a, m) denote the number of monic irreducible polynomials of degree N congruent to a modulo m and let M = deg m. If

q N/2 > (3 + M )q M then #S N (a, m) ≥ 1.
The proof of the following lemma is similar to that of [START_REF] Shallit | Automaticity IV: Sequences, sets, and diversity[END_REF]Lemma 6], which is in turn based on an idea found in [START_REF] Hartmanis | On the recognition of primes by automata[END_REF] and [START_REF] Allen | On a characterization of the nonregular set of primes[END_REF].

Lemma 9 Let d ∈ F[X] such that deg d > 0 and let f, g ∈ F[X] <deg d such that f = g and (d, f ) = (d, g) = 1.
Then there exists a constant C q and a polynomial h such that hd + f is irreducible and hd + g is not irreducible, where deg h ≤ C q deg d. We may thus take C q = 2C(C + 1) to complete the proof. Hence |xz| = n/(1 + C q ) + C q |x| = n/(1 + C q ) + C q (n/(1 + C q )) = n.

We now estimate the size of D n . Let B = deg b/(1+C q ). Note that there are q Bn /Bn+O(q Bn/2 /Bn) monic irreducible polynomials in F [X] of degree Bn. Since deg b is a constant, there are at most a constant number of polynomials f that divide b. Hence |D n | = q Bn /Bn + O(q Bn/2 /Bn).

2

•

  |xz| ≤ n and xz ∈ L; and • for each y ∈ U such that x = y, we have |yz| ≤ n and yz / ∈ L. Theorem 3 ([3]) Let L ⊆ Σ * and let U be a set of uniformly n-dissimilar words for L. Then N L (n) ≥ |U |.

Fig. 1 :

 1 Fig. 1: An automaton accepting binary squares of length 6

Proof:

  By Theorem 8 there exist a constant C and a polynomial h 0 such that r = h 0 d + f is irreducible, where deg h 0 ≤ C deg d. If s = h 0 d + g is reducible, we are done. Otherwise, since (sd + r, sd) = 1, by Theorem 8 again, there exists h 1 such that h 1 (sd) + (sd + r) is irreducible, where deg h 1 ≤ C(deg sd) = C(deg s + deg d). However, h 1 (sd) + (sd + s) is a multiple of s and hence is reducible. Therefore we set h = s(h 1 + 1) + h 0 . Furthermore, we have deg h ≤ max{deg h 1 + deg s, deg h 0 } ≤ max{C(2 deg s + deg d), C deg d} ≤ C(2 deg s + deg d) ≤ C(2(C deg d) + 2(deg d)) ≤ 2C(C + 1)(deg d).

2 Proof of Theorem 7 :

 27 To prove Theorem 7 we will contruct a set D n of n-dissimilar words for [S] b . Let C q be as in Lemma 9. LetD n = {[f ] b : f ∈ S, (f, b) = 1, deg f = (n deg b)/(1 + C q )}.Note that all words in D n have the same length. Consider two elements x, y ∈ D n . Let f = x b , g = y b . By Lemma 9, there exists h such that hb |x| + f is irreducible and hb |x| + g is not, wheredeg h = C q deg b |x| . Let z = [h] b . Then xz ∈ [S]b and yz / ∈ [S] b . Since deg h = C q deg b |x| , we have |z| deg b = C q |x| deg b, and so |z| = C q |x|. Since deg f = (n deg b)/(1+C q ), we have |x| = n/(1+C q ).

Acknowledgments

We thank Michel Rigo for suggesting to us the problem of the automaticity of the irreducible polynomials and for his helpful comments. We also thank Jeffrey Shallit for interesting discussions on the subject of automaticity.