Wojciech Czerwiński

Claire David

Katja Losemann

Wim Martens

Deciding Definability by Deterministic Regular Expressions ⋆

We investigate the complexity of deciding whether a given regular language can be defined with a deterministic regular expression. Our main technical result shows that the problem is PSPACE-complete if the input language is represented as a regular expression or nondeterministic finite automaton. The problem becomes EXPSPACE-complete if the language is represented as a regular expression with counters.

Introduction

Schema information is highly advantageous when managing and exchanging XML data. Primarily, schema information is crucial for automatic error detection in the data itself (which is called validation, see, e.g., [START_REF] Bray | Extensible Markup Language XML 1.0[END_REF][START_REF] Segoufin | Validating streaming XML documents[END_REF][START_REF] Balmin | Incremental validation of XML documents[END_REF][START_REF] Konrad | Validating XML documents in the streaming model with external memory[END_REF]) or in the procedures that transform the data [START_REF] Milo | Typechecking for XML transformers[END_REF][START_REF] Martens | On the complexity of typechecking top-down XML transformations[END_REF][START_REF] Maneth | XML type checking with macro tree transducers[END_REF]. Furthermore, schemas provide information for optimization of XML querying and processing [START_REF] Neven | On the complexity of XPath containment in the presence of disjunction, DTDs, and variables[END_REF][START_REF] Wood | Containment for XPath fragments under DTD constraints[END_REF], they are inevitable when integrating data through schema matching [START_REF] Arenas | Foundations of Data Exchange[END_REF], and they provide users with a high-level overview of the structure of the data. From a software development point of view, schemas are very useful to precisely specify pre-and post-conditions of software routines that process XML data.

In their core, XML schemas specify the structure of well-formed XML documents through a set of constraints which are very similar to extended context-free grammar productions. Such schema are usually abstracted as a set of rules of the form Type → Content,

where Content is a regular expression that defines the allowed content inside the element type specified in the left-hand side. As such, regular expressions are a central component of schema languages for XML. The two most prevalent schema languages for XML data, Document Type Definition (DTD) [START_REF] Bray | Extensible Markup Language XML 1.0[END_REF] and XML Schema Definition (XSD) [START_REF] Fallside | XML Schema Part 0: Primer[END_REF], both developed by the World Wide Web Consortium, do not allow arbitrary regular expressions to define Content. Instead, they require these expressions to be deterministic. We refer to such deterministic regular expressions as DREs. In order to get a good understanding of schema languages for XML, it is thus important to develop a good understanding on DREs. Furthermore, since the concept of determinism in regular expressions is a rather foundational, we believe our results to be relevant in a larger scope as well.

Intuitively, a regular expression is deterministic if, when reading a word from left to right without looking ahead, it is always clear where in the expression the next symbol can be matched. For example, the expression (a + b) * b(a + b) is not deterministic, because if we read a word that starts with b, it is not clear whether this b should be matched in the expression if we do not know what the remainder of the word will be. As such, determinism in regular expressions is very similar to determinism in finite automata: When we consider each alphabet symbol in an expression as a state and consider transitions between positions in the expression that can be matched by successive symbols, then the expression is deterministic if and only if the thus obtained automaton (which is known as the Glushkov automaton of the expression) is deterministic.

Deterministic regular expressions or DREs have therefore been a subject of research since their foundations were laid in a seminal paper by Brüggemann-Klein and Wood [START_REF] Brüggemann-Klein | Deterministic regular languages[END_REF][START_REF] Brüggemann-Klein | One-unambiguous regular languages[END_REF]. The most important contribution of this paper is a characterization of languages definable by DREs in terms of structural properties on the minimal DFA. In particular, this characterization showed that some regular languages cannot be defined with a DRE. One such language is defined by the expression (a + b) * b(a + b). Furthermore, Brüggemann-Klein and Wood showed that it is decidable whether a given regular language is definable by a DRE. Since then, DREs have been studied in the context of language approximations [START_REF] Bex | Simplifying XML Schema: effortless handling of nondeterministic regular expressions[END_REF], learning [START_REF] Bex | Learning deterministic regular expressions for the inference of schemas from XML data[END_REF], descriptional complexity [START_REF] Gelade | Succinctness of the complement and intersection of regular expressions[END_REF][START_REF] Losemann | Descriptional complexity of deterministic regular expressions[END_REF] and static analysis [START_REF] Chen | Inclusion test algorithms for one-unambiguous regular expressions[END_REF][START_REF] Colazzo | Efficient inclusion for a class of XML types with interleaving and counting[END_REF]. Recently, it was shown that testing if a regular expression is deterministic can be done in linear time [START_REF] Groz | Deterministic regular expressions in linear time[END_REF].

Determinism has also been studied for a more general class of regular expressions which allows a counting operator [START_REF] Kilpeläinen | One-unambiguity of regular expressions with numeric occurrence indicators[END_REF][START_REF] Gelade | Regular expressions with counting: Weak versus strong determinism[END_REF][START_REF] Hovland | Regular expressions with numerical constraints and automata with counters[END_REF]. This operator allows to write the expression a 10,100 defining the language that contains strings of length 10 to 100 and labeled with only a's. The motivation for the counting operator again comes from schema languages, because the operator can be used to define expressions in XML Schema. Determinism for expressions with counters seems to pose more challenges than without the counting operator. For example, already testing whether an expression with counters is deterministic is non-trivial [START_REF] Kilpeläinen | Checking determinism of XML Schema content models in optimal time[END_REF].

In this paper we study the following problem:

Given a regular expression, can it be determinized?

This problem seems to be very foundational and has first been studied around 20 years ago [START_REF] Brüggemann-Klein | Deterministic regular languages[END_REF] but the precise complexity was still open, despite the rich body of research discussed above. The best known upper bound is from Brüggeman-Klein and Wood, who showed that the problem is in EXPTIME (by exhibiting an algorithm that works in polynomial time on the minimal DFA [START_REF] Brüggemann-Klein | One-unambiguous regular languages[END_REF]) and the best known lower bound is PSPACE-hardness [START_REF] Bex | Simplifying XML Schema: effortless handling of nondeterministic regular expressions[END_REF]. The main result of this paper settles this question and proves that this problem is PSPACE-complete. Our proof is rather technical and provides deeper insights in the decision algorithm of Brüggemann-Klein and Wood. A central insight, which is a cornerstone of our proof, is that the recursion depth of the algorithm is only polynomial in the size of the smallest NFA for the given regular language. Since regular expressions with counters are important in the context of W3C XML Schema, we also study the complexity of deciding if a given expressions with counters can be written as a DRE. This problem turns out to be EXPSPACE-complete. We complement these completeness results by proving that it is NLOGSPACE-hard to decide if a given DFA can be written as a DRE. At the moment, it is not clear to us whether this lower bound can be improved. The problem is known to be in polynomial time by [START_REF] Brüggemann-Klein | One-unambiguous regular languages[END_REF].

Organisation: We give the basic definitions in Section 2. In Section 3 we present the algorithm of Brüggeman-Klein and Wood and prove preliminary results. Complexity results are presented in Section 4. Due to space limits, some proofs are not presented or only sketched.

Definitions

For a finite set S, we denote its cardinality by |S|. By Σ we always denote an alphabet, i.e., a finite set of symbols. A (Σ-)word w over alphabet Σ is a finite sequence of symbols a 1 • • • a n , where a i ∈ Σ for each i = 1, . . . , n. The set of all Σ-words is denoted by Σ * . The length of a word w = a 1 • • • a n is n and is denoted by |w|. The empty word is denoted by ε. A language is a set of words.

A (nondeterministic) finite automaton (or NFA) N is a tuple (Q, Σ, δ, q 0 , F ), where Q is a finite set of states, δ : Q × Σ → 2 Q is the transition function, q 0 is the initial state, and F ⊆ Q is the set of accepting states. We sometimes denote that q 2 ∈ δ(q 1 , a) as q 1 a -→ q 2 ∈ δ to emphasize that, when N is in state q 1 , it can go to state q 2 when reading an a. A run of N on word w = a 1 • • • a n is a sequence q 0 • • • q n where, for each i = 1, . . . , n, we have q i-1 ai -→ q i ∈ δ. Word w is accepted by N if there is such a run which is accepting, i.e., if q n ∈ F . The language of N , also denoted L(N ), is the set of words accepted by N . By δ * we denote the extension of δ to words, i.e., δ * (q, w) is the set of states which can be reached from q by reading w. The size |N | of an NFA is the total number of transitions, i.e., q,a |δ(q, a)|. An NFA is deterministic, or a DFA, when every δ(q, a) has at most one element. Throughout the paper, we will use the notation P N for the power set automaton of N and [N ] for the minimal DFA for L(N ). It is well-known that [N ] is unique for N and that it can be obtained by merging states of P N [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF]. In this paper we assume that all states of automata are useful unless mentioned otherwise, that is, every state can appear in some accepting run. This implies that every state can be reached from the initial state and that, from each state in an automaton, an accepting state can be reached. This also implies that we use minimal DFAs without sink state and that P N by default only contains the useful subsets of states of N . We sometimes abuse notation and also denote by ∅ the minimal DFA with no states.

Furthermore, we will often see an NFA as a graph, which is obtained by considering its states as nodes and its transitions as (labeled) directed edges. Then, we also refer to a connected sequence of transitions in N as a path.

The regular expressions (RE) over Σ are defined as follows: ε and every Σsymbol is a regular expression; and whenever r and s are regular expressions then so are (r •s), (r +s), and (s) * . In addition, we allow ∅ as a regular expression, but we do not allow ∅ to occur in any other regular expression. For readability, we usually omit concatenation operators and parentheses in examples. The language defined by an RE r, denoted by L(r), is defined as usual. Whenever we say that expressions or automata are equivalent, we mean that they define the same language. The size |r| of r is defined to be the total number of occurrences of alphabet symbols, epsilons, and operators, i.e., the number of nodes in its parse tree.

Variations of Regular Expressions

The regular expressions with counters (RE(#)) extend the REs with a counting operator. That is, each RE-expression is an RE(#)-expression. Furthermore, when r and s are RE(#)-expressions then so are (r • s), (r + s), and r k,ℓ for k ∈ N and ℓ ∈ N + ∪ {∞} with k ≤ ℓ. Here,

N + denotes N \ {0}. For a lan- guage L, define L k,ℓ as ℓ i=k L i . Then, L(r k,ℓ ) = ℓ i=k L(r) i . Notice that r * is equivalent to r 0,∞ .
The size of an expression in RE(#) is the number of nodes in its parse tree, plus the sizes of the counters, where a counter k ∈ N has size log k.

Deterministic regular expressions (DREs) put a restriction on the class of REs. Let r stand for the RE obtained from r by replacing, for every i and a, the i-th occurrence of alphabet symbol a in r (counting from left to right) by a i . For example, for r = b * a(b * a) * we have r = b * 1 a 1 (b * 2 a 2 ) * . A regular expression r is deterministic (or one-unambiguous [START_REF] Brüggemann-Klein | One-unambiguous regular languages[END_REF] or a DRE ) if there are no words wa i v and wa j v ′ in L(r) such that i = j. The expression (a + b) * a is not deterministic since both strings a 2 and a 1 a 2 are in L((a 1 + b 1 ) * a 2 ). The equivalent expression b * a(b * a) * is deterministic. Brüggemann-Klein and Wood showed that not every regular expression is equivalent to a deterministic one [START_REF] Brüggemann-Klein | One-unambiguous regular languages[END_REF]. We call a regular language DRE-definable if there exists a DRE that defines it. The canonical example for a language that is not DRE-definable is (a + b) * b(a + b) [START_REF] Brüggemann-Klein | One-unambiguous regular languages[END_REF]. We therefore have that the set of DREs forms a strict subset of the REs, which in turn are a strict subset of the RE(#)s.

Problems of Interest

In this paper, we investigate variants of the following problem. DRE-Definability: Given a regular language L, is L DRE-definable?

We consider this problem for various representations of regular languages: regular expressions, regular expressions with counters, NFAs, and DFAs. Whenever we consider such a variation, we put the respective representation between braces. For example, DRE-Definability(RE) is the problem: Given a regular expression r, is L(r) DRE-definable? DRE-Definability was first studied by Brüggemann-Klein and Wood who showed that the problem can be solved in polynomial time in the size of the minimal DFA of a language [START_REF] Brüggemann-Klein | One-unambiguous regular languages[END_REF]. Their algorithm (henceforth referred to as the Bkw-Algorithm) is not at all trivial and gives good insight in DRE-definable regular languages. We recall the Bkw-Algorithm together with some definitions and known results and then we prove deeper properties of the Bkw-Algorithm which will be the basis of further results in the paper.

Orbits and gates: For a state q in an NFA N , the orbit of q, denoted O(q), is the maximal strongly connected component of N that contains q. We call q a gate of O(q) if q is accepting or q has an outgoing transition that leaves O(q). If an orbit consists only of one state q and q has no self-loops, we say that it is a trivial orbit. We say that a transition q 1 a -→ q 2 is an inter-orbit transition if q 1 and q 2 belong to different orbits. The orbit automaton of state q is the sub-automaton of N consisting of O(q) in which the initial state is q and the accepting states are the gates of O(q). We denote the orbit automaton of q by N q . The orbit language of q is L(N q ). The orbit languages of N are the orbit languages of states of N .

Orbit property: An NFA N has the orbit property if, for every pair of gates q 1 , q 2 in the same orbit in N , the following properties hold:

1. q 1 is accepting if and only if q 2 is accepting; and, 2. for all states q outside the orbit of q 1 and q 2 , there is a transition q 1 a -→ q if and only if there is a transition q 2 a -→ q.

Consistent symbols: A symbol a ∈ Σ is N -consistent if there is a state f (a), such that every accepting state q of N has a transition q a -→ f (a). We refer to the corresponding transitions as consistent transitions of N . A set S ⊆ Σ is N -consistent if every symbol in S is N -consistent. Whenever we consider N -consistent sets S in the remainder of the paper we assume that they are maximal, i.e., there does not exist an a ∈ Σ that is not in S and is N -consistent. Henceforth, we will therefore refer to the N -consistent set. For the set S of N -consistent symbols, the S-cut of N , denoted N S , is obtained by removing all consistent transitions from N . Using these notions, Brüggemann-Klein and Wood give the following characterization of the class of DRE-definable languages.

Theorem 1 (Brüggemann-Klein and Wood [START_REF] Brüggemann-Klein | One-unambiguous regular languages[END_REF]). Let D be a minimal DFA and S be the set of D-consistent symbols. Then the following are equivalent: choose a state q in O if not Bkw((DS)q) then return false 12: return true They also show this result about the orbit property and the orbit languages.

Lemma 2 (Brüggemann-Klein and Wood [START_REF] Brüggemann-Klein | One-unambiguous regular languages[END_REF]). Let D be a minimal DFA and S be the set of D-consistent symbols.

1. If D S has the orbit property, then (D S ) q is minimal for each state q in D. 2. If p and q are states in the same orbit of D S , then L((D S ) p ) is DRE-definable if and only if L((D S ) q ) is DRE-definable.

Point 1 of the above lemma is immediate from combining Lemmas 5.9 and 5.10 from [START_REF] Brüggemann-Klein | One-unambiguous regular languages[END_REF]. Point 2 is immediate from the fact that DRE-definable regular languages are closed under derivatives [START_REF] Brüggemann-Klein | One-unambiguous regular languages[END_REF]. Notice that, in general, D S does not have to be a minimal DFA. In particular, it can have states that are not reachable from the initial state. These results lead to a recursive test that decides whether the language of a minimal DFA is DRE-definable. We present this test in Algorithm 1. Notice that Lemma 2 ensures that we never have to minimize the DFA that we give to the recursive call in line 11 of the algorithm.

In the remainder of this article, D always denotes a minimal DFA. In the following we investigate the recursion depth of Algorithm 1. Therefore, we examine how, for a state q of D, the orbit of q evolves during the recursion. In one iteration of Algorithm 1 we always delete two kinds of transitions, if they are present: the consistent transitions (which we delete to obtain D S from D) and the inter-orbit transitions in D S (which we delete to obtain (D S ) q ). Level automata: For a state q of a minimal DFA D and k ∈ N we inductively define the level k automaton of D for the state q, denoted lev k (D, q), as follows:

lev 0 (D, q) = D.

-Let S be the maximal set of consistent symbols in D. Then

lev 1 (D, q) =          (D S ) q if D
has more than one orbit and D S has the orbit property; (D S ) q if S = ∅ and D S has the orbit property; ∅ otherwise. -Let k > 1 and S k-1 be the maximal set of consistent symbols in B := lev k-1 (D, q). Then

lev k (D, q) = (B S k-1 ) q if S k-1 = ∅ and B S k-1 fulfills the orbit property ∅ otherwise.
The above definition actually precisely follows the construction in Algorithm 1 if state q is chosen every time in line 10. The definition makes clear that the top level recursion of the Bkw-Algorithm (in which we construct lev 1 (D, q)) is slightly different from the others: the input DFA D of the top level can have multiple orbits, whereas this is not the case for deeper recursive levels. According to Lemma 2, lev k (D, q) is always minimal.

Example 3. Figure 1 provides an example to illustrate the notion of level automata. Consider the minimal DFA D from Figure 1(a) and its state q 0 . By definition, lev 0 (D, q 0 ) is the automaton D itself. In order to build lev 1 (D, q 0 ) (see Figure 1(b)), observe that D has two orbits and its set of consistent symbols S is empty since no transitions leave state q 5 . Furthermore, D S , which equals D, fulfills the orbit property since all transitions that leave O(q 0 ) go to state q 5 . As such, lev 1 (D, q 0 ) equals (D ∅ ) q0 , the orbit automaton of q 0 in D. We now explain how to obtain lev 2 (D, q 0 ) (see Figure 1(d)). First notice that S 1 = {a} is the maximal set of consistent symbols in lev 1 (D, q 0 ). Furthermore, the S 1 -cut of lev 1 (D, q 0 ) (illustrated in Figure 1(c) without unreachable states) fulfills the orbit property. The automaton lev 2 (D, q 0 ) is the orbit automaton of q 0 in the S 1 -cut of lev 1 (D, q 0 ) (that is, lev 2 (D, q 0 ) = (lev 1 (D, q 0 ) S1 ) q0 ). Finally, observe that lev 2 (D, q 0 ) has only one orbit and no consistent symbols which implies that lev 3 (D, q 0 ) = ∅. Also, in accordance with the Bkw-Algorithm, this means that L(D) is not DRE-definable.

The following lemma summarizes the link between DRE-definability and level automata.

Lemma 4. Let D be a minimal DFA. Then the following are equivalent:

1. L(D) is DRE-definable; 2.
for every state q of D and k ∈ N, L(lev k (D, q)) is DRE-definable; 3. for every state q of D and k ∈ N, L(lev k (D, q)) is DRE-definable and lev k (D, q) S k has the orbit-property.

The Recursion Depth of BKW

First we observe that, once a state becomes a gate in the Bkw-Algorithm, its outgoing transitions will disappear in deeper recursion levels.

Lemma 5. Let D be a minimal DFA and q be a gate in lev k (D, q) for some k > 0. Then either lev k+1 (D, q) = ∅ or q has strictly less outgoing transitions in lev k+1 (D, q). In the latter case, q is also a gate in lev k+1 (D, q).

From Lemma 5, we can infer how long it takes for a state p to become a gate. Lemma 6. Let D be a minimal DFA and p be a state of lev k (D, p) for some k ∈ N. Let ℓ be the length of the shortest path from p to a gate in lev k (D, p).

Then either lev k+|Σ|•ℓ+1 (D, p) = ∅ or p is a gate in lev k+|Σ|•ℓ+1 (D, p).

Next, we want to combine Lemma 6 with an observation about NFAs versus their minimal DFAs, namely that paths to accepting states are short.

Lemma 7. Let N be an NFA with size n. Then for every state of [N ] there is a path leading to some accepting state of length at most n -1.

Combining Lemma 6 and 7 tells us how long states can be present in the recursion of the Bkw-Algorithm, compared to the size of an NFA for the language.

Lemma 8. Let N be an NFA with size n. Then it holds that lev n

•|Σ|+2 ([N ], p) = ∅ for every state p of [N ].
Summarized, we know that the recursion depth of the Bkw-Algorithm is polynomial in the size of the minimal NFA for a language.

Theorem 9. Let N be an NFA with size n. The recursion depth of Algorithm 1 on

[N ] is at most n • |Σ| + 2.

Consistency Violations

In the following, we analyze the possible causes of failure for the Bkw-Algorithm.

We identify three properties such that the Bkw-Algorithm fails if and only if one of them holds for some orbit automaton at some level k. This will be a tool for our PSPACE algorithm that will search for one of these violations.

From the Bkw-Algorithm, we can immediately see that there are two situations in which it can reject: (in line 6) at some point in the recursion, the automaton consists only of one orbit which has no consistent symbols or (in line 8) at some point in the recursion, the S-cut of the automaton does not have the orbit property. The latter means that there exist two gates of the same orbit in the S-cut, such that either they do not have the same transitions to the outside or one of them is accepting while the other one is not. We now formalize these different types of violations and we then prove that the Bkw-Algorithm fails if and only if one of these violations is found at some point in the recursion. Let D be a minimal DFA and S be its set of consistent symbols. Then D has an Out-Consistency Violation, if there exist gates q 1 and q 2 in the same orbit O of D S and there exists a state q outside O such that there is a transition q 1 a -→ q and no transition q 2 a -→ q; -an Acceptance Consistency Violation, if there exist gates q 1 and q 2 in the same orbit of D S such that q 1 is accepting and q 2 is not; and an Orbit Consistency Violation, if there exists an accepting state q 1 such that, for every symbol a, there exists another accepting state q 2 in O(q 1 ) in D, such that for every state q, at most one of the transitions q 1 a -→ q and q 2 a -→ q exists. 3Notice that the first two violations focus on D S and the last one on D, as in the Bkw-Algorithm. In summary, we will also say that a DFA D has a violation if and only if it has at least one of the above violations. We show that these violations are a valid characterization of DRE-definable languages.

Theorem 10. Let D be a minimal DFA. Then it holds that L(D) is not DREdefinable if and only if there exist a state q of D and k ∈ N such that lev k (D, q) has a violation.

The Definability Problem

We are now ready to prove results about the complexity of DRE-Definability for different formalisms. We first show that the problem is PSPACE-complete for NFAs and REs. Then we look at RE(#)s which are natural extensions in the context of W3C XML Schema. In that setting, the problem becomes EXPSPACEcomplete. Finally, we look at the class of DFAs.

Definability for REs and NFAs

Our PSPACE algorithm for DRE-definability for REs and NFAs exploits Theorem 10 in the following way. Given an NFA N , we search for a level k and a state p of [N ] such that lev k ([N ], p) has a violation. As PSPACE is closed under complement, the result follows. Notice that, in general [N ] can be exponentially larger than N and therefore we cannot simply compute [N ] in space polynomial in |N |. To overcome this difficulty, we use the following two ideas:

1. Use the fact that the maximal recursion depth of Algorithm 1 on [N ] is polynomial in the size of the NFA N (Theorem 9); 2. Adapt Algorithm 1 using Theorem 10 and apply it on the minimal DFA by only partially constructing it on-the-fly from the NFA.

In the following we explain how we can detect if there occurs a violation in the minimal DFA for some NFA on the fly, i.e., without constructing the DFA explicitly. To this end, we fix the following notations for the remainder of the section. By N = (Q N , Σ, δ N , q 0 N , F N ) we always denote an NFA. So, in particular, we always denote by Q N the state set of N . For a set of states q ⊆ Q N , we denote by [q] the corresponding state in the minimal DFA [N ]. More formally, [q] is the set of words {w | ∃t ∈ q s.t. δ * N (t, w) ∩ F N = ∅}, i.e., the Myhill-Nerode class of q. Also, whenever we talk about lev k ([N ], [q]) S k , the set S k is the set of consistent symbols in lev k ([N ], [q]). The key result (Lemma 17) is to show that we can detect if a violation occurs in a level k for [N ] in space polynomial in k and |N |. Here are the precise problems we consider. For each of them the input is an NFA N and k ∈ N:

Out-Cons-Violation: Given N and k, is there a q ⊆ Q N such that lev k ([N ], [q]) S k has an out-consistency violation? Acc-Cons-Violation:

Given N and k, is there a q ⊆ Q N such that lev k ([N ], [q]) S k has an acceptance consistency violation? Orbit-Cons-Violation: Given N and k, is there a q ⊆ Q N such that lev k ([N ], [q]) has an orbit consistency violation?

We first study the complexity of the following subproblems which will be used in the proof of Lemma 17. The input is always a subset of an NFA N , sets p, q ⊆ Q N , a ∈ Σ, k ∈ N that is relevant to the problem.

Edge:

Given

(N, p, q, a, k), is [p] a -→ [q] a transition in lev k ([N ], [p])? Reachability: Given (N, p, q, k), is [q] reachable from [p] in lev k ([N ], [p])? SameOrbit:
Given (N, p, q, k), are [p] and [q] in the same orbit of lev k ([N ], [p])? InterOrbit:

Given (N, p, k), is there an inter-orbit transition [p] a -→ [q] for some label a and q in lev k (

[N ], [p])? Acceptance: Given (N, p, k), is [p] accepting in lev k ([N ], [p])? IsGate: Given (N, p, k), is [p] a gate in lev k ([N ], [p])?
Notice that SameOrbit and InterOrbit are only non-trivial if k = 0. Furthermore, for some of the above problems X we consider a variation called X-Cut in which, with the same input, we want to decide if the problem X is true for automaton lev k (

[N ], [p]) S k (instead of lev k ([N ], [p])).
We will heavily use the following result:

Theorem 11 (Corollary to Savitch's Theorem). Let f (n) ≥ log n be a non-decreasing polynomial function. Then NSPACE(f

(n)) ⊆ SPACE(f 2 (n)).
Our proof is a careful mutual induction on the above defined problems. First we show that Edge, Edge-Cut, and Acceptance can be computed in polynomial space on level 0 and then we prove a set of implications of the sort if we can solve X on level k, then we can solve Y on level k (or level k + 1). All the lemmas have to be carefully put together in the right order. In the following, whenever we say that we solve a problem for N at level k, we mean that we solve it for the NFA N and arbitrary sets of states p, q ⊆ Q N , a ∈ Σ, and k. The basis of our entire mutual induction is being able to test if a certain transition is present in the minimal DFA equivalent to N , if it is present in its S-cut, or if some state is accepting. Proof. We first show how to check, for a given set p ⊆ Q N , whether [p] is a state in [N ], i.e., whether it is useful. As N only has useful states, there exists a path from [p] to some accepting state in [N ]. Thus it is enough to check whether there is a path from [{q 0

N }] to [p]. This clearly can be done by a nondeterministic algorithm working in space O(|N |). This algorithm would guess a word symbol by symbol, simulate P N on the fly, starting from {q 0 N } and test at each step whether the reached state q is equivalent to p, i.e., if [p] = [q] (proof of Lemma 12). Thus, by Theorem 11, it can also be done by a deterministic algorithm working in space O(|N | 2 ).

We now turn our attention to Edge. Let (N, p, q, a, 0) be the input for Edge. We omit the proof how to solve Acceptance and Edge-Cut.

We must decide if [p]

1 .Algorithm 1 2 :

 112 L(D) is DRE-definable; 2. D has the orbit property and all orbit languages of D are DRE-definable; 3. D S has the orbit property and all orbit languages of D S are DRE-definable. Furthermore, if D consists of a single, nontrivial orbit and L(D) is DRE-definable, then there is at least one D-consistent symbol. The Bkw-Algorithm [7]. Algorithm Bkw Input: Minimal DFA D = (Q, Σ, δ, q0, F ) Output: true if L(D) is DRE-definable, else false 4: S ← the maximal set of D-consistent symbols if D has only one trivial orbit then return true 6: if D has precisely one orbit and S = ∅ then return false compute the orbits of DS 8: if DS does not have the orbit property then return false for each orbit O in DS do 10:

  The automaton D, i.e., lev0(D, q0), S = ∅. lev2(D, q0), S2 = ∅.

Fig. 1 .

 1 Fig. 1. An example of level automata for a minimal DFA D.

Lemma 12 .

 12 Given N and p, q ⊆ Q N , we can test whether[p] = [q] in space O(|N | 2 ).Proof (Sketch). A non-deterministic Turing Machine can test in non-deterministic space O(|N |) whether [p] = [q]. The lemma then follows from Theorem 11 and the fact that deterministic complexity classes are closed under complement.

Lemma 13 .

 13 Edge, Acceptance and Edge-Cut for N at level 0 can be solved in space O(|N | 2 ).

a-→

  [q] is a transition in[N ]. Since[N ] does not have useless states, this means that we should test two things:both [p] and [q] are states in [N ]; -[δ P N (p, a)] = [q], where P N is the power set automaton of N . The former can be solved in O(|N | 2 ), as we mentioned before. It remains to prove the latter. Given p and a, we can easily compute δ P N (p, a) in space O(|N |). According to Lemma 12, we can then decide if [δ P N (p, a)] = [q] in space O(|N | 2 ).

Notice that δ(q1, a) may be empty if D only has useful states.

Acknowledgement. We thank Wouter Gelade for bringing this problem to our attention.

⋆ This work was supported by grant number MA 4938/2-1 of the Deutsche Forschungsgemeinschaft (Emmy Noether Nachwuchsgruppe).

When we can solve Edge or Edge-Cut at a certain level, we can use it to make more complex tests. The next lemma allows us to do a single induction step that allows us to compute the structure of an automaton at level k + 1 if we can compute the automaton at level k. Lemma

The following lemma shows that we can compute properties of the level k automaton if we can decide some properties for all smaller levels. For technical reasons, we need the assumption that all lower level automata lev i ([N ], [p]) have no violation. This is because, otherwise, the level k automaton would be empty. The proof is basically a careful induction that puts together the previous lemmas. Lemma 16 states that we can decide on-the-fly which transitions are present and which states are accepting in level k automata (if no violations occur in more shallow levels). Since these properties give the entire structure of the level k automata, we can now also test for violations on level k. Proof. Let the input for Out-Cons-Violation be N and k. Then, an outconsistency violation occurs at level k of N if and only if there exist p, q ⊆ Q N such that all of the following hold:

does not.

By the lemma statement we know that all automata lev i ([N ], [p]) for 0 ≤ i ≤ k -1 have no violation. According to Lemma 16 we can solve IsGate-Cut and Same-Orbit-Cut for N at level k in space O((k + 1)|N | 2 ). We solve the last point by enumerating all a ∈ Σ and states q ′ ⊆ Q N and testing whether

Again by Lemma 16 Edge-Cut and SameOrbit-Cut for N at level k may be done in space O((k + 1)|N | 2 ). This concludes the proof for Out-Cons-Violation.

The proofs for Acc-Cons-Violation and Orbit-Cons-Violation are similar.

We now have all the elements to prove our main result. Proof. DRE-Definability(RE) is known to be PSPACE-hard [START_REF] Bex | Simplifying XML Schema: effortless handling of nondeterministic regular expressions[END_REF]. Since an RE can be translated in polynomial time into an equivalent NFA, the lower bound also holds for NFAs.

Furthermore, the upper bound for REs follows from the upper bound for NFAs. We therefore show that DRE-Definability for an NFA N is in space O(|N | 4 ), which proves the theorem. We assume w.l.o.g. that |Σ| ≤ |N |. According to Theorem 10, a language L(N ) is not DRE-definable if and only if one of Out-Cons-Violation, Acc-Cons-Violation and Orbit-Cons-Violation occurs at some level k for N . Due to Theorem 9 we need to check this only for levels up to |N | 2 + 2, since the recursion depth of Algorithm 1 is never bigger than this.

We test whether there exists a violation at some level k for N , starting from level 0 and moving into higher and higher levels, up to level |N | 2 +2. For every single level k the test can be done in space O((k + 1)|N | 2 ), according to Lemma 17. Note that during the application of the above lemma we know that the smaller levels do not contain any violation, since it was checked before, thus the assumptions in the lemma statements are fulfilled. Therefore the space needed for solving DRE-Definability(NFA) for N is bounded by

Definability for RE(#)s

Next we show that testing DRE-Definability is EXPSPACE-complete when the input is given as a regular expression with counters. The upper bound is immediate from Theorem 18 and the fact that we can translate an RE(#) into an RE of exponential size by unfolding the counters.

For the lower bound, we reduce from the exponential corridor tiling problem, which is defined as follows. An exponential tiling instance is a tuple I = (T, H, V, x ⊥ , x ⊤ , n) where T is a finite set of tiles, H, V ⊆ T × T are the horizontal and vertical constraints, x ⊥ , x ⊤ ∈ T , and n is a natural number in unary notation. A correct exponential corridor tiling for I is a mapping λ : {1, . . . , m} × {1, . . . , 2 n } → T for some m ∈ N, such that every of the following constraints is satisfied:

the first tile of the first row is x ⊥ : λ(1, 1) = x ⊥ ; -the first tile of the m-th row is x ⊤ : λ(m, 1) = x ⊤ ; -all vertical constraints are satisfied: ∀i < m, ∀j ≤ 2 n , (λ(i, j), λ(i+1, j)) ∈ V ;

and, -all horizontal constraints are satisfied: ∀i ≤ m,∀j < 2 n ,(λ(i, j), λ(i, j+1)) ∈ H.

Then, the EXP-Tiling problem asks, given an exponential tiling instance, whether there exists a correct exponential corridor tiling. The latter problem is known to be EXPSPACE-complete [START_REF] Van Emde | The convenience of tilings[END_REF].

The full proof of the lower bound combines elements from the proof that DRE-definability for REs is PSPACE-complete [START_REF] Bex | Simplifying XML Schema: effortless handling of nondeterministic regular expressions[END_REF] and that language universality for RE(#)s is EXPSPACE-complete [START_REF] Gelade | Optimizing schema languages for XML: Numerical constraints and interleaving[END_REF].

Theorem 19. Given a regular expression with counters r, the problem of deciding whether L(r) is DRE-definable is EXPSPACE-complete.

Definability for DFAs

As explained before, the DRE-definability problem is in polynomial time if the input is a minimal DFA [START_REF] Brüggemann-Klein | One-unambiguous regular languages[END_REF]. As a final, minor result, we give an NLOGSPACE lower bound in this case.

Theorem 20. DRE-Definability(minDFA) is NLOGSPACE-hard.

Proof (sketch). The reduction for the lower bound is from the reachability problem in directed acyclic graphs. This problem asks, given a DAG G = (V, E), a source node s, and a target node t, whether t is reachable from s by a directed path. The DAG reachability problem is well-known to be NLOGSPACEcomplete [START_REF] Jones | Space-bounded reducibility among combinatorial problems[END_REF].

In this proof, we will use the fact that finite languages are always DREdefinable. (This can be checked through the Bkw-Algorithm which discovers immediately that all orbits are trivial.) For the reduction, let G = (V, E), and nodes s, t ∈ V be an instance of DAG reachability. We construct a minimal DFA D such that L(D) is DRE-definable if and only if vertex t is reachable from vertex s in graph G.

We build D = (Q, Σ, δ, q 0 , {q f }) from G as follows. The set Q of states is the disjoint union of the vertices V of G, plus two distinguished states q 0 (which is D's initial state) and q f (which is D's only accepting state). The alphabet Σ is defined as (V ⊎ {q 0 , q f }) 2 . The transitions of D are defined as follows. Let V = {v 1 , . . . , v n } be the vertices of G.

-For each directed edge (v i , v j ) ∈ E, the automaton D has the transition δ(v i , (v i , v j )) = v j ; -for each vertex v i , the automaton D has the transitions δ(q 0 , (q 0 , v i )) = v i and δ(v i , (v i , q f )) = q f ; and δ(t, (t, s)) = s is a transition of the automaton D.

As such, every transition has its unique label. This concludes the reduction. The reduction can be conducted in logarithmic space.

Conclusions

We have pinned down the exact complexity of testing whether a regular expression can be determinized and considered additional variants of this problem. Our proof provides additional insights on such DRE-definable languages and on the decision algorithm of Brüggemann-Klein and Wood. An important open question is about the possible blow-up in the determinization process: Given a regular expression, what is the worst-case (unavoidable) blow-up when converting it to an equivalent deterministic one? At the moment, we know that an exponential blow-up cannot be avoided [START_REF] Losemann | Descriptional complexity of deterministic regular expressions[END_REF] but the best known upper bound is double exponential. While our proofs seem to give some insight in how to improve this upper bound, testing if a language is DRE-definable and actually constructing a minimal equivalent DRE are quite different matters. It is not yet clear to us how our techniques can be leveraged to obtain better upper bounds for this question.