Thomas Colcombet

Clemens Ley

Gabriele Puppis

On the use of guards for logics with data

The notion of orbit finite data monoid was recently introduced by Bojańczyk as an algebraic object for defining recognizable languages of data words. Following Büchi's approach, we introduce the new logic 'rigidly guarded MSO' and show that the data languages definable in this logic are exactly those recognizable by orbit finite data monoids. We also establish, following this time the approach of Schützenberger, McNaughton and Papert, that the first-order variant of this logic defines exactly the languages recognizable by aperiodic orbit finite data monoids. Finally, we give a variant of the logic that captures the larger class of languages recognized by non-deterministic finite memory automata.

Introduction

Data languages are languages over an infinite alphabet -the letters of which are called data values -which are closed under permutation of the data values. This invariance under permutation makes any property concerning the data values, other than equality, irrelevant. Some examples of data languages are:

The sets of words containing exactly k distinct data values. The sets of words where the first and last data values are equal. The sets of words with no consecutive occurrences of the same data value. The sets of words where each data value occurs at most once. (⋆) The intention behind data values in data words (or data trees, . . . ) is to model, e.g. the id's in a database, or the process or users numbers in the log of a system. Those numbers are used as identifiers, and we are interested only in comparing them by equality. The invariance under permutation of data languages captures this intention. Data words can also be defined to have both a data value and a letter from a finite alphabet at each position. This is more natural in practice, and does not make any difference in the results to follow.

The paper aims at understanding better how the classical theory of regular languages can be extended to data languages. The classical theory associates regular languages to finite state automata or, equivalently, to finite monoids. For instance, important properties of regular languages can be detected by exploiting equivalences with properties of the monoid -see, e.g. Straubing's book [START_REF] Straubing | Finite Automata, Formal Logic, and Circuit Complexity[END_REF] or Pin's survey [START_REF] Pin | Mathematical foundations of automata theory[END_REF] for an overview of the approach.

Recently, Bojańczyk introduced the notion of data monoids [START_REF] Bojańczyk | Data monoids[END_REF] as a framework for algebraic characterizations of data languages. Bojańczyk focused on the languages of data words recognizable by orbit finite data monoids, an analog of finite monoids for data languages. All the above examples but ⋆ are recognizable with this definition. Our main objective is to understand better the expressive power of the orbit finite data monoid model by comparing it with automatonbased models and logical formalisms for data words.

In terms of logic, there is a natural way to define logics for data words. It is sufficient for this to use a predicate x ∼ y meaning that the data values at positions x and y are equal. In particular, one may think that the monadic (second-order) logic with this new predicate is a good candidate to equivalently specify recognizable languages, i.e., would play the role of monadic logic in the standard theory of regular languages. However, this is not the case, as monadic logic happens to be much too expressive. One inclusion indeed holds: every language of data words recognized by an orbit finite monoid is definable in monadic logic. However, the converse does not hold, as witnessed by the formula ∀ x, y. x ≠ y → x ≁ y, (⋆⋆) which defines the above (non-recognizable) language ⋆. More generally, it has been shown that monadic logic (indeed, even first-order logic with data equality) has an undecidable satisfiability problem and it can express properties not implementable by automaton models, such as finite memory automata (FMA, described below) [START_REF] Neven | Finite state machines for strings over infinite alphabets[END_REF]. We naturally aim at answering the following question:

Is there a natural variant of monadic logic which defines precisely the data languages recognizable by orbit finite data monoids?

We answer this question positively, introducing rigidly guarded MSO (abbreviating monadic second-order logic with rigidly guarded data equality tests). This logic allows testing equality of two data values only when the two positions are related in an injective way (we say rigid). That is, data equality tests are allowed only in formulas of the form ϕ(x, y) ∧ x ∼ y, where ϕ is rigid, i.e., defines a partial injection. For instance, it is easy to check whether there are two consecutive positions sharing the same data value, e.g., by the formula ∃ x, y. (x = y + 1) ∧ x ∼ y.

The guard (x = y + 1) is rigid since x uniquely determines y, and vice versa. However, it is impossible to describe the language ⋆ in this logic. In particular, the above formula ⋆⋆ can be rewritten as ¬∃ x, y. (x ≠ y) ∧ x ∼ y, but this time the guard x ≠ y is not rigid: for a given x, there can be several y such that x ≠ y.

It may seem a priori that the fact that rigidity is a semantic property is a severe drawback. This is not the case since (i) rigidity can be enforced syntactically, and (ii) rigidity is decidable for formulas in our logic.

To validate the robustness of our approach, we also answer to the following question inspired from the seminal Schützenberger-McNaughton-Papert result: Does the rigidly guarded FO logic (i.e., the first-order fragment of rigidly guarded MSO) correspond to aperiodic orbit finite data monoids?

We answer this question positively as well. We finally consider data languages recognizable by finite memory automata and we prove that a natural variant of rigidly guarded MSO, called ∃backward-rigidly guarded MSO captures the class of data languages recognized by non-deterministic finite memory automata.

Overall, we don't claim that data languages recognizable by orbit finite data monoids are the counterpart to the notion of regular languages in the standard theory, since this model is rather expressively weak (see related work below). However, in this restricted framework, we are able to recover several of the major results which hold for usual regular languages.

Related work. This work is highly related to the well known theory of regular languages. We refer by this to the key equivalence between monadic logic and regular languages due to Büchi [START_REF] Büchi | Weak second-order arithmetic and finite automata[END_REF], and the Schützenberger-McNaughton-Papert result that characterizes the subclass of first-order definable languages [START_REF] Schützenberger | On finite monoids having only trivial subgroups[END_REF][START_REF] Mcnaughton | Counter-free Automata[END_REF].

The other branch of related work is the one concerned with languages of data words. The first contribution in this direction is due to Kaminski and Francez [START_REF] Kaminski | Finite-memory automata[END_REF], who introduced finite memory automata (FMA for short). These automata possess a fixed finite set of registers that can store data values. At each step such an automaton can compare the current data value with the values stored in the registers, and can decide to store this value in some register (forgetting the previous content of the register). This model of automaton, in its non-deterministic form, has a decidable emptiness problem and an undecidable universality problem (decidability of the latter problem is recovered in the deterministic variant).

Recently, the deterministic model of FMA has been modified by requiring a stricter policy in the use of registers [START_REF] Benedikt | What you must remember when processing data words[END_REF]. This modification does not affect the expressive power of the model, but, as opposed to the original model, the new model can be efficiently minimized. In [START_REF] Benedikt | Automata vs. logics on data words[END_REF] partial results on relating automata to logics are also given. The question of characterizing the first-order logic definable language among the languages recognized by deterministic FMA is still open.

Many other automaton models for data languages have been studied in the literature (see [START_REF] Schwentick | Automata for XML -a survey[END_REF] for a survey). These include pebble automata [START_REF] Neven | Finite state machines for strings over infinite alphabets[END_REF] and data automata [START_REF] Bojańczyk | Twovariable logic on words with data[END_REF], the latter introduced as a mean of capturing decidable logics over data words. The algebraic theory for these models has not been developed, nor is there an exact characterization of definability in logics for any of these models.

Contribution and structure of the paper. These are our contributions:

1. We show how infinite orbit finite data monoids can be finitely represented.

2. We introduce a new logic called "rigidly guarded MSO" -a natural weakening of MSO logic with data equality tests. Although the syntax of our logic is based on a semantic property, one can decide whether a formula belongs to the logic or not.

3. We show that satisfiability of rigidly guarded MSO formulas is decidable.

4. We show that rigidly guarded MSO is as expressive as orbit finite data monoids, and that its first-order fragment corresponds precisely to aperiodic orbit finite data monoids.

5. We give a decidable variant of rigidly guarded MSO that captures the data languages recognized by non-deterministic finite memory automata and has a decidable satisfiability problem. We also provide a decidable logic for data trees along the same lines.

Section 2 gives preliminaries on data languages and data monoids, and explains how to define representations of data monoids with finitely many orbits. Section 3 introduces rigidly guarded MSO and its first-order fragment. Section 4 describes the translation from rigidly guarded MSO (resp., FO) formulas to orbit finite data monoids (resp., aperiodic orbit finite data monoids) recognizing the same languages. Section 5 describes the converse translation, namely, from (aperiodic) orbit finite data monoids to rigidly guarded MSO (resp., FO) formulas. Section 6 introduces a variant of rigidly guarded MSO that captures precisely the class of languages recognized by non-deterministic finite memory automata. Finally, Section 7 provides an assessment of the results and related open problems.

will consider monoids whose elements have finite memory (this property is called finite support axiom and the resulting algebraic objects data monoids).

Definition 1. A data monoid M = (M, ⋅, ˆ) over C is a monoid (M, ⋅) that is acted upon by G C , in which every element has finite memory.

Unless otherwise stated, data monoids are defined over the set D of data values.

The orbit of an element s of M = (M, ⋅, ˆ) is the set of all elements τ (s) with τ ∈ G D . Note that two orbits are either disjoint or equal. We say that M is orbit finite if it contains finitely many orbits. It is easy to see that if two elements are on the same orbit, then their memories have the same size. Hence an orbit finite data monoid has a uniform bound on the size of the memories (this is not true for arbitrary data monoids).

A morphism between two data monoids M = (M, ⋅, ˆ) and N = (N, ⊙, ˇ) is a monoid morphism that commutes with the action of renamings.A data language

L ⊆ (D × A) * is recognized by a morphism h ∶ (D × A) * → M if the membership of a word u ∈ (D × A) * in L is determined by the element h(u) of M, namely, if L = h -1 (h(L)). As L is closed under renamings, h(L) is a union of orbits.
Finite presentations of data monoids. Since orbit finite data monoids are infinite objects, we need suitable representations that ease algorithmic manipulation. The basic idea is to consider the restriction of an orbit finite data monoid to a finite set of data values: The above proposition shows that the restriction of an orbit finite data monoid M over a sufficiently large finite set C uniquely determines M. A more careful analysis shows that many operations on orbit finite data monoids (e.g., the product of two such monoids, the quotient with respect to a congruence) can be performed at the level of the finite restriction. This allows us to effectively compute the results of algebraic operations on orbit finite data monoids.

Term-based presentations of data monoids. We have just shown how we can represent an infinite data monoid by a finite one. It is also possible to give a more explicit presentation of orbit finite data monoids using what we call a term-based presentation system. Each element is a term of the form o(d 1 , . . . , d k ) in which o is an orbit name (belonging to some fixed set) of a fixed arity k, and d 1 , . . . , d k are distinct values. Those terms are furthermore considered modulo an equivalence relation, and equipped with a binary operation. Such a presentation is valid if the binary operation is associative over the equivalence classes, and if the data values respect the renaming policy required for data monoids. Under those suitable assumptions, the equivalence classes of terms equipped with the associative operation as product and the natural renaming operations form a data monoid. Furthemore, if there are finitely many orbit names, then the represented data monoid is orbit finite. We also show that conversely, every orbit finite data monoid can be represented by such a term-based representation, using finitely many orbit names.

This kind of presentation ease algorithmic manipulations of the elements of the data monoid, and are heavily used in the proofs. Some open questions are directly related to this presentation such as: is it possible to get rid of the equivalence relation for recognizing a language of data words?

Rigidly guarded logics

From now on, we abbreviate monadic second-order logic with data equality tests by MSO. MSO formulas are built up from atoms of the form x < y, a(x), x ∈ X, or x ∼ y, using boolean connectives and existential quantifications over first-order variables (e.g., x, y, . . .) and monadic second-order variables (e.g., X, Y, . . .). The meaning of an atom x ∼ y is that the data values at the two positions that correspond to the interpretation of the variables x and y must be the same. The meaning of the other predicates is as usual.

Here we introduce a new logic called "rigidly guarded MSO". We say that a formula ϕ(x, y) with two free first-order variables x, y is rigid if for all data words u ∈ (D × A) * and all positions x (resp., y) in u, there is at most one position y (resp., x) in u such that u ⊧ ϕ(x, y). Rigidly guarded MSO is obtained from MSO by enforcing the following restriction: every data equality test of the form x ∼ y must be guarded by a rigid formula ϕ(x, y). Precisely, the formulas of rigidly guarded MSO are build up using the following grammar:

ϕ ∶= ∃ x. ϕ ∃ Y . ϕ x < y a(x) x ∈ Y ¬ϕ ϕ ∧ ϕ ϕ rigid (x, y) ∧ x ∼ y
where a ∈ A and ϕ rigid (x, y) is a rigid formula that is generated by the same grammar. Rigidly guarded FO is the first-order fragment of rigidly guarded MSO.

The notion of rigidity is a semantic property, and this may seem problematic. However, we can enforce rigidity syntactically as follows. Instead of a guard ϕ rigid (x, y) in a formula, one uses the new guard

φrigid (x, y) = def ϕ rigid (x, y) ∧ ∀ x ′ , y ′ . ϕ rigid (x ′ , y ′ ) → (x = x ′ ↔ y = y ′ ) .
It is easy to check that φrigid is always rigid, and that furthermore, if ϕ rigid is rigid then it is equivalent to φrigid . This trick allows us to enforce rigidity syntactically. We will also see in Corollary 2 below that one can decide if a formula respects the rigidity assumption in all its guards (the problem being undecidable when data tests are not guarded).

We remark that in this logic, the similar constructions ϕ rigid (x, y) ∧ x ≁ y, ϕ rigid (x, y) → x ∼ y, and ϕ rigid (x, y) → x ≁ y can be derived. This is thanks to the Boolean equivalences ϕ

→ ϕ ′ iff ϕ → (ϕ ∧ ϕ ′ ), ϕ ∧ ¬ϕ ′ iff ¬(ϕ → ϕ ′ ), and ϕ → ¬ϕ ′ iff ¬(ϕ ∧ ϕ ′ ).
Example 1. Let us consider the language L ≥k of all data words that contain at least k different data values. If k = 1 we just need to check the non-emptiness of the word by the sentence ∃ x. true. For k = 2 it is sufficient to test for the existence of two distinct consecutive data values, using for instance the formula ∃ x, y. (x + 1 = y) ∧ x ≁ y. For k > 2, one can by induction as follows. One first observes that if a word has at least k distinct data values, then there is a minimal factor witnessing this property, say [x, y]. A closer inspection reveals that, in this case, [x + 1, y -1] is a maximal factor that uses exactly k -2 data values and thus belongs to the language L ≥k-2 ∖ L ≥k-1 . By induction, the fact that [x + 1, y -1] is a maximal factor that belongs to L ≥k-2 ∖ L ≥k-1 is expressible in rigidly guarded FO by a formula ϕ(x, y). Furthermore, this formula ϕ(x, y) is rigid according to its semantic definition. We conclude that the language L ≥k is defined by the formula ∃ x, y. ϕ(x, y) ∧ x ≁ y.

To simplify the notation, it is sometimes convenient to think of a first-order variable x as a second-order variable X interpreted as a singleton set. Therefore, by a slight abuse of notation, we shall often write variables in uppercase letters, without explicitly saying whether these are first-order or second-order variables (their correct types can be inferred from the atoms they appear in). As usual, we write ϕ(X 1 , . . . , X m ) whenever we want to make explicit that the free variables of ϕ are among X 1 , . . . , X m . Moreover, given a formula ϕ(X 1 , . . . , X m ), a data word u ∈ (D × A) * , and some unary predicates U 1 , . . . , U m ⊆ Dom(u), we write u ⊧ ϕ(U 1 , . . . , U m ) whenever ϕ holds on u by interpreting the free variables X 1 , . . . , X m with the predicates U 1 , . . . , U m .

As usual, given a formula ϕ( X) with some free (first-order or monadic secondorder) variables X 1 , . . . , X m , one can see it as defining the language

ϕ = {⟨u, U 1 , . . . , U m ⟩ ∶ u ⊧ ϕ(U 1 , . . . , U m )} ⊆ (D × A × B m ) *
where B denotes the binary alphabet {0, 1} and ⟨u, U 1 , . . . , U m ⟩ is the word over the alphabet

D × A × B m that has letter (d, a, b 1 , . . . , b m ) at position i iff (d, a)
is the i-th letter of u, and for all j = 1 . . . m, b j is 1 if i ∈ U j , and 0 otherwise.

From the logic to data monoids

In this section, we show that every data language defined by a rigidly guarded MSO sentence is recognized by an orbit finite data monoid. Our proof follows the classical technique for showing that MSO definable languages over standard words can be recognized by monoids. Namely, we show that each construction in the logic corresponds to a closure under some operation on recognizable languages: disjunction corresponds to union, negation corresponds to complement, existential quantification corresponds to projection, etc.

The principle of the proof is to establish that, given a rigidly guarded MSO formula ϕ( X), the language ϕ is recognized by an orbit finite data monoid. Though this statement is true, it cannot be used -as it is the case in the standard theory -as an induction hypothesis. The problem is that the operation that corresponds to existential quantification (i.e. projection) transforms an orbit finite data monoid into a data monoid which is not orbit finite, in general. That is why our induction hypothesis is stronger, and states that ϕ is recognized by an orbit finite data monoid via a projectable morphism, to be defined below (we write s ≐ t whenever the elements s and t are in the same orbit): Definition 3. Let h be a morphism from the free data monoid (D ×A ×B m ) * to a data monoid M = (M, ⋅, ˆ). We say that h is projectable if for all data words u ∈ (D × A) * and all tuples of predicates Ū = (U 1 , . . . , U m ) and

V = (V 1 , . . . , V m ), h(⟨u, Ū ⟩) ≐ h(⟨u, V ⟩) implies h(⟨u, Ū ⟩) = h(⟨u, V ⟩) .
We now state the theorem, which is at the same time our induction hypothesis: Theorem 1. For all rigidly guarded MSO formulas ϕ( X), the language ϕ is effectively recognized by an orbit finite data monoid with a projectable morphism.

From the above theorem we obtain, in particular, the following key corollaries: Corollary 1. Every data language definable in rigidly guarded MSO (resp., rigidly guarded FO) is recognizable by an orbit finite data monoid (resp., aperiodic orbit finite data monoid).

Note that the claim for the first-order case is deduced using the result that every language recognized by an orbit finite data monoid and definable in FO (without any rigidity assumption) is recognized by an aperiodic orbit finite data monoid [START_REF] Bojańczyk | Data monoids[END_REF]. That is why Theorem 1 needs not to consider the first-order case.

Corollary 2. The satisfiability problem for rigidly guarded MSO logic is decidable. Moreover, one can decide whether a formula belongs to the rigidly guarded MSO logic, and in this case whether the formula is rigid.

The proof of Theorem 1 is by structural induction on the rigidly guarded MSO formulas: the translation of the atomic formulas x < y, a(x), x ∈ Y are easy (at least towards non-aperiodic monoids) and the translations of the Boolean connectives are as in the classical case.

The translation of the existential closures uses a powerset construction on orbit finite data monoids. Since data monoids are in general infinite objects, the standard powerset construction would yield infinitely many orbits even if the original data monoid has finitely many of them. In our case, the construction remembers all possible elements of the original monoid, but since the morphism is projectable, one never has to store more than one element per orbit. Indeed, whenever another element in the same orbit is encountered, it has to be equal to the one already present: this limitation allows us to preserve orbit finiteness.

The most technical part concerns the translation of the rigidly guarded data tests ϕ(x, y) ∧ x ∼ y. The rigidity assumption on the guard ϕ(x, y) is crucial for this result: if ϕ(x, y) were not rigid, then the data monoid recognizing ϕ(x, y) ∧ x ∼ y would still be orbit finite, but the morphism would in general not be projectable. The proof that ϕ(x, y) ∧ x ∼ y is recognized via a projectable morphism requires a bit of analysis since rigidity is a semantic assumption and hence one cannot directly deduce from it a property for the data monoid. However, one can use the rigidity property for "normalizing" the data monoid, allowing the construction to go through.

From data monoids to the logic

Having shown that every language defined by a rigidly guarded MSO (resp., FO) formula is recognized by an orbit finite data monoid (resp., by an aperiodic orbit finite data monoid), we now show the converse.

Theorem 2. Given an orbit finite data monoid M, a morphism h from the free data monoid to M, and an orbit o, one can compute a rigidly guarded MSO sentence ϕ that defines the data language L = h -1 (o). Moreover, if M is aperiodic, then ϕ is a rigidly guarded FO sentence. This is the most technical result of the paper. Note that in the classical theory of regular languages, the analogous of Theorem 2 (at least the part involving only MSO) is straightforward: indeed, a monoid can be used as an automaton, and it is sufficient to write an MSO formula that guesses a run of such an automaton and checks that it is valid and accepting. We cannot use such a proof for data monoids: not only there is no equivalent automaton model, but furthermore, the above approach is intrinsically not compatible with the notion of rigidity.

Our proof follows a structure similar to Schützenberger's proof that languages recognized by aperiodic monoids are definable by star-free expressions (i.e., in FO logic). The proof relies on an induction on the structure of ideals of the data monoid, the so called Green's relations [START_REF] Pin | Mathematical foundations of automata theory[END_REF]. This requires specific study of this theory for orbit finite data monoids. Such a study was initiated by Bojańczyk [START_REF] Bojańczyk | Data monoids[END_REF], but we had to develop several new tools for our proof to go through (these tools concern the size of H-classes and the analysis of the memory inside the Jclasses). As opposed to the classical case, the proof is significantly more involved for MSO compared to FO.

Logics for finite memory automata

In this section, we try to see how guards as introduced above can help constructing decidable logics. We consider languages recognized by finite memory automata (FMA) [START_REF] Kaminski | Finite-memory automata[END_REF]. These extend finite state automata by a finite set of registers, storing values from an infinite alphabet D. Data words are processed from left to right. At each step the automaton compares (up to equality) the current input value with the values that are stored in its registers. Based on this information, the automaton decides whether or not to store the input value in one of its registers, updates its state, and moves one symbol to the right.

The deterministic variant of FMA can be viewed as the natural automaton counterpart of orbit finite data monoids. However, deterministic FMA are more expressive than orbit finite data monoids, as witnessed by the language

L = def {d 1 . . . d n ∶ n ∈ N, d 1 = d i for some 1 < i ≤ n}
which is recognizable by deterministic FMA, but not by orbit finite data monoids. Moreover, unlike classical finite automata, non-deterministic FMA are even more expressive than deterministic FMA, as witnessed by the language

L ′ = def {d 1 . . . d n ∶ n ∈ N, d i = d j for some 1 ≤ i < j ≤ n}.
It thus comes natural to look for logical characterizations of data languages recognizable by deterministic (resp., non-deterministic) FMA.

A natural attempt at finding a logic for FMA consists in relaxing the notion of rigidity. One could imagine using backward-rigid guards for data tests. These are formulas ϕ(x, y) that determine the leftmost position min(x, y) from the rightmost position max(x, y) (but possibly not the other way around). Formulas of backward-rigidly guarded MSO are built up using the grammar:

ϕ ∶= ∃ x. ϕ ∃ Y . ϕ x < y a(x) x ∈ Y ¬ϕ ϕ ∧ ϕ ϕ backward (x, y) ∧ x∼y
where ϕ backward is a backward-rigid formula generated from the same grammar (as usual, we can enforce backward-rigidity syntactically). For example the above language L can be easily defined by the backward-rigidly guarded MSO sentence ∃ x, y. (x < y ∧ ∀ z. x ≤ z) ∧ x ∼ y. One can translate backward-rigidly guarded MSO formulas to equivalent deterministic FMA, but not the other way around: Proposition 2. Every language definable in backward-rigidly guarded MSO is recognizable by deterministic FMA. There is a language recognized by a deterministic FMA which cannot be defined in backward-rigidly guarded MSO.

We do not have a candidate logic that corresponds precisely to deterministic FMA. However, we are able to characterize the larger class of languages recognized by non-deterministic FMA. The logic for this class is obtained from backward-rigidly guarded MSO by allowing the guards to use additional secondorder variables (which however needs to be quantified existentially in the outermost part of the formula). The logic, abbreviated ∃backward-rigidly guarded MSO, consists of the formulas ∃ Z. ϕ, with ϕ is generated by the grammar ϕ ∶= ∃x. ϕ ∃Y . ϕ x<y a(x) x∈Y ¬ϕ ϕ ∧ ϕ ϕ ∃backward (x, y, Z) ∧ x∼y where ϕ ∃backward is a formula from the same grammar that determines min(x, y) from max(x, y) and Z, and where the quantifications are over variables different from Z (the variables Z are quantified only in the outermost part of ∃ Z. ϕ). Theorem 3. A language is definable in ∃backward-rigidly guarded MSO iff it is recognizable by non-deterministic FMA.

As it happens for rigidly guarded MSO logic, one can derive from Theorem 3 the following decidability results: Corollary 3. The satisfiability problem for ∃backward-rigidly guarded MSO is decidable. Moreover, one can decide whether a formula belongs to the ∃backwardrigidly guarded MSO, and in this case whether the formula is ∃backward-rigid.

It is also easy to generalize both Theorem 3 and Corollary 3 to data tree languages recognized by non-deterministic finite memory tree automata [START_REF] Kaminski | Tree automata over infinite alphabets[END_REF]. For this we use a natural variant of ∃backward-rigidly guarded MSO on data trees. The guarded tests in this case are of the form ϕ ∃ downward (x, y, Z) ∧ ϕ ′ ∃ downward (x, z, Z) ∧ y ∼ z where ϕ ∃ downward (x, y, Z) (resp. ϕ ′ ∃ downward (x, z, Z)) is a formula in the logic that determines the position y (resp., z) from an ancestor x in the data tree and the second-order variables Z. This logic happens to be equivalent with the natural extension of non-deterministic FMA to trees.

Finally, it is natural to look for effective characterizations of data languages that are both recognizable by non-deterministic FMA and definable in (unrestricted) FO. However, it is known that such characterization cannot be achieved: in [START_REF] Benedikt | Automata vs. logics on data words[END_REF] it has been shown that the problem of determining whether a language recognized by a non-deterministic FMA is definable in FO is undecidable. The problem of characterizing FO within the class of languages recognizable by deterministic FMA is still open.

Conclusion and future work

We have shown that the algebraic notion of orbit finite data monoid corresponds to a variant of the logic MSO which is -and this is of course subjective -natural. It is natural in the sense that it only relies on a single and understandable principle: guarding data equality tests by rigidly definable relations.

We believe that this notion of guard is interesting by itself. Of course, it is not the first time that guards are used to recover some decidability properties from a too expressive logic. What is more original in the present context is the equivalence with the algebraic object, which shows that this approach is in some sense maximal: it is not just a particular technique among others for having decidability, but it is sufficient for completely capturing the expressiveness of the very natural algebraic model.

Another contribution of the present work is the development of the structural understanding of orbit finite data monoids. By structural understanding, we refer to Green's relations. These relations form a major tool in most involved proofs concerning finite monoids. The corresponding study of Green's relations for orbit finite data monoids was already a major argument in the proof of [START_REF] Bojańczyk | Data monoids[END_REF], and it had to be developed even further in the present work.

Finally, we proved that a variant of the same logic captures the larger class of data languages recognized by non-deterministic NFA.

Definition 2 .

 2 Given a data monoid M = (M, ⋅, ˆ) and C ⊆ D, we define the restriction of M to C to be M C = M C , ⋅ C , ˆ C , where M C consists of all elements s ∈ M such that mem(s) ⊆ C, ⋅ C is the restriction of ⋅ to M C , and ˆ C is the restriction of ˆto G C and M C . Note that s ⋅ t ∈ M C and τ (s) ∈ M C for all s, t ∈ M C and τ ∈ G C . Hence, if C is finite, M C is a finite data monoid. 3 Hereafter, we denote by M the maximum cardinality of the memories of the elements of an orbit finite data monoid M. Proposition 1. Let M, M ′ be orbit finite data monoids such that M = M ′ and let C ⊆ D be of cardinality at least 2 M . If M C and M ′ C are isomorphic, then so are M and M ′ .

One has to keep in mind that data monoids over finite sets do not satisfy the same properties as those over infinite sets. For instance, the Memory Theorem, as stated in[START_REF] Bojańczyk | Data monoids[END_REF], does not hold for data monoids over finite sets.

Acknowledgments. We would like to thank Michael Benedikt and Anca Muscholl for the many helpful remarks on the paper.

We are only at the beginning of understanding the various notions of recognizability for data languages. However, several interesting questions were raised during our study. Some of them concern the fine structure of the logic:

The nesting level of guards seems to be a robust and relevant parameter in our logic. Can we understand it algebraically? Can we decide it? Other questions concern the more general model of FMA:

Can we characterize among the languages recognized by deterministic FMA the ones recognizable by orbit finite data monoids? Can we give a logic equivalent to deterministic FMA and characterize its FO fragment?

Data Monoids

In this paper, D will usually denote an infinite set of data values (e.g., d, e, f, . . .) and A will denote a finite set of symbols (e.g., a, b, c, . . .). A data word over the alphabet

Given a set C ⊆ D of data values, a (data) renaming on C is a permutation on C that is the identity for all but finitely many values of C. We denote by G C the set of all renamings on C. Renamings are naturally extended to tuples of data values, data words, sets of data words, and so on. A data language over D × A is a set of data words in (D × A) * that is closed under renamings in G D .

Recall that a monoid is an algebraic structure M = (M, ⋅) where ⋅ is an associative product on M and M contains an identity 1 M . A monoid is aperiodic if for all elements s, there is n such that s n = s n+1 . We say that the set G C of renamings acts on a monoid M = (M, ⋅) if there is a function ˆthat maps every renaming τ ∈ G C to an automorphism τ on M. That is, for all renamings τ, π ∈ G C and all elements s, t ∈ M , we have (i) τ ○ π = τ ○ π, (ii) τid (s) = s, where τ id is the identity function on C, (iii) τ (s) ⋅ τ (t) = τ (s ⋅ t), and (iv) τ (1 M ) = 1 M . For example, consider the free monoid ((D × A) * , ⋅) consisting of all finite words over D × A equipped with the operation of juxtaposition (the empty word ε playing the role of the identity). The group G D of data renamings acts on the free monoid when the action is defined by τ ((d 1 , a 1 ) . . .

We say that a renaming τ is a stabilizer of an element s of a monoid M acted upon by G C , if τ (s) = s. A set C ′ ⊆ D of data values supports an element s if all renamings that are the identity on C ′ are stabilizers of s. It is known that the intersection of two sets that support s is a set that supports s as well [START_REF] Bojańczyk | Data monoids[END_REF][START_REF] Gabbay | A new approach to abstract syntax with variable binding[END_REF]. Hence we can define the memory of s, denoted mem(s), as the intersection of all sets that support s. Note that there are finite monoids whose elements have infinite memory (see [START_REF] Bojańczyk | Data monoids[END_REF] for an example). On the other hand, monoids that are homomorphic images of the free monoid contains only elements with finite memory. As we are interested in homomorphic images of the free monoid, we


Chengjin Wang
email: cjwang@igsnrr.ac.cn

César Ducruet

New port development and global city making: Emergence of the Shanghai-Yangshan multilayered gateway hub

Keywords: Asia, China, corridor, offshore hub, port system evolution, urban growth, Yangtze River Delta

Planned as Shanghai's new port, Yangshan is currently expanding its roles as transhipment hub and integrated logistics/industrial center in the Asia-Pacific region. This paper examines the impact of the emergence of Yangshan on the spatial pattern of the Yangtze River Delta since the 1970s, with reference to existing port system spatial evolutionary models. While this emergence confirms the trend of offshore hub development and regionalization processes observed in other regions, we also discuss noticeable deviations due to territorial and governance issues. Strong national policies favoring Shanghai's vicinity rather than Ningbo as well as the growth of Yangshan beyond sole transhipment functions all contribute to Shanghai's transformation into a global city.

Introduction

Throughout the literature on port cities, a majority of the research provides a separate discussion on either port or urban functions. Port and urban specialists often focus on what may appear as processes and actors of distinctly different nature. One example is the large body of research on so-called port systems where neighbouring port nodes go through successive development phases marked by varying traffic concentration levels. Geographers have been particularly active in describing the spatial evolution of port systems where load centers and offshore hubs influence the port hierarchy due to their competitiveness and attractiveness in the transport and logistics chain at sea and on land [START_REF] Fleming | Spatial characteristics of transportation hubs: Centrality and intermediacy[END_REF][START_REF] Notteboom | Port regionalization: Towards a new phase in port development[END_REF]). Yet, reference to the territorial aspects of these changes is generally kept minimal due to a central focus on transport players and flows. This paper chooses another perspective that is to consider port dynamics as illustrations and components of wider urban transformation processes. Maritime ports have been recently recognized to be still i m p o r t a n t p a r t o f urban a r e a s despite many changes in the distribution and operation of transport and value chains [START_REF] Peter | Why are maritime ports (still) urban, and why should policy makers care?[END_REF]. Although ports and port terminals perform specific activities not always in accordance with their adjacent economy, they can u s u a l l y be seen as one function among others in the wider urban fabric. Port cities are thus typical illustrations of local-global interactions taking place between territories, production networks, and commodity chains through physical transfers and sector-specific services [START_REF] Hesse | Cities, material flows and the geography of spatial interaction: Urban places in the system of chains[END_REF][START_REF] Jacobs | Integrating world cities into production networks: the case of port cities[END_REF][START_REF] Jacobs | The location and global network structure of maritime advanced producer services[END_REF]. Such port-cityregion relationships are particularly intense in Asia where urban and port issues are very much intermingled, which seem to be less significant in contexts such as Europe (Van der [START_REF] Van Der Lugt | Ports as locations for logistics activities[END_REF][START_REF] Lee | Spatial glocalization in Asia-Pacific hub port cities: A comparison of Hong Kong and Singapore[END_REF]. Many case studies confirm this fact.

For example studies of Kaohsiung [START_REF] Haynes | Regional port dynamics in the global economy: the case of Kaohsiung, Taiwan[END_REF], Busan [START_REF] Frémont | The emergence of a mega-port: The case of Busan, from the local to the global[END_REF], Dubai [START_REF] Jacobs | What conditions supply chain strategies of ports? The case of Dubai[END_REF], Hong Kong (Wang and Chen, 2010), and Incheon [START_REF] Ducruet | The flight of Icarus? Incheon's transformation from port gateway to global city[END_REF] all show that port dynamics are adapted to broader metropolitan processes. These adaptations may be changing as new types of nodes are emerging through a combination of transport, supply chain, logistics, and international trade activities [START_REF] Palmer | Current port trends in an historical perspective[END_REF] which have created multilayered gateways ensuring multiple functions which together have new urban impacts.

To date little has been said about the case of Shanghai, which has developed as one of the world's largest seaports and global financial center. Research that has been done has most likely studied Shanghai's urban functions with reference to Pudong rather than its port [START_REF] Yeung | Bargaining with transnational corporations: The case of Shanghai[END_REF]; W u , 2 0 0 0 ; [START_REF] Yusuf | Pathways to a world city: Shanghai rising in an era of globalization[END_REF][START_REF] Cai | Measuring world city formation: The case of Shanghai[END_REF][START_REF] Wei | Development zones, foreign investment, and global city formation in Shanghai[END_REF][START_REF] Lai | Global cities in competition? A qualitative analysis of Shanghai, Beijing and Hong Kong as financial centres[END_REF], or e x p l o r e d its maritime functions barely mentioning i t s emerging global city functions [START_REF] Wang | Port governance in China: A review of policies in an era of internationalizing port management practices[END_REF]. Exceptions have been the recent study by [START_REF] Huang | The growth of global hub port cities under globalisation: The case of Shanghai international shipping centre[END_REF], questioning Shanghai's place as an Asian model city and the earlier study by [START_REF] Yan | Areal expansion of urban Shanghai[END_REF] on the interdependence between port and urban growth in Shanghai's history. The coincidence of rapid urban and port growth in Shanghai thus deserves special attention. That attention will need to include insight on the evolution of global hub port cities, believed to exhibit certain similarities across Asia [START_REF] Lee | A tale of Asia's world ports: The spatial evolution in global hub port cities[END_REF]. In addition the rapid integration of China in global shipping and logistics networks has been well documented [START_REF] Comtois | The integration of China's port system into global container shipping[END_REF][START_REF] Cullinane | The container shipping industry and the impact of China's Accession to the WTO[END_REF][START_REF] Yap | Competition dynamics between container ports in East Asia[END_REF] as well as the diffusion of containerization and the emergence of hub ports [START_REF] Rimmer | China's container-related dynamics, 1990-2005[END_REF][START_REF] Cullinane | Asian Container Ports: Development, Competition and Co-operation[END_REF]. Scholars h a v e principally looked at Chinese ports such as port-FEZ bundles in Tianjin [START_REF] Wang | Port -FEZ bundles as spaces of global articulation: The case of Tianjin, China[END_REF], port development in the Pearl River Delta [START_REF] Wang | The evolution of a regional container port system: The Pearl River Delta[END_REF][START_REF] Airriess | The regionalization of Hutchison Port Holdings in Mainland China[END_REF], and traffic reorientation across the Yellow Sea [START_REF] Lee | Trade reorientation and its effects on regional port systems: The Korea-China link along the Yellow Sea Rim[END_REF]).Shanghai's prominence as main gateway for the Yangtze River has been well discussed in terms of port competition and corridor formation and insight has extended to include the current hinterland penetration of logistics networks across the Yangtze River Valley (YRV) [START_REF] Cullinane | Port competition between Shanghai and Ninbgo[END_REF][START_REF] Veenstra | The development of the Yangtze River container port system[END_REF]. To date very limited attention has been paid to Yangshan, a gigantic new port project operating since 2005 which has lifted Shanghai into a new level of global activity.

Yangshan raises some problems and opportunities that reflect the coincidence between port expansion and global city formation. Beyond the sole provision of additional capacity and better technical standards, one main factor in the emergence of Yangshan is the difficulty for Shanghai to maintain and increase both its gateway (hinterland) and hub (maritime) functions at a single node. Such pressures are felt simultaneously at regional and local level and are expressed in the shift of some shipping activity away from the inner port (as in the spatial development model of [START_REF] Bird | The Major Seaports of the United Kingdom[END_REF]) and captured in port system evolution models (see [START_REF] Ducruet | Going West? Spatial polarization of the North Korean port system[END_REF] for a synthesis). A dual system mixing hub and gateway functions is thus emerging in contrast to more classic experiments of new port development elsewhere.

Another factor central to Yangshan's influence upon Shanghai is highly political, as seen in problems of cross-border governance among different provincial jurisdictions. Here its experience is shared with other Asian port cities such as Busan and Incheon in South Korea [START_REF] Frémont | The emergence of a mega-port: The case of Busan, from the local to the global[END_REF][START_REF] Ducruet | The flight of Icarus? Incheon's transformation from port gateway to global city[END_REF], Hong Kong and Shenzhen [START_REF] Song | Regional container port competition and co-operation: The case of Hong Kong and South China[END_REF], and some other peripheral port developments in Asia [START_REF] Slack | The challenge of peripheral ports: An Asian perspective[END_REF]. These two dimensions emerge as growing global cities emphasise the control of physically grounded port and logistics functions in a competitive context, and how port dynamics, in turn, can foster economic activities beyond sole transhipments. It is the interdependencies between these two aspects that provide the agenda of the research reported in this paper.

The remainder of the paper is as follows. Section 2 describes the evolution of the entire YRD port system since the early 1970s in the light of port system evolutionary models.

Section 3 analyzes with more scrutiny the deviations from the models, with a special focus on the emergence of Yangshan new port in terms of (trans-)port governance, urban and regional planning, economic development problems and opportunities. Conclusions are proposed in section 4 about the lessons learned from this case study for further research on port system evolution.

Port system evolution in the Yangtze River Delta (1970-2010)

Since the 1960s, a wide-ranging literature has provided a number of port system evolutionary models and applications, recently classified by [START_REF] Ducruet | Going West? Spatial polarization of the North Korean port system[END_REF] into concentration and de-concentration factors. Although such ideal-typical approaches remain limited in explaining particular cases and contexts [START_REF] Weber | Diverging narratives: Evaluating the uses of the ideal-typical sequence of transport network development[END_REF], they are used in this paper to help reveal local deviations caused by specific territorial and governance issues and to facilitate comparisons with other port systems worldwide. Although recent studies of Hong Kong [START_REF] Wang | A container load center with a developing hinterland: A case study of Hong Kong[END_REF] and peripheral port challenges in Asia [START_REF] Slack | The challenge of peripheral ports: An Asian perspective[END_REF] question the mechanical character of port system evolutionary models, the same authors recognized that trends affecting Pearl River Delta ports "are being replicated elsewhere" (Wang and Slack, 2000, p. 263). Figure 1 provides a synthesis of stylized phases affecting a container port system, with reference to the pioneer model of [START_REF] Edward | Transport expansion in underdeveloped countries: A comparative analysis[END_REF] and to the recent synthesis of other classic models by [START_REF] Notteboom | Port regionalization: Towards a new phase in port development[END_REF]. The latter notably added a sixth phase about the emergence of an offshore hub that is relevant to the development of Yangshan port. Each phase has a generic sequence, which when compared to actual outcomes can detect deviations caused by local particularities. To provide a starting point for an analysis along these lines Figure 2 provides key traffic data by port and by period for the Yangtze port hierarchy.

[Insert Figure 1: Spatial evolution model of a container port system] [Insert Figure 2:

Evolution of the YRD port hierarchy, 1979-2010]

Pre-containerization and containerization experiment (1970s)

Before the 1970s, the port system in the YRD was in the phase of pre-containerization.

Shanghai possessed locational advantage being at the junction of different transport networks, namely river and maritime shipping as well as north-south coastal shipping, and it became the main port of this region and even of the whole mainland China. In 1972, Shanghai handled about 72.1% of YRD's total traffic, conferring a high traffic concentration level to one port within a system, which greatly differs from the generic model where the first two phases represent a homogenous distribution between many ports with only a slight concentration on one main port. Shanghai also became the largest trade-gateway port and its international traffic accounted for 22% of its total traffic. Meanwhile, as the largest river ports in the YRD, Nanjing and Wuhu ports shared 13.6% and 6.5% of YRD's total traffic respectively. Other ports such as Nantong, Anqing, Tongling, Zhenjiang, Chizhou, Maanshan, Jiangyin, and Gaogang handled much less traffic, The observed spatial pattern is consistent with the pre-containerization phase of the model, with the notable difference that smaller ports have not experienced much development, for two main reasons. First, the north side of the Yangtze River estuary is an alluvial coast with poor physical conditions in terms of port construction. Second, before the 1970s, the planned economy resulted in limited maritime trade and lesser need for the development of seaports in North Zhejiang.

Since the early 1970s, YRD ports welcomed containerization (Figures 2 and3 International standards for container shipments at Chinese ports only started in the mid-1970s. In 1977, Shanghai port imported large and small forklifts as well as trailers from Japan, thereby becoming China's first port to handle international standard containers. Subsequently, international container shipping routes from Shanghai to Japan and Australia were opened in 1978 using what were originally bulk cargo vessels. The same year, Shanghai, Tianjin, and Qingdao ports handled 18,000 TEU altogether. The period 1972-1978 thus marks the phase of containerization experiment concerning Shanghai, Nantong, and Nanjing in the YRD. This confirms that containerization favored t h e largest ports first and spread through a hierarchical diffusion process. However, the lack of specialized handling facilities prevented higher traffic levels at traditional port terminals. Therefore, the introduction of container technology greatly favored traffic concentration in Shanghai at the expense of other ports, So a major difference b e t w e e n t h e a c t u a l o u t c o m e a n d Figure 1 w a s probably due to the way the controls of a centralized economy shaped shipping patterns.

Spread of containerization (1980s to mid-1990s)

In the late 1970s, the port system moved beyond the experimental phase and entered international container shipping. Since the early 1980s, the reform and a policy to open up the economy promoted the development of export-oriented industries in the YRD, resulting in a rapid increase of containerized cargoes and the popularization of container technology (Figures 3 and4). The container shipping route from Shanghai to the United States was launched in 1980, followed by other full container shipping routes to Japan, Europe, and West Africa. In addition, domestic shipping routes also developed, such as Dalian-Shanghai and YRD-Hong Kong. In 1983, Shanghai port reached a total traffic of about 80,000 TEUs. This success rapidly motivated other ports to apply this technology, such as Zhangjiagang in 1983, Nantong, and Nanjing in 1984. Zhangjiagang handled about 33,000 TEUs in 1986, and after the operation of Yangtze River shipping route from Shanghai to Wuhan in 1984, over 20 container shipping routes started their operations throughout mainland China, including river, coastal, and deep-sea shipping. An increasing number of ports developed international container shipping, such as Ningbo and Haimen in 1988, Anqing, Zhenjiang, Zhoushan, and Wuhu in 1990, Jiangyin in 1994, and Gaogang in 1995. Shanghai

Container hub port and concentration (mid-1990s to 2005)

Since the late 1990s, the YRD port system experienced a growing concentration at a few ports as can be seen in the trends in the Gini coefficient and the Herfindahl-Hirschman Index (HHI) in Figure 4 before stabilizing in the early 2000s, even though there was an increase in the number of ports. Concentration and de-concentration thus go together, as seen with the lowering traffic concentration at Shanghai. Indeed around 2000, 85% of YRD ports possessed container technology and handled about 7.25 million TEUs. Shanghai then handled 5.61 million TEUs, accounting for 77.4% of the YRD's total traffic, notably due to its concentration of most shipping routes to Hong Kong and Japan and to the polarization of a hub-feeder system for canal and river trade. Other ports started international services, such as Taizhou and Yangzhou in 1996, Zhapu in 1997, Changshu in 1998, Sheyang in 1999, and Changzhou, Hangzhou, Maanshan, and Taicang in 2000. Such parallel trends explain the stabilization of the number of ports in the 2000s and the subsequent decrease of concentration in the YRD. Yet, Shanghai maintained a strong polarization of flows as it benefited from Chinese government strategy to reinforce its role as an international shipping centre. Shanghai's shipping activity thus reached 1,494 monthly schedules of containerships in 2004, of which 279 are international and 416 are coastal, and handled14.55 million TEUs.

Such evidence somewhat contradicts the fourth phase of the model characterized by the dominance of one single gateway. For instance, Ningbo enjoyed high yearly growth rates of over 30% while attracting 115 shipping routes and 500 schedules a month. The growth of Ningbo occurred in parallel with the decline of other medium-sized ports such as Nantong, Nanjing, and Wuhu, due to less dynamic local economic development [START_REF] Veenstra | The development of the Yangtze River container port system[END_REF] and traffic limits associated with river transport compared with truck transport. The development of a domestic hub-feeder system centered upon Shanghai illustrates the latter's hinterland expansion (i.e. Jiangsu, Zhejiang, Anhui, Jiangxi, Hunan, Hubei, Chongqing, and Sichuan) on the level of the Yangtze River Valley (YRV) backed by new expressway and railway services as well as the dredging of the Yangtze River and the Great Canal. Feeder cargo from the YRV accounts for 50% of Shanghai's total traffic (excluding traffic related with the supply of Shanghai city itself) (see Figure 5).

Shanghai polarizes a major share of some inland river ports such as 80% and 48% of Jiujiang and Nanjing's container traffic respectively. Shanghai notably strengthened its gateway position by building logistics bases in the YRV and purchasing shares o f inland ports to a level of 40% in Chongqing, 55% in Wuhan, and 25% in Nanjing, while also cooperating with Wuhu, Taicang, Nantong, Jiangyin, and Wenzhou. Several small river ports such as Changsha, Nantong, and Yangzhou also became Shanghai's feeder ports. This trend to widen and deepen the catchment zone only partly matches the generic model as hinterland

Feeder traffic between Yangtze River ports and Shanghai]

Emergence of the offshore hub (2005)

With the growth of traffic, Shanghai port faced important local limitations on its further1 development, such as the growing size of vessels requiring deep-water access at terminals. Such constraints could lead to a decentralization phase (Rimmer, 1967a[START_REF] Rimmer | The search for spatial regularities in the development of Australian seaports[END_REF]) that is similar to the challenge of the periphery [START_REF] Hayuth | Rationalization and concentration of the U.S. container port system[END_REF] whereby large and congested gateways lose traffic to secondary ports. This could be facilitated by changes in shipping deregulations enabling transport players to focus more on service cost and quality rather than on the size of infrastructure [START_REF] Slack | Containerization, inter-port competition, and port selection[END_REF][START_REF] Ng | Assessing the attractiveness of ports in the North European container transhipment market: An agenda for future research in port competition[END_REF]. In this way a secondary port with poor hinterland access but good nautical accessibility can become the focus of important traffic gains depending on the availability of cheap land for terminal construction. To ward off these threats a so-called offshore hub can be developed in the vicinity of the large gateway and so maintain the significant role of the port while meeting the needs of the international carriers and terminal operators [START_REF] Baird | Global strategic management in liner container shipping[END_REF]. The main gateway may compensate the shifts of container services to the offshore hub by expanding its involvement in the logistics integration of the hinterland and also via increased activity at dry ports [START_REF] Palmer | Current port trends in an historical perspective[END_REF], as seen in the regionalization phase described by [START_REF] Notteboom | Port regionalization: Towards a new phase in port development[END_REF]. At the same time, the offshore hub can develop value-added activities in relation to a local cargo base [START_REF] Rodrigue | Foreland-based regionalization: Integrating intermediate hubs with port hinterlands[END_REF].

Although the regionalization process started earlier than in the models, as seen in the previous discussions, the construction of Yangshan new port well fits with the phase of diffusion and offshore hub. This consortium signed a deal to provide a 17 billion Yuan credit line for the port construction up to 2020. In consideration of the importance of Yangshan port for China's economy, the main stakeholders relied on themselves during this first phase of port construction. However, the port's excellent natural conditions and geographical location motivated many foreign investors to participate in the project, as in many similar projects of new port development [START_REF] Baird | Global strategic management in liner container shipping[END_REF]. World. This gradual opening to foreign players is believed to improve the efficiency of port infrastructures and operation as well as the management level.

[Insert Figure 6: Governance structure of Yangshan port]

Foreign players remain restricted in several aspects, however. For instance in 2007, SIG accepted to be placed under the authority of STI to operate and manage the construction of the third phase. Another example is SPAB imposing several guidelines to the selection of partners, such as the financial situation of the firm, its performance record as terminal operator, its ability to attract more shipping lines and to set up more routes, and its relationship with Shanghai. Such elements illustrate China's will to remain self-sufficient during the first steps of the construction process in order to avoid the domination of individual port operators. Even when attracting foreign investors, Chinese authorities maintain a complex structure of terminal ownership and stakeholder community, under a single port administration. In addition, one visible trend is the gradual shift from a structure dominated by terminal operators to a structure dominated by a variety of major shipping 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 111111111 lines [START_REF] Wang | Port governance in China: A review of policies in an era of internationalizing port management practices[END_REF], some of them being Chinese. For instance, phase 2 of Yangshan port construction welcomed investments from Hutchison Whampoa (32%), Maersk (32%), SIPG (16%), COSCO (10%), and CSCL (10%) through the joint venture called Shanghai Yadong InternationalContainerco.Ltd.Similarly,thethirdphase(partA)received investments from PSA (30%), CMA-CGM (10%), CSCL (30%), and SIPG (30%), thus demonstrating

[Insert Table 1: Construction phases of Yangshan port]

Diffusion and regionalization (since 2005)

Consistently with the discussion by [START_REF] Lemarchand | Regional integration and maritime range[END_REF] on the bigger growth rates of emerging ports compared with more mature ports, Yangshan rapidly increased its traffic within a few years (Figure 7), reaching 8.23 million TEUs in 2008, of which 48% was river shipping (against 43.1% in 2010) and 8-9% for international transhipment 5 , the rest being related with hinterland traffic through trucking over the Donghai Bridge. With reference to the model, we see that one crucialdimensionofthisdevelopmentphaseisthecodevelopmentofthemain gateway port and of the offshore hub through a mixture of deep-sea and short-sea services, thus taking the form and function of a dual hub and gateway. Such duality has been observed by Wang and Chen (2010): "Spatially, it has been evident that dual hub port systems appear in megacity regions such as the ports of Hong Kong and Shenzhen" but also Singapore and Tanjung Pelepas, Busan and Gwangyang. As seen in 5 Sea-river transshipment corresponds to traffic from the YRD to Yangshan port that is transshipped towards other Chinese mainland ports, Hong Kong, and/or foreign ports, while international transshipment is the traffic originating from overseas transiting through Yangshan port.

than 300 ports and 90 weekly schedules operated by 28 carriers, while short sea services (i.e. intra-Asian) concentrated at Waigaoqiao, Zhanghuabang, and Jungonglu. At present, Yangshan welcomes 900 to 1,100 container vessels monthly, of which one-third a r e o n international trading routes. Traffic patterns were also modified along the Yangtze corridor as 26 carriers opened 17 feeder routes between river ports and Yangshan. Such riverborne traffic is provided daily by 62 vessels, which account for 34.5% of Yangshan's total traffic. between Shanghai and the hinterland (e.g. Nanjing, Chengdu, Hefei, Bengbu, Changsha, Xi'an, Zhengzhou, Chongqing, Yiwu, Wenzhou, Ningbo, Nanchang, and Zhuzhou). Most cargo moves a short distance; the cargo coming from YRV currently accounts for 95% of Shanghai's rail-sea integrated traffic. This is supported by growing traffic flows over the Donghai Bridge 6 by truck (see Figure 9). Numerous carriers, shippers, and forwarders have also spread their offices across this vast hinterland, and companies such as COSCO, Orient Overseas Container Lines (OOCL), Sinotrans, American President Lines (APL), K-line, ZIM, Hanjin, and Nedlloyd now have offices in other YRD cities inland. Such dynamics are backed by efforts to better integrate the corridor, notably through the merging of port authorities 7 , the 1111111111111111111111111111111111111111111111111111111111 1 6 Since the opening of Donghai Bridge, truck traffic of containers has increased continuously from 1.5 million TEUs in 2006 to 3 million TEUs in 2008. Trucks transfer containers from the railway station of Luchao port which connects 14 cities (e.g. Hefei, Nanchang), but also from the YRD to overseas. In 2008, truck (hinterland) traffic accounted for about 3.23 million TEUs (39.3%) in Yangshan's total port traffic reaching 8.23 million TEUs. No congestion problems have been so far reported on the bridge. While container trucks do not pay the expensive bridge toll, it is not the case for other cargo trucks of passengers vehicles. 7 Taicang, Changshu, and Zhangjiagang were merged into one single Suzhou port authority in 2002.

purchasing of port infrastructure and stocks by carriers and terminal operators, the joint planning of bonded areas across the YRD (i.e. Yangshan, Waigaoqiao, Ningbo, Zhangjiagang, and Suzhou), and the redirection of local flows 8 .

[Insert Figure 9: Container traffic by truck over Donghai Bridge, 2006Bridge, -2009] ] At the East Asian level, although Shanghai's handling capacity in the early 2000s was comparable with other major hub ports, its transhipment function has remained secondary compared with traditional hub ports being Busan, Hong Kong, Kaohsiung, and Singapore.

Recent studies on East Asian and Northeast Asian liner shipping networks demonstrated the relatively limited centrality of Shanghai in 1996and 2006[START_REF] Ducruet | Centrality and vulnerability in liner shipping networks: Revisiting the Northeast Asian port hierarchy[END_REF] with regard to the domination of traditional hub ports and despite the rise of several other secondary ports such as Incheon, Port Klang, and Surabaya. Despite their impressive growth in traffic volumes, Chinese ports as a whole did not experiment equivalent centrality growth within East Asia, largely due to a late entry into the transshipment market. Indeed, Shanghai's transshipment ratio remained around 23.4% of total traffic in 2005, while the international transshipment ratio represented 2.2%: the latter reached 5.7% in 2009 although the 11th fiveyear plan predicted a level of 10%. International cargoes are thus generally transshipped via foreign hubs. For instance, about 40% of Busan's traffic is fed by transshipment with Chinese ports, which represents 2 million TEUs annually. Such evidence confirms that Shanghai's port development has so far been driven by hinterland-related dynamics rather than hub-related dynamics. It is thus too soon to predict whether or not Yangshan will take over the transshipment flows of traditional Asian hub ports. In terms of logistics performance however, Shanghai has already been seen as more competitive than Hong Kong and Kaohsiung in terms of cost, market, and industrial factors [START_REF] Lu | Comparison of investment preferences for international logistics zones in Kaohsiung, Hong Kong, and Shanghai ports from a Taiwanese manufacturer's perspective[END_REF]. The main question is thus about whether Yangshan itself may develop purely port/transport functions or additional port-related and urban functions.

The metropolitan dimension of port dynamics

1111111111111111111111111111111111111111111111111111111111 1 8 Yangshan and Luchao are planned to strengthen mutual traffic by attracting cargo from South Jiangsu (Suzhou, Wuxi, and Changzhou) and North Zhejiang (Huzhou, Jiaxing, and Hangzhou) through Sushen, Dalu, Hangshen lines and the Huangpu River. Pudong railway will extend northward to Waigaoqiao and will connect Beijing, Nantong, Zhenjiang, and Jiaxing through Shanghai. Yangpu station in the urban core will shift its traffics to Luchao in order to avoid congestion.

The evolution of the YRD port system in relation to Shanghai witnesses several deviations from the generic model presented in Figure 1 and used as a benchmark. While such differences were expected and can be largely attributed to the national factor of a rapid transition from a command economy to market-oriented economy, a more in-depth analysis of local factors remains necessary in order to fully understand the role of territorial and governance issues.

Firstly, recent logistics development in and around Shanghai must be understood bearing in mind wider functional and spatial shifts within metropolitan Shanghai. In 1986 and1992 Shanghai was designated by the State Council to become China's largest urban, economic, technological, trading, financial, information, culture, and maritime centre, a n o b j e c t i v e t h a t is reflected in s u b s e q u e n t rapid FDI growth since then [START_REF] Wei | Development zones, foreign investment, and global city formation in Shanghai[END_REF].

Several large-scale and complementary projects 9 were launched to achieve such objectives by which Shanghai's economy would shift from traditional industrial functions 10 to international higher-order economic functions. Yet, with about 9.1 million people residing in Shanghai's inner city nowadays and a very high urban density, lack of space and congestion issues became paramount, taking the form of land-use tensions between industrial, port, and service activities. Early planning measures since the 1980s had the effect of moving industries and related port terminals (e.g. coal, oil, and sand) from the Wusong estuary to the south coast of Yangtze River estuary, notably by constructing the first container berth in Waigaoqiao. Current measures have prolonged such shifts by supporting the attraction of modern service industries at the urban core, and high-tech industries between the two main ring roads, while moving heavy industries and manufacturing plants towards suburban industrial parks 11 .

1111111111111111111111111111111111111111111111111111111111 1 9 Pudong zone, Lujiazui Financial and Trade Zone, Waigaoqiao Bonded Area, Jinqiao Export Processing Zone, and Zhangjiang Hi-Tech Park. 10 In 1994, 18.1% of Shanghai's inner city built-up area was devoted to industrial uses (20% on the level of the metropolitan area), 8.6% to warehousing, and 3.4% to other private services. In the early 2000s Shanghai was still characterized by a strong dependence on manufacturing (50% of total employment, against 27% in Taipei, 22% in Singapore, 18% in Tokyo and 8% in Hong Kong) a low car ownership and a low density of roads but with higher carbon emissions than most large Asian cities except Bangkok, and the highest rate of respiratory diseases among large Asian cities. FDI between 1979 and 2000 remained dominated by manufacturing [START_REF] Wei | Development zones, foreign investment, and global city formation in Shanghai[END_REF]. 11 The urban core comprises the Huangpu and Nanshi districts for finance and trade, a second area between the two main ring roads includes Xuhui and Luwan districts for high-tech and culture, Jing`an, Changning, and Putuo districts for business, logistics and education, Zhabei, Hongkou, and Yangpu districts for technological and urban industry, and the third area outside the second ring road is made of Baoshan, Minxing, and Jiading districts ensuring industrial base activities, of Jinshan, Songjiang, Fengxian, Nanhui, Qingpu, and Chongming districts mainly focusing on agriculture, industry, and tourism, and 10 "new towns" (Baoshan, Jiading, Songjiang, Jinshan, Minxing, Qingpu, Nanqiao, Huinan and Chengqiao as well as Luchao port city).

Secondly, some of the new projects are both supporting and competing with Shanghai through attempts to exploit proximity within the global city (Figure 10). As recalled by Wei and Leung (2005, p.19), "in emerging global cities, such as in Shanghai, CBDs are usually weak, and often several emerging nodes compete with each other for preferential policies and foreign investment". Such trends directly reflect the ambitions of the 1999-2020 Masterplan launched by Shanghai Municipality that aims to de-concentrate the urban core through the establishment of new cities in other districts (see Figure 10). Luchao port city, situated at the southeast corner of Shanghai's urban area is planned as a new urban nucleus potentially rivaling central Shanghai in terms of global urban functions.

Luchao is planned as the administrative base of Yangshan port by providing comprehensive functions including container distribution and storage, offshore processing, shipping market, residential, financial and commercial services, amenity and tourism. Third, the Hulu Expressway is another crucial element which connects Donghai Bridge with the hinterland and bypasses the old urban core. Another important traffic line is Pudong railway, with a first phase completed in late 2005 connecting Luchao, Shanghai-Hangzhou, Shanghai-Beijing, and providing fast access to the national railway network. The Yanshan project thus had important impacts on the layout of transport networks, since traffic shifted gradually from Yangpu station (closer to Shanghai's CBD) to Luchao station, which possesses anannualhandlingcapacityof1.72millionTEUs.A significant issue in the urban context is the fact that Yangshan Island falls under the jurisdiction of the neighboring Zhejiang province. This has exacerbated tensions about local benefits. As underlined by Wang and Olivier (2003, p. 48), "never [in China] had a port authority built a container terminal situated outside its own boundaries". However, it was decided by the central government that while Yangshan port would belong to Zhejiang province, its management and administration would belong to Shanghai 12 . Nevertheless, Shengsi county (Zhejiang) plans to develop a new city on Yangshan island performing business, culture, leisure, tourism, and housing activities. Another issue concerned the role of Ningbo. This port would have been a suitable location for welcoming deep-sea terminals, with a water depth of about 18.2 m in Beilun 1111111111111111111111111111111111111111111111111111111111 1

12 Zhejiang province's early expectations levying taxes on Yangshan port operations confronted the fact that Shanghai Tongsheng Investment Co. Ltd (STI) registers in Shanghai. Yet, the Shengsi county, where Yangshan port locates, in Zhejiang province, is allowed to get a small share of taxes. Such tensions fostered Zhejiang province's investments on Ningbo port to compete with Shanghai and Yangshan ports. In addition, Shengsi county uses Yangshan port as a tool for competing with nearby Luchao harbor city through the attraction of large companies (Australia, Germany, Japan, and also Shanghai) for designing Yangshan new city with a capacity of 50 to 60,000 residents.

harbor, the Chinese government preferred locating new investments nearer to Shanghai as a means consolidating Shanghai's international shipping center. Thirdly, Yangshan was planned by the Chinese government as a value-added and integrated industrial, logistics, and shipping complex rather than a sole transhipment node. The Yangshan Bonded Port Area (YBPA) 13 is a multimodal logistics centre for transhipment, distribution, insurance, finance, and entrepôt trade. This facility is designed to provide a local manufacturing base limiting truck and shipping flows to and from mainland China i n a d d i t i o n t o i t s f i r s t t r a n s h i p m e n t f u n c t i o n . Up to 2008, 63 foreign companies have registered in this area, including third party logistics (e.g. Maersk, CTW, ProLogis, DSV A/S, BoConcept A/S),storage, manufacturers (e.g. non-ferrous metals, electronics, automobile parts) 14 , and carriers (e.g. Sinotrans, COSCO, Maersk). The total gross value of the bonded supervised goods in Yangshan reaches a total of US$ 4.23 billion. Domestic cargoes fall under the same customs, tax, and currency exchange procedures than foreign goods. Registered companies are exempted from business taxes if they engage in shipping, transportation, loading and unloading, and storage. A cooperation across the YRD makes it possible for registered companies to declare at any of the 69 customs offices in mainland China. Crude oil and liquefied natural gas terminals are also being built.

[Insert Figure 10: Location of map of Shanghai, Yangshan and Ningbo]

The Shanghai-Yangshan dual hub in fact fully participates to the building of a global city, a process in which the reorganization of physical infrastructure and flows is a major factor. Such strategy even takes the form of a "multimodal tri-hub" including seaport, airport, and many centers (i.e. trade, financial, technical, information, tourism, and industrial) such as Lujiazui in Pudong, Waitan in Puxi (finance), and Zhangjiang (high-tech). Shanghai itself hosts the headquarters of China's three largest carriers (COSCO, CSCL, Sinotrans Shipping) and of 20 global shipping lines, 66 international carriers, 630 ship agencies, and 350 international freight forwarders. Luchao port city provides not only shipping-related services but also urban functions (i.e. residence, leisure, education and training) as well as industrial functions (equipment manufacturing industry, industrial park, export processing), thus becoming a new growth pole in Shanghai.

Conclusion

The current transformation of Shanghai into a global city is in many ways similar to other development paths occurring in other large Asian port cities. However, Shanghai remains unique with regard to the crucial importance of the Yangtze River Delta (YRD) that developed since the 1970s as a corridor and gateway connecting China with the rest of the world, thereby conferring Shanghai specific logistics and multimodal functions for hinterland control. While those maritime and logistics functions fully influence the formation of a global city, they also exhibit particular trends and contribute to reinforce Shanghai's specialization in certain economic sectors. A large portion of urban space is devoted to physical infrastructure of which port terminals and related industrial and service activities ensuring cargo transfers.

These have been accommodated within a broader metropolitan region; elsewhere the lack of space and fierce competition among East Asian ports fostered the expansion of facilities beyond the urban core, thus creating tensions among local authorities. Although the evolution of the YRD port system matches, overall, general models of port system evolution, significant deviations are observed.

First, the distribution of container flows among YRD ports was already strongly concentrated upon Shanghai in the early phases, while the regionalization phase has started earlier than in the generic model. This can be attributed to three complementary factors: a specific context where the diffusion of containerization has been more selective during the transition from command to market economy, a crucial importance of river shipping facilitating rapid hinterland penetration in contrast to limited road and rail infrastructure over long distances, and a rather aggressive strategy of hinterland control by Shanghai port m a n a g e m e n t b y securing inland terminals for feeder traffic and centralizing decision over freight distribution patterns. Second, strong support from the central government to Shanghai's globalization favored Yangshan new port rather than existing neighboring ports (i.e. Ningbo) for infrastructure expansion and offshore hub development. This strong role of the central government has minimized some potential tensions arising from rent-seeking attempts by adjacent local authorities to levy benefits from Yangshan's development. The maintenance of the dominance of domestic players also stands in contrast with the literature on other Asian peripheral ports where global foreign players have stimulated the emergence of offshore hubs (Slack and Wang,2002). Third, the Shanghai-Yangshan dual hub port exhibits important differences with generic models due to the development of activities other than sole transshipment, notably in the manufacturing and tertiary sectors, and to the connection of the new port with the hinterland through logistics regionalization.

The case of the Shanghai-Yangshan dual hub port thus contributes revisiting existing literatures about global ports and global cities while providing new insights about the urbanport trajectories of maritime cities in Asia and the rest of the world. The first contribution is the confirmation that the evolution of port, transport, and logistics activities not only illustrates but directly contributes to the evolution of cities and urban systems. This infers that Shanghai's rapid globalization would not have been possible without a gradual improvement of its capacity to move cargo locally and across the Yangtze corridor, as its economic base remains specialized in transport and manufacturing functions. Such an outcome stands in contrast with a general belief that large global cities would (and should) get rid of their physical functions in order to realize a successful transformation into higher-valued, more knowledge-based activities associated with a role as a global command and control centre.

The second contribution is that conversely, deviations from general models of port system

%#!!!! !!!!! #!!!! *!!!!! *#!!!! (!!!!! ! ! ' F ! % ! ! ' F ! ! ! ' F ! * ! ! ' F ! ( ! ! ' F ! # ! ! ' F ! ' ! ! ' F ! $ ! ! ' F ! 6 ! ! ' F ! 7 ! ! ' F % ! ! ! ' F % % ! ! ' F % ! ! $ F ! % ! ! $ F ! ! ! $ F ! * ! ! $ F ! ( ! ! $ F ! # ! ! $ F ! ' ! ! $ F ! $ ! ! $ F ! 6 ! ! $ F ! 7 ! ! $ F % ! 1 ! ! $ F % % ! ! $ F % ! ! 6 F ! % ! ! 6 F ! ! ! 6 F ! * ! ! 6 F ! ( ! ! 6 F ! # ! ! 6 F ! ' ! ! 6 F ! $ ! ! 6 F ! 6 ! ! 6 F ! 7 ! ! 6 F % ! 1 ! ! 6 F % % ! ! 6 F % ! ! 7 F ! % ! ! 7 F ! ! ! 7 F ! * ! ! 7 F ! (

  ). Coastal container shipping extended firstly from Shanghai to Dalian in 1972, and further extended to Nantong port. Subsequently, Shanghai launched another experimental shipping of twenty-foot containers through foreign bulk cargo ships to US ports in 1974. Between 1973 and 1975, China as a whole realized 89 shipments totalling 2,499 containers in such fashion. However, all these experiments remained under Chinese container technology standards.

  acquired a leading role through constructing numerous terminals along the Huangpu River (i.e. Zhanghuabang, Jungonglu, Gongqing, Zhujiamen, and Longwu) and the south bank of Yangtze River (i.e. Baoshan, Luojing, and Waigaoqiao) providing the infrastructure to tranship containers along the emerging Yangtze corridor. Such feeder traffic with Shanghai represented about 20% of Nantong and Zhenjiang's total traffic in 1995, and 10% of Zhangjiagang and Nanjing's total traffic. New land-based transport systems connecting major seaports developed as well, such as the Shanghai-Nanjing and Shanghai-Hangzhou expressways, in order to improve hinterland accessibility. The destinations of international shipping expanded to include Hong Kong, Japan, North American ports and Australia. This period witnessed certain similarities with the model as earliest adopters of containerization concentrated most traffic and became t h e dominant ports. As suggested by Figure 4, traffic concentration levels have been irregular from the early 1980s to the mid-1990s, suggesting the spread of container technology outside Shanghai. [Insert Figure 3: Container traffic evolution, 1979-2010]

  expansion occurred much earlier compared with the sixth phase of Taaffe et al. (1963)'s model labelled the emergence of high-priority main streets. [Insert Figure 4: Number of container ports and traffic concentration] [Insert Figure 5:

  Constructed since 2002 and starting its operations in 2005, Yangshan is located on the eponym island at the junction between Yangtze River shipping and maritime shipping, with a shoreline of about 20 km and a water depth of over 15 m. A total of 50 deep-water berths can accommodate vessels of 8,000 TEUs and over. Besides such technical capabilities, Yangshan is connected to mainland by truck through the Donghai Bridge or by other ports through shipping and railway 2 . In China, central and local governments traditionally hold high control over the port industry. The main developer of Yangshan port, Shanghai Tongsheng Investment Co. Ltd (STI), is jointly owned by three main players, namely Shanghai International Group Co. Ltd (SIG), Shanghai Port Administration Bureau (SPAB), and Shanghai State-owned Assets Operation Co 3 (see Figure 6). The first phase of the project was largely supported by the central government and was completed by Shanghai firms such as Shanghai Port Building Group. In June 2002, STI was offered 7.5 billion Yuan in loans for the first-phase construction by one consortium of five domestic banks and five other lending institutions.

  By promulgating a document called Provisions on Guiding Foreign Investment Direction in 2002, the central government allowed foreign investors to establish joint ventures with domestic firms and even to reach a majority share. China's agreement with the World Trade Organization allows foreign investors to own a maximum of 75% share in port construction projects. Overseas shipping giants such as Maersk, China Ocean Shipping (Group) Company (COSCO), Orient Overseas Container Line (OOCL) as well as global terminal operators such as APM Terminals, Hutchinson Whampoa, and PSA Singapore Terminals directly expressed their interest in the second phase of the project. The second phase was completed jointly by Hutchison Whampoa, Maersk, COSCO, China Shipping Container Lines (CSCL), and Shanghai International Port Group (SIPG). The currently ongoing third phase already attracted many investors such as Maersk, Hutchison Whampoa, APM, and Dubai Ports

a

  growing share of foreign (global) players. Yet, part B of the third phase depends entirely upon the investment from Shanghai Guangdong International Container Terminal Co., which is also owned by SIPG. In parallel, there is a reinforcement of the SIPG during the completion of the project, as the group acquired progressively several other companies responsible for the construction of Donghai Bridge (Shanghai Tongsheng Bridge Construction Co. Ltd in 2002), the Yangshan bonded area (Shanghai Tongsheng Logistics Park Investment and Development Co. in 2002), and Yangshan port first two phases (Shanghai Shengdong International Container Terminal Co. Ltd in 2005).After six years of feasibility studies, the project of Yangshan port and Donghai Bridge was approved by China's State Council, and was planned to be constructed over three phases (see Table1). The first phase started in 2002 and was completed in 2005, comprising port terminals on Yangshan Island, the Donghai Bridge 4 , the Hulu Expressway, and supporting infrastructures in Luchao city. This phase covers a port area of about 1.53 square km equipped with five container berths, totaling 1,600 m of quays and a storage yard of 720,000 square meters. The water depth of berths reaches 15.5 m to accommodate the fifth and sixth generation vessels, with an annual handling capacity of 2.2 million TEUs. The second phase started in 2006 added 4 deep-water berths and another 2.1 million TEUs capacity. At present the two first phases are completed with nine berths totaling 3 km of quay length. The third phase is planned to add seven berths and 4.7 million TEUs capacity, while according to the master plan the whole project shall be fully completed by 2020, with about 30 deep-water berths having a total handling capacity of 15 million TEUs.

Figure 8 ,

 8 Figure 8, Shanghai's traffic decreased in recent years from 20.04 million TEUs in 2007 to 18 million TEUs in 2010. The global financial crisis had direct impacts on the level of shipping activities as it even decreased to 16.5 million TEUs in 2009. As Yangshan's traffic continues to grow and reached about 10 million TEUs in 2010, the combined traffic of Shanghai and Yangshan overtook Hong Kong as the world's second biggest container port. Yangshan's market share in the YRD steadily increased from 13.8% (2006) to 34% (2009) and 35.7% (2010), while Shanghai's market share comparatively diminished from 86.2% (2006) to 64.3% (2010). Shanghai's relative decline is also attributed to Ningbo's rapid growth into a deepwater port since the 1990s as discussed previously (see Figure 9). Traffic shifts from Shanghai to Ningbo contribute to narrow the gap from 13 to 5 million TEUs between 2005 and 2010.

  Nowadays about 13 shuttle vessels and 4-5 daily schedules are provided between Yangshan and Waigaoqiao. The Taicang-Yangshan service is operated with 250 TEU vessels since 2005, while the Nanjing-Yangshan and Nantong-Yangshan services operated by Mitsui O.S.K. Lines and Sinotrans were launched in 2006 with 17 and 4 weekly schedules respectively. From May 2006 a direct river shipping service from Wuhan operated by COSCO shifted destination from Waigaoqiao to Yangshan. Such nonstop services were officially systematized in 2008 with the Navigation Technological Conditions for Specific Routes issuing special permit to vessels passing through the Yangtze River Estuary towards Yangshan. With the development of logistics networks and deep-water ports, the YRD has experienced a continuation of the port regionalization phase. Several cities in the YRD have built new logistics facilities as seen in numerous logistics parks in Shanghai (8), Suzhou (10), and Nanjing (4) as well as in Changzhou and Wuxi. Dedicated rail services have been established

  approved by the State Council in 2005 as China's first bonded port following the Reply of the State Council on Approval of Establishing Yangshan Bonded Harbor District and Directory of Industrial Development and Investing Policies in Yangshan Bonded Zone. It covers 8.14 square kilometers including an export processing area, a bonded area, and the port area itself, providing storage and supervision of import and export cargo, processing of imported raw materials and semi-finished goods as well as reprocessing, assembling and exporting components.14 Yangshan was notably selected by large companies such as Alcatel-Lucent (Asia-Pacific integrated logistics centre), Ericsson and Pioneer (processing and distribution base), WSP Italy and Chrysler (automobile storage and logistics centre), Zhongchu Development Stock Co. and GKE (metals).

  evolution were mostly caused by the specific local urban and political context. Efforts to transform Shanghai into a global city gave precedence to certain areas that pure physical and economic factors may not have predicted. Rather than the shift of modern terminals towards the already established and well accessible port of Ningbo, preference was given to Yangshan island, in closer proximity to Shanghai, notwithstanding additional costs required in bridge connection. Hence ideal-typical sequences of port system development cannot fully explain the Shanghai-Yangshan case without the inclusion of urban factors. Maintaining new port development within Shanghai's close proximity despite inherent costs and administrative tensions thus translated the will to create a polycentric yet more compact multifunctional and multilayered gateway centered upon Shanghai. The decisive role of the central government in such processes adds to the originality of the Shanghai-Yangshan case compared with other examples of new port development in Asia.

Zhanghuabing terminal and the Huangpu River were limited by a water depth of 7-8 m thus not allowing the entrance of vessels beyond 1,400 TEUs capacity.

Donghai Bridge is

32.5 km in length and 31.5 meters in width with six traffic lanes two-way. The annual navigable capacity under the bridge is over 5 million TEUs.

The stock share of Shanghai Tongsheng Investment Co. (created in 2002) is owned by three main players, namely Shanghai International Group Co. (52%), Shanghai Port Administration Bureau (40%), and Shanghai State-owned Assets Operation Co. (8%).

Constructed by Shanghai Tongsheng Bridge Construction Co. Ltd, acquired by Shanghai International Port Group CO. Ltd in 2002.

Acknowledgements

This research was supported by the Natural Science Foundation of China (Project no. 41171108).