Éric Fusy
email: eric.fusy@univ-eiffel.fr

Gregory Kucherov
email: gregory.kucherov@univ-eiffel.fr

Phase transition in count approximation by Count-Min sketch with conservative updates

Count-Min sketch is a hashing-based data structure to represent a dynamically changing associative array of counters. Wse analyse the counting version of Count-Min under a stronger update rule known as conservative update, assuming the uniform distribution of input keys. We show that the accuracy of conservative update strategy undergoes a phase transition, depending on the number of distinct keys in the input as a fraction of the size of the Count-Min array. We prove that below the threshold, the relative error is asymptotically o(1) (as opposed to the regular Count-Min strategy), whereas above the threshold, the relative error is Θ(1). The threshold corresponds to the peelability threshold of random k-uniform hypergraphs. We demonstrate that even for small number of keys, peelability of the underlying hypergraph is a crucial property to ensure the o(1) error. To our knowledge, this relationship has not been observed previously. Finally, we provide experimental data on the behavior of the average error for Zipf's distribution compared with the uniform one.

Introduction

Count-Min sketch is a hash-based data structure to represent a dynamically changing associative array a of counters in an approximate way. The array a can be seen as a mapping from some set K of keys to N, where K is drawn from a (large) universe U . The goal is to support point queries about the (approximate) current value of a(p) for a key p. Count-Min is especially suitable for the streaming framework, when counters associated to keys are updated dynamically. That is, updates are (key,value) pairs (p, ) with the meaning that a(p) is updated to a(p) + .

Count-Min sketch was proposed in [START_REF] Cormode | An improved data stream summary: the countmin sketch and its applications[END_REF], see e.g. [START_REF] Cormode | Count-min sketch[END_REF] for a survey. A similar data structure was introduced earlier in [START_REF] Cohen | Spectral Bloom filters[END_REF] named Spectral Bloom filter, itself closely related to Counting Bloom filters [START_REF] Fan | Summary cache: a scalable wide-area web cache sharing protocol[END_REF]. The difference between Count-Min sketch and Spectral Bloom filter is marginal: while a Count-Min sketch requires hash functions to have disjoint codomains (rows of Count-Min matrix), a Spectral Bloom filter has all hash functions mapping to the same array. This difference is the same as between partitioned [START_REF] Almeida | A case for partitioned Bloom filters[END_REF] and regular Bloom filters. In this paper, we will deal with the Spectral Bloom filter version but will keep the term Count-Min sketch as more common in the literature.

Count-Min sketch supports negative update values provided that at each moment, each counter a(p) remains non-negative (so-called strict turnstile model [START_REF] Liu | Methods for mining frequent items in data streams: an overview[END_REF]). When updates are positive, the Count-Min update algorithm can be modified to a stronger version leading to smaller errors in queries. This modification, introduced in [START_REF] Estan | New directions in traffic measurement and accounting[END_REF] as conservative update, is mentioned in [START_REF] Cormode | Count-min sketch[END_REF], without any formal analysis given in those papers. This variant is also discussed in [START_REF] Cohen | Spectral Bloom filters[END_REF] under the name minimal increase, where it is claimed that it decreases the probability of a positive error by a factor of the number of hash functions, but no proof is given. We discuss this claim in the concluding part of this paper.

The case of positive updates is widespread in practice. In particular, a very common instance is counting where all update values are 1. This task occurs in different scenarios in network traffic monitoring, as well as other applications related to data stream mining [START_REF] Estan | New directions in traffic measurement and accounting[END_REF]. In bioinformatics, we may want to maintain, on the fly, multiplicities of fixed-length words occurring in a big sequence dataset [START_REF] Mohamadi | ntCard: a streaming algorithm for cardinality estimation in genomics data[END_REF][START_REF] Behera | Kmerestimate: A streaming algorithm for estimating k-mer counts with optimal space usage[END_REF][START_REF] Shibuya | Set-Min sketch: a probabilistic map for power-law distributions with application to k-mer annotation[END_REF]. We refer to [START_REF] Einziger | A formal analysis of conservative update based approximate counting[END_REF] for more examples of applications.

While it is easily seen that the error in conservative update can only be smaller than in Count-Min, obtaining more precise bounds is a challenging problem. Count-Min guarantees, with high probability, that the additive error can be bounded by ε a 1 for any ε, where a 1 is the L1-norm of a [START_REF] Cormode | An improved data stream summary: the countmin sketch and its applications[END_REF]. In the counting setting, a 1 is the length of the input stream which can be very large, and therefore this bound provides a weak guarantee in practice, unless the distribution of keys is very skewed and queries are made on frequent keys (heavy hitters) [START_REF] Liu | Methods for mining frequent items in data streams: an overview[END_REF][START_REF] Charikar | Finding frequent items in data streams[END_REF][START_REF] Cormode | Finding frequent items in data streams[END_REF]. It is therefore an important practical question to analyse the improvement provided by the conservative update strategy compared to the original Count-Min sketch.

To our knowledge, the first attempt towards this goal was made in [START_REF] Bianchi | Modeling conservative updates in multi-hash approximate count sketches[END_REF], under assumption that all n k counter combinations are equally likely at each step (n size of the Count-Min array, k number of hash functions) which amounts to assuming uniform distribution on n k input keys, each hashed to a distinct combination of counters. Thus, the number of distinct keys in the input is assumed to be much larger than the sketch size n. It was observed that the behavior of this model with uniformly distributed keys has important implications to nonuniformly distributed input. Another approach to bounding the error proposed in [START_REF] Einziger | A formal analysis of conservative update based approximate counting[END_REF] is based on a simulation of spectral Bloom filters by a hierarchy of ordinary Bloom filters. However, the bounds provided are not explicit but are expressed via a recursive relation based on false positive rates of involved Bloom filters. Recent works [START_REF] Ben Mazziane | A formal analysis of the count-min sketch with conservative updates[END_REF][START_REF] Ben Mazziane | Analyzing count min sketch with conservative updates[END_REF] propose formulas for computing error bounds depending on key probabilities assumed independent but not necessarily uniform, in particular leading to an improved precision bounds for detecting heavy hitters.

In this paper, we provide a probabilistic analysis of the conservative update scheme for counting under the assumption of uniform distribution of keys in the input. Our main result is a demonstration that the error in count estimates undergoes a phase transition when the number of distinct keys grows relative to the size of the Count-Min array. We show that the phase transition threshold corresponds to the peelability threshold for random k-uniform hypergraphs. For the subcritical regime, when the number of distinct keys is below the threshold, we show that the relative error for a randomly chosen key tends to 0 asymptotically, with high probability. This contrasts with the regular Count-Min algorithm producing a relative error shown to be at least 1 with constant probability.

For the supercritical regime, we show that the average relative error is lowerbounded by a constant (depending on the number of distinct keys), with high probability. We prove this result for k = 2 and conjecture that it holds for arbitrary k as well. We provide computer simulations showing the growth of the expected relative error after the threshold, with a distribution showing a peculiar multi-modal shape. In particular, keys with small (or zero) error still occur after the threshold, but their fraction quickly decreases when the number of distinct keys grows.

After defining Count-Min sketch and conservative update strategy in Section 2 and introducing hash hypergraphs in Section 3, we formulate the conservative update algorithm (or regular Count-Min, for that matter) in terms of a hypergraph augmented with counters associated to vertices. In Section 4, we state our main results and illustrate them with a series of computer simulations. In Section 5 we outline the proof of our main result for the subcritical regime and provide a proof for the supercritical regime.

In addition, in Section 6, we study a specific family of 2-regular k-hypergraphs that are sparse but not peelable. For such graphs we show that while the relative error of every key is 1 with the regular Count-Min strategy, it is 1/k + o(1) for conservative update. While this result is mainly of theoretical interest, it illustrates that the peelability property is crucial for the error to be asymptotically vanishing. Finally, in Section 7, we turn to non-uniform distributions and provide a brief experimental analysis of the behavior of the average error for Zipf's distribution compared with the uniform one. Missing full proofs and additional experimental data can be found in [START_REF] Fusy | Phase transition in count approximation by Count-Min sketch with conservative updates[END_REF].

Count-Min and Conservative Update

We consider a (counting version of) Count-Min sketch to be an array A of size n of counters initially set to 0, together with hash functions h 1 , . . . , h k mapping keys from a given universe to [1..n]. To count key occurrences in a stream of keys, regular Count-Min proceeds as follows. To process a key p, each of the counters A[h i (p)], 1 ≤ i ≤ k, is incremented by 1. Querying the occurrence number a(p) of a key p returns the estimate âCM (p) = min 1≤i≤k {A[h i (p)]}. It is easily seen that âCM (p) ≥ a(p). A bound on the overestimate of a(p) is given by the following result adapted from [START_REF] Cormode | An improved data stream summary: the countmin sketch and its applications[END_REF].

Theorem 1 ([13]). For ε > 0, δ > 0, consider a Count-Min sketch with k = ln( 1 δ ) and size n = k e ε . Then âCM (p) -a(p) ≤ εN with probability at least 1 -δ, where N is the size of the input stream.

While Theorem 1 is useful in some situations, it has a limited utility as it bounds the error with respect to the stream size which can be very large.

Conservative update strengthens Count-Min by increasing only the smallest counters among

A[h i (p)]. Formally, for 1 ≤ i ≤ k, A[h i (p)] is incremented by 1 if and only if A[h i (p)] = min 1≤j≤k {A[h j (p)]
} and is left unchanged otherwise. The estimate of a(p), denoted âCU (p), is computed as before: âCU (p) = min 1≤i≤k {A[h i (p)]}. It can be seen that âCU (p) ≥ a(p) still holds, and that âCU (p) ≤ âCM (p). The latter follows from the observation that on the same input, an entry of counter array A under conservative update can never get larger than the same entry under Count-Min.

Hash hypergraphs and CU process

With a counter array A[1.

.n] and hash functions h 1 , ..., h k we associate a kuniform hash hypergraph H = (V, E) with vertex-set V = {1, ..., n} and edge-set E = {{h 1 (p), ..., h k (p)}} for all distinct keys p. Let H k n,m be the set of k-uniform hypergraphs with n vertices and m edges. We assume that the hash hypergraph is a uniformly random Erdős-Rényi hypergraph in H k n,m , which we denote by

H k n,m
, where m is the number of distinct keys in the input (for k = 2, we use the notation G n,m = H 2 n,m ). Even if this property is not granted by hash functions used in practice, it is a reasonable and commonly used hypothesis to conduct the analysis of sketch algorithms.

Below we show that the behavior of a sketching scheme depends on the properties of the associated hash hypergraph. It is well-known that depending on the m/n ratio, many properties of Erdős-Rényi (hyper)graphs follow a phase transition phenomenon [START_REF] Frieze | Introduction to Random Graphs[END_REF]. For example, the emergence of a giant component, of size O(n), occurs with high probability (hereafter, w.h.p.) at the threshold [START_REF] Karoński | The phase transition in a random hypergraph[END_REF]. Particularly relevant to us is the peelability property. Let H = (V, E) be a hypergraph. The peeling process on H is as follows. We define H 0 = H, and iteratively for i ≥ 0, we define V i to be the set of leaves (vertices of degree 1) or isolated vertices in H i , E i to be the set of edges of H i incident to vertices in V i , and H i+1 to be the hypergraph obtained from H i by deleting the vertices of V i and the edges of E i . A vertex in V i is said to have peeling level i. The process stabilizes from some step I, and the hypergraph H I is called the core of H, which is the largest induced sub-hypergraph whose vertices all have degree at least 2. If H I is empty, then H is called peelable.

m n = 1 k(k-1)
It is known [START_REF] Molloy | Cores in random hypergraphs and boolean formulas[END_REF] that peelability undergoes a phase transition. For k ≥ 3, there exists a positive constant λ k such that, for λ < λ k , the random hypergraph H k n,λn is w.h.p. peelable as n → ∞, while for λ > λ k , the core of H k n,λn has w.h.p. a size concentrated around αn for some α > 0 that depends on λ. The first peelability thresholds are λ 3 ≈ 0.818, λ 4 ≈ 0.772, etc., λ 3 being the largest.

For k = 2, for λ < 1/2, w.h.p. a proportion 1 -o(1) of vertices are in trees of size O(1), (and a proportion o(1) of the vertices are in the core), while for λ > 1/2, the core size is w.h.p. concentrated around αn for α > 0 that depends on λ [START_REF] Pittel | Counting connected graphs inside-out[END_REF].

We note that properties of hash hypergraphs determine the behavior of some other hash-based data structures, such as Cuckoo hash tables [START_REF] Pagh | Cuckoo hashing[END_REF] and Cuckoo filters [START_REF] Fan | Cuckoo filter: Practically better than bloom[END_REF], Minimal Perfect Hash Functions and Static Functions [START_REF] Majewski | A family of perfect hashing methods[END_REF], Invertible Bloom filters [START_REF] Goodrich | Invertible Bloom lookup tables[END_REF], and others. We refer to [START_REF] Walzer | Random hypergraphs for hashing-based data structures[END_REF] for an extended study of relationships between properties of hash hypergraphs and some of those data structures. In particular, peelability is directly relevant to certain constructions of Minimal Perfect Hash Functions as well as to good functioning of Invertible Bloom filters. However, its relation to Count-Min sketches is less direct and has not been observed earlier.

The connection to hash hypergraphs allows us to reformulate the Count-Min algorithm with conservative updates as a process, which we call CU-process, on a random hypergraph H k n,m , where n, m, k correspond to counter array length, number of distinct keys, and number of hash functions, respectively. Let H = (V, E) be a hypergraph. To each vertex v we associate a counter c v initially set to 0. At each step t ≥ 1, a CU-process on H chooses an edge e = {v 1 , . . . , v k } ∈ E in H, and increments by 1 those c vi which verify c vi = min 1≤j≤k c vj . For t ≥ 0 and v ∈ V , c v (t) will denote the value of the counter c v after t steps, and o e (t) the number of times edge e ∈ E has been drawn in the first t steps. The counter c e (t) of an edge e = {v 1 , . . . , v k } is defined as c e (t) = min 1≤i≤k c vi (t). Clearly, for each t and each e, o e (t) ≤ c e (t). The relative error of e at time t is defined as R e (t) = ce(t)-oe(t) oe(t)

. The following lemma can be easily proved by induction on t.

Lemma 1. Let H = (V, E) be a hypergraph on which a CU-process is run. At every step t, for each vertex v, there is at least one edge e incident to v such that c e (t) = c v (t).

Observe that, when H is a graph (k = 2), Lemma 1 is equivalent to the property that vertex counters cannot have a strict local maximum, i.e., at every step t, each vertex v has at least one neighbour u such that c u (t) ≥ c v (t).

4 Phase transition of the relative error

Main results

Let

H = (V, E) be a hypergraph, |V | = n, |E| = m. Let N ≥ 1.
We consider two closely related models of input to perform the CU-process. In the N -uniform model, the CU process is performed on a random sequence of keys (edges in E) of length N • m, each key being drawn independently and uniformly in E. In the N -balanced model, the CU-process is performed on a random sequence of length N • m, such that each e ∈ E occurs exactly N times, and the order of keys is random. In other words, the input sequence of keys is a random permutation of the multiset made of N copies of each key of E. Clearly, both models are very close, since the number of occurrences of any key in the N -uniform model is concentrated around N (with Gaussian fluctuations of order √ N ) as N gets large. For both models, we use the notation c deg(v k )) -1, and is thus always a non-negative integer. For fixed k ≥ 2 and λ > 0, and for a random edge e in H k n,λn , the probability that all k vertices belonging to e have at least one incident edge apart from e converges to a positive constant c(λ, k) = (1 -e -kλ ) k . Therefore, Re is a nonnegative integer whose probability to be non-zero converges to c(λ, k). Thus, Theorem 2 ensures that, for λ < λ k , conservative updates lead to a drastic decrease of the error, from Θ(1) to o(1).

(N ) v = c v (N m) for the resulting counter of v ∈ V , o
For a given hypergraph H = (V, E) with m edges, we define err

N (H) = 1 m e∈E R (N ) e
the average error over the edges of H. Formally, Theorem 2 does not imply that err N (H) is o(1), as it might possibly happen that a small fraction of edges have very large errors, yielding err N (H) larger than o(1). However, we believe that this is not the case. From the previous remark, it follows that the error of an edge e = (v 1 , . . . , v k ) is upper-bounded by min(deg(v 1 ), . . . , deg(v k )) -1. Since the expected maximal degree in H k n,λn grows very slowly with n, one can expect that any set of o(n) edges should have a contribution o(1) w.h.p.. This is also supported by experiments given in the next section.

Based on Theorem 2 and the above discussion, we propound that a phase transition occurs for the average error, in the sense that it is o(1) in the subcritical regime λ < λ k , and Θ(1) in the supercritical regime λ > λ k , w.h.p.. Regarding the supercritical regime, we are able to show that this indeed holds for k = 2 in the N -balanced model.

Theorem 3 (supercritical regime, case k = 2). Let λ > 1/2. Then there exists a positive constant f (λ) such that, in the N -balanced model, err N (G n,λn ) ≥ f (λ) w.h.p., as n grows 2 .

Our proof of Theorem 3 extends to k ≥ 3 for λ > λ k , where λ k is the threshold beyond which the giant component of H k n,λn has w.h.p. more edges than vertices.

1 Formally, for any > 0, there exists M such that P(R

(N ) e ≤ ) ≥ 1 -if n ≥ M and N ≥ M .
2 Formally, for any > 0, there exists M such that P(errN

(Gn,m) ≥ f (λ)) ≥ 1 -if N ≥ 1 and n ≥ M .
The analysis given in [START_REF] Behrisch | Local limit theorems for the giant component of random hypergraphs[END_REF] ensures that λ k exists and is explicitly computable, λ 3 ≈ 0.94, λ 4 ≈ 0.98. We believe however that the peelability threshold λ k constitutes the right critical value in Theorem 3 for k ≥ 3 as well, which is supported by simulations presented below. Proving this would require a different kind of argument than we use in our proof though.

Simulations

Here we provide several experimental results illustrating the phase transition stated in Theorems 2 and 3. Figure 1 The phase transitions are clearly seen to correspond to the critical threshold 0.5 for k = 2, and, for k ∈ {3, 4}, to the peelability thresholds λ 3 ≈ 0.818, λ 4 ≈ 0.772. Observe that the transition looks sharper for k ≥ 3, which may be explained by the fact that the core size undergoes a discontinuous phase transition for k ≥ 3, as shown in [START_REF] Molloy | Cores in random hypergraphs and boolean formulas[END_REF] (e.g. for k = 3, the fraction of vertices in the core jumps from 0 to about 0.13).

For the supercritical regime, we experimentally studied the empirical distribution of individual relative errors, which turns out to have an interesting multimodal shape for intermediate values of λ. Typical distributions for k ∈ {2, 3} are illustrated in Figure 2 where each point corresponds to an edge, and the edges are randomly ordered along the x-axis. Each plot corresponds to an individual random graph.

When λ grows beyond the peelability threshold, a fraction of edges with small errors still remains but vanishes quickly: these include edges incident to at least one leaf (these have error 0) and peelable edges (these have error o(1)), as follows from our proof of Theorem 2. For intermediate values of λ, the distribution presents several modes: besides the main mode (largest concentration on plots of Figure 2), we observe a few other concentration values which are typically integers. While this phenomenon is still to be analysed, we explain it by the presence of certain structural graph motifs that involve disparities in node degrees. Note that the fraction of values concentrated around the main mode is dominant: for example, for k = 3, λ = 3 (Figure 2d), about 90% of values correspond to the main mode (≈ 3.22). Finally, when λ becomes larger, these "secondary modes" disappear, and the distribution becomes concentrated around a single value. More data about concentration is given in the full version [START_REF] Fusy | Phase transition in count approximation by Count-Min sketch with conservative updates[END_REF]. Our analysis suggests that a positive average error in the supercritical regime is due to a large core -a non-peelable subgraph with Θ(n) nodes -which exists in this regime. To test this claim (for k = 3), we simulated the CU-process on sparse random non-peelable 3-hypergraphs, namely 2-regular 3-hypergraphs with 2n edges and 3n vertices (n parameter). These are sparsest possible nonpeelable 3-hypergraphs, with degree 2 of each vertex. In a separate experiment, we observed that the average error for such graphs is concentrated around a constant value of ≈ 0.217. While these graphs fall to the subcritical regime (λ = 2/3 < λ 3 ≈ 0.818), they still generate an average error bounded away from 0. Along with our results of Section 6, this supports that peelability is crucial for the error to be o(1), and the presence of large non-peelable subgraphs results in a Θ(1) error.

(a) k = 2, λ = 1 (b) k = 3, λ = 1 (c) k = 2, λ = 3 (d) k = 3, λ = 3 (e) k = 2, λ = 5 (f) k = 3, λ = 5

Proofs of the main results

Sketch of proof of Theorem 2

Here we only provide main steps to show Theorem 2, the full proof is given in [START_REF] Fusy | Phase transition in count approximation by Count-Min sketch with conservative updates[END_REF]. Theorem 2 relies on properties of random hypergraphs.

Case k = 2 corresponds to Erdős-Rényi random graphs G n,λn [START_REF] Erdos | On the evolution of random graphs[END_REF] which have been extensively studied [START_REF] Frieze | Introduction to Random Graphs[END_REF]. In particular, it is well known that when λ < 1/2 and n gets large, G n,λn is, w.h.p., a union of small connected components most of which are constant-size trees. That is, a random edge in G n,λn is, w.h.p., in a tree of size O(1). Thus, the proof amounts to showing that, for a fixed tree T and an edge e ∈ T , we have w.h.p. R The proof is done by induction on the peeling level i of v. If i = 0, then v is a leaf. Letting e be its incident edge, we have c

(N ) v = o (N )
e , hence w.h.p. c (N ) v /N = 1 + o(1). To let the induction work for i ≥ 1, we actually have to carry a stronger property. Namely, we show that for each v ∈ T , there exist absolute positive constants a v , b v such that, for any N ≥ 1 and x > 0, we have

P max t∈[0..N m] |c v (t) -t/m| ≥ x √ N ≤ a v exp(-b v x 2 ). (1)
The proof of ( 1) for v at level 0 follows from the fact that, for each e ∈ T (in particular, the one incident to v), o

(N ) e
follows a Bin(N m, 1/m) distribution, so that one can apply Hoeffding's inequality combined with Doob's maximal martingale inequality. This yields (1) for v at level 0, where a v = 2 and b v = 2/m. For v at level i ≥ 1, we have the property that there is an edge e incident to v such that all the other neighbors v 1 , . . . , v h of v (i.e., the neighbors not incident to e) have level smaller than i, and thus satisfy (1) by induction. We then have to check that c v (t) stays close to t/m for t ∈ [0..N m] (in the sense of (1)).

For the lower bound part, we use the fact that c v (t) ≥ o e (t), and that o e (t) stays close to t/m. For the upper bound part we use the following argument. Letting d v (t) = max(c v1 (t), . . . , c v h (t)), we can show that if c v (t 0 ) ≥ d v (t 0 ) + M at some time t 0 , then there exists t ≤ t 0 such that |o e (t ) -t /m| ≥ M/4 or |d v (t ) -t /m| ≥ M/4 (the crucial point to establish this property, specific to the CU-process, is that in the regime where c v (t) > d v (t), any step where c v (t) increases occurs when picking e). Since o e (t) and d v (t) stay close to t/m (for d v (t) we use induction on i, and the union bound), this property ensures that c v (t) is unlikely to exceed t/m. Given the lower bound part, c v (t) hence stays close to t/m (in the sense of ( 1)). Estimate (1) then guarantees that, in the N -uniform model, we have |c

(N ) v /N -1| ≤ N -1/3
with probability exponentially close to 1. The same holds in the N -balanced model, by noting that the N -balanced model is the N -uniform model conditioned on the event that each edge is chosen N times, which occurs with a probability of order N -m/2 (thus, any event that is almost sure with exponential rate in the N -uniform model is also almost sure with exponential rate in the N -balanced model).

The proof for k ≥ 3 is analogous but requires some more ingredients. An additional difficulty is that, for λ < λ k , a random edge e in H k n,λn may be in the giant component

(if λ ∈ ( 1 k(k-1) , λ k ))
. However, we rely on the fact that the peeling level of e is O(1) w.h.p., and prove that for a vertex v of bounded level, we have c 1) w.h.p. as N → ∞, where the o(1) term does not depend on the size of the giant component.

(N ) v /N = 1 + o(

Proof of Theorem 3

The excess of a hypergraph H is exc(H) = |E| -|V |.

Lemma 2. Let H = (V, E) be a k-uniform hypergraph. Then, for the N -balanced model, we have e∈E R

(N ) e ≥ 1
k exc(H). Proof. During the CU process, each time an edge is drawn, the counter of at least one of its extremities is increased by 1. Hence v∈V c

(N ) v ≥ N |E|. Hence, with the notation R (N ) v := c (N ) v /N -1, we have v∈V R (N ) v
≥ exc(H). Now, by Lemma 1, for each v ∈ V , there exists an edge e v incident to v such that c

(N ) ev = c (N ) v
(if several incident edges have this property, an arbitrary one is chosen). Hence, v∈V R (N ) ev ≥ exc(H). Note that, in this sum, every edge occurs at most k times (since it has k extremities), thus e∈E R

(N ) e ≥ 1
k exc(H). For k = 2 and λ > 1/2, it is known [START_REF] Pittel | Counting connected graphs inside-out[END_REF]Theorem 6] that there is an explicit constant f (λ) > 0 such that the excess of the giant component G = (V , E ) of G n,λn is concentrated around f (λ)n, with fluctuations of order √ n. Thus, exc(G ) ≥ 1 2 f (λ)n w.h.p. as n → ∞. Hence, by Lemma 2, w.h.p. as n → ∞ (and for any N ≥ 1), we have

err N (G n,λn ) ≥ 1 λn e∈E R (N ) e ≥ 1 2λn exc(G ) ≥ 1 4λ f (λ) =: f (λ),
which implies Theorem 3.

6 Analysis for some non-peelable hypergraphs

Analysing the asymptotic behaviour of the relative error of the CU-process on arbitrary hypergraphs seems to be a challenging task, even if we restrict ourselves to N -uniform and N -balanced models, as we do in this paper. Based on simulations, we expect that, for a fixed connected k-hypergraph H = (V, E), and for v ∈ V , we have c

(N ) v /N = C v + o(1) w.h.p. as N → ∞, for an explicit constant C v ∈ [1, deg(v)].
Since the number of increments at each step lies in

[1..k], constants C v must verify 1 ≤ 1 |E| v∈V C v ≤ k, where 1 |E| v∈V C v
can be seen as the average number of increments at a step. If H is peelable, then Theorem 2 implies that this concentration holds, with C v = 1. We expect that, if no vertex of H is peelable, and if H is "sufficiently homogeneous", then the constants C v should be all equal to the same constant C > 1, and thus the relative error R (N ) e of every edge is concentrated around C -1 > 0 w.h.p. as N → ∞. This, in particular, is supported by an experiment reported at the end of Section 4.2.

In this Section, we show that this is the case for a family of regular hypergraphs which are very sparse (O( |V |) edges) but have a high order (an edge contains O( |V |) vertices). The dual of a hypergraph H is the hypergraph H where the roles of vertices and edges are interchanged: the vertices of H are the edges of H, and the edges of H are the vertices of H so that an edge of H corresponding to a vertex v of H contains those vertices that correspond to edges incident to v in H.

Here we consider the hypergraph K n dual to the complete graph K n . It is a (n -1)-uniform hypergraph with n edges and n 2 vertices, all of degree 2, therefore no vertex is peelable. For a fixed n ≥ 3, we consider a CU-process on K n , in the N -balanced model. Note that with regular Count-Min, the relative error of every edge is 1, since all vertices have degree 2 and c (N ) v = 2N for every vertex v of K n . We prove that with conservative updates, the relative error is reduced to a smaller constant 1/(n -1). The proof is omitted and can be found in [START_REF] Fusy | Count-min sketch with variable number of hash functions: an experimental study[END_REF].

Non-uniform distributions

An interesting and natural question is whether the phase transition phenomenon holds for non-uniform distributions as well. This question is of practical importance, as in many practical situations keys are not distributed uniformly. In particular, Zipfian distributions often occur in various applications and are a common test case for Count-Min sketches [START_REF] Cormode | Summarizing and mining skewed data streams[END_REF][START_REF] Bianchi | Modeling conservative updates in multi-hash approximate count sketches[END_REF][START_REF] Einziger | A formal analysis of conservative update based approximate counting[END_REF][START_REF] Chen | Precise error estimation for sketchbased flow measurement[END_REF][START_REF] Ben Mazziane | A formal analysis of the count-min sketch with conservative updates[END_REF]. We mention a recent learning-based variant of CountMin [START_REF] Hsu | Learning-based frequency estimation algorithms[END_REF] (learning heavy hitters) and its study under a Zipfian distribution [START_REF] Aamand | Learned) frequency estimation algorithms under Zipfian distribution[END_REF][START_REF] Du | Putting the "learning" into learningaugmented algorithms for frequency estimation[END_REF]. In Zipf's distributions, key probabilities in descending order are proportional to 1/i β , where i is the rank of the key and β ≥ 0 is the skewness parameter. Note that for β = 0, Zipf's distribution reduces to the uniform one. It is therefore a natural question whether the phase transition occurs for Zipf's distributions with β > 0.

One may hypothesize that the answer to the question should be positive, as under Zipf's distribution, frequent keys tend to have no error, as it has been observed in earlier papers [START_REF] Bianchi | Modeling conservative updates in multi-hash approximate count sketches[END_REF][START_REF] Ben Mazziane | A formal analysis of the count-min sketch with conservative updates[END_REF][START_REF] Ben Mazziane | Analyzing count min sketch with conservative updates[END_REF]. On the other hand, keys of the tail of the distribution have fairly similar frequencies, and therefore might show the same behavior as for the uniform case.

However, this hypothesis does not hold. Figure 3 shows the behavior of the average error for Zipf's distributions with β ∈ {0.2, 0.5, 0.7, 0.9} vs. the uniform distribution (β = 0). The average error is defined here as the average error of all keys weighted by their frequencies3 , i. We observe that the phase transition behavior disappears for β > 0. It turns out that even in the subcritical regime, frequent elements, while having no error themselves, heavily affect the error of certain rare elements, which raises the resulting average error. This phenomenon is analysed in more detail in our followup paper [START_REF] Fusy | Count-min sketch with variable number of hash functions: an experimental study[END_REF]. In the supercritical regime (λ > 1 in Figure 3) the opposite happens: the uniform distribution shows the largest average error. This is because an increasingly large fraction of the keys (those in the core of the associated hypergraph) contribute to the error, while for skewed distributions, frequent keys tend to have no error, and thus the larger β (with frequent keys becoming more predominant) the smaller the average error. Note that this is in accordance with the observation of [START_REF] Bianchi | Modeling conservative updates in multi-hash approximate count sketches[END_REF] that the estimates for the uniform distribution majorate the estimates of infrequent keys for skewed distributions.

Concluding remarks

We presented an analysis of conservative update strategy for Count-Min sketch under the assumption of uniform distribution of keys in the input stream. Our results show that the behaviour of the sketch heavily depends on the properties of the underlying hash hypergraph. Assuming that hash functions are fully independent, the error produced by the sketch follows two different regimes depending on the density of the underlying hypergraph, that is the number of distinct keys relative to the size of the sketch. When this ratio is below the threshold, the conservative update strategy produces a o(1) relative error when the input stream and the number of distinct keys both grow, while the regular Count-Min produces a positive constant error. This gap formally demonstrates that conservative update achieves a substantial improvement over regular Count-Min.

We showed that the above-mentioned threshold corresponds to the peelability threshold for k-uniform random hypergraphs. One practical implication of this is that the best memory usage is obtained with three hash functions, since λ 3 is maximum among all λ k , and therefore k = 3 leads to the minimum number of counters needed to deal with a given number of distinct keys.

In [START_REF] Cohen | Spectral Bloom filters[END_REF] it is claimed, without proof, that the rate of positive errors of conservative update is k times smaller than that of regular Count-Min. This claim does not appear to be true. Note that Count-Min does not err on a key represented in the sketch if and only if the corresponding edge of the hypergraph includes a leaf (vertex of degree 1), while the conservative update can return an exact answer even for an edge without leaves. However, this latter event depends on the relative frequencies of keys and therefore on the specific distribution of keys and the input length. On the other hand, our experiments with uniformly distributed keys show that this event is relatively rare, and the rate of positive error for Count-Min and conservative update are essentially the same.

One important assumption of our analysis is the uniform distribution of keys in the input. We presented an experimental evidence that for skewed distributions, in particular for Zipf's distribution, the phase transition disappears when the skewness parameter grows. Therefore, the uniform distribution presents the smallest error in the subcritical regime. The situation is the opposite in the supercritical regime when the number of distinct keys is large compared to the number of counters: here the uniform distribution presents the largest average error. As mentioned earlier, for Zipf's distribution, frequent keys have essentially no error, whereas in the supercritical regime, low frequency keys have all similar overestimates. This reveals another type of phase transition in error approximation for Zipf's distribution, occurring between frequent and infrequent elements, having direct application to accurate detection of heavy hitters in streams. We refer to our follow-up work [START_REF] Fusy | Count-min sketch with variable number of hash functions: an experimental study[END_REF] for further insights regarding this issue.

=

  o e (N m) for the resulting number of occurrences of e ∈ E, c (N ) e = c e (N m) for the resulting counter of e ∈ E, and R (N ) e = R e (N m) e for the resulting relative error of e. In the N -balanced model, since each key e ∈ E occurs N times, we have R (N ) e = (c (N ) e -N )/N . Our main result is the following. Theorem 2 (subcritical regime). Let k ≥ 2, and let λ < λ k , where λ 2 = 1/2, and for k ≥ 3, λ k is the peelability threshold as defined in Section 3. Consider a CU-process on a random hypergraph H k n,λn under either N -uniform or Nbalanced model, and consider the relative error R (N ) e of a random edge in H k n,λn . Then R (N ) e = o(1) w.h.p., as both n and N grow 1 . Note that with the regular Count-Min algorithm (see Section 2), in the Nbalanced model, the counter value of a node v is c(N) v = N • deg(v), and the relative error R(N) e of an edge e = (v 1 , . . . , v k ) is always (whatever N ≥ 1) equal to min(deg(v 1 ), . . . ,

  shows plots for the average relative error err N (H k n,m ) as a function of λ = m/n, for k ∈ {2, 3, 4} for regular Count-Min and the conservative update strategies. Experiments were run for n = 1, 000 with the N -uniform model (each edge drawn independently with probability 1/m) and N = 50, 000 (number of steps N • |E|). For each λ, an average is taken over 15 random graphs.

= 4 Fig. 1 :

 41 Fig. 1: Average relative error as a function of λ = m/n for regular Count-Min (orange) and conservative update (blue), for k ∈ {2, 3, 4}. Vertical line shows the peelability threshold.

Fig. 2 :

 2 Fig. 2: Distribution of relative errors of individual edges shown in a random order along x-axis.

1 )

 1 (as N gets large), both in the N -uniform and in the N -balanced model (performed on T alone). Let m be the number of edges in T . We first give a proof for the N -uniform model. Since o (N ) e follows a Bin(N m, 1/m) distribution, we have w.h.p. o (N ) e /N = 1 + o(1). Hence, it is enough to prove that, for each vertex v ∈ T , we have w.h.p. c (N ) v /N = 1 + o(1).

Theorem 4 .

 4 For any fixed n ≥ 2, in the N -uniform model (resp. in the Nbalanced model), the counter of each vertex v ∈ K n satisfies c (N ) v /N = n/(n -1) + o(1) w.h.p. as N → ∞. Hence, the relative error R (N ) e of each edge e in K n satisfies R (N ) e = 1/(n -1) + o(1) w.h.p. as N → ∞.

  e. err N (H) =1 In other words, err N (H) is the expected error of a randomly drawn key from the entire input stream of length mN (taking into account multiplicities).

Fig. 3 :

 3 Fig. 3: Average error as a function of λ = m/n, for Zipf's distributions with β ∈ {0.0, 0.2, 0.5, 0.7, 0.9}. Plots obtained for n = 1000, k = 3, N = 50, 000.

This definition is natural for non-uniform distributions, as the error for a frequent key should have a larger contribution. Note that it is consistent with the definition of Section

4.1 in the N -balanced case, and in the N -uniform case it presents a negligible difference when N gets large.

Acknowledgments We thank Djamal Belazzougui who first pointed out to us the conservative update strategy.


Waltraud Paul
email: waltraud.paul@ehess.fr&shanshanyan@pku.edu.cn

Shanshan Yan

Sentence-final particles in Mandarin Chinese: Syntax, semantics and acquisition *

Keywords: split CP, sentence type, finiteness, tense, aspect

Sentence-final particles (SFPs) in Mandarin Chinese realize the heads of three projections in the rigidly ordered head-final CP 'Low CP < ForceP < AttitudeP'. Only the highest projection AttitudeP encodes discourse-related properties, whereas ForceP encodes the sentence-type (interrogative, imperative). Low Cs interact with properties of the TP-internal extended verbal projection and are obligatory when acting as (non-default) anchors. They play an important role in determining the temporal interpretation and finiteness in Mandarin Chinese and can therefore no longer be neglected by studies addressing these issues. There is no evidence for an "incremental" acquisition "up the tree" of the different projections in the split CP nor for the acquisition of TP prior to CP, as postulated by the cartographic approach.

Introduction

Mandarin Chinese not only features SFPs linked to discourse (as would be expected from its alleged "discourse-oriented" nature), but also SFPs encoding the sentence-type (interrogative, imperative etc.) as well as a set of SFPs that interact with the properties of the TP-internal extended verbal projection and in certain cases are obligatory. SFPs all occupy a position in the (right) sentence periphery (CP) and are construed with the entire clause, leading to a transparent syntax/semantics mapping in terms of scope relations. More precisely, SFPs realize heads in a three-layered split CP in the spirit of [START_REF] Rizzi | The fine structure of the left periphery[END_REF]: 1 (1) Split CP in Mandarin Chinese [START_REF] Paul | Consistent disharmony: Sentence-final particles in Chinese[END_REF]):

[Attitude-CP [Force-CP [ClowP [TP NP V NP] Clow° ] Force° ] Attitude°]]] [START_REF] Rizzi | The fine structure of the left periphery[END_REF] demonstrated in great detail that the sentence periphery above TP, the sentence proper, does not consist of a single CP hosting e.g. the fronted wh-phrase (and the "dummy" verb do, in the absence of an auxiliary verb) in English sentences such as [CP Whati [C' [C° did] [TP he buy ti ]]]?. On the contrary, the sentence periphery is "split up", i.e. divided into numerous subprojections displaying a rigid order, among them projections for topic phrases and focus phrases. As for the heads present in the left periphery, i.e. complementisers, he likewise argued that they are of different types and hence occur in different projections within the split CP. Complementisers indicating the type of clause (declarative "force", interrogative "force" etc., e.g. that, whether in English; che in Italian) head the projection ForceP preceding the topic and focus projections; by contrast, prepositional complementisers in Romance such as Italian di introducing infinitivals realize the head of FinitenessP, a projection immediately above TP and below topic and focus projections:

(2) a. Penso (*a Gianni) che, a Gianni, gli dovrei parlare think.1SG to Gianni that to Gianni him should speak 'I think that to Gianni, I should speak to him.' b. Penso, a Gianni, di (*a Gianni) dovergli parlare think.1SG to Gianni that to Gianni him.should speak 'I think, to Gianni, 'of' to have to speak to him.' [sic] (Rizzi 1997: 304, [61], [62])

Subsequent studies of mostly Romance and Germanic languages extended this approach to matrix clauses and analysed as different types of complementisers those items at the sentence periphery that had so far been called "particles", for want of a precise categorial status (cf. among others [START_REF] Munaro | Ways of clausal typing[END_REF]. Importantly, these studies also provided evidence for the existence of an additional, discourse-related projection above ForceP, equivalent in function to the projection labelled AttitudeP by [START_REF] Paul | Consistent disharmony: Sentence-final particles in Chinese[END_REF] (3) DiscourseP > ForceP > FiniteP > TP (Split CP for Germanic and Romance languages) (Note that (3) concentrates on the projections within the split CP that are exclusively realized by heads, to the exclusion of topic and focus phrases.) The hierarchy in (3) thus extends [START_REF] Rizzi | The fine structure of the left periphery[END_REF] original hierarchy where the highest projection had been ForceP. Comparing (3) with (1) for Chinese, we see that they only differ in the directionality, head-initial for [START_REF] Rizzi | The fine structure of the left periphery[END_REF], head-final in Chinese. 2The split CP for Chinese in (1) in fact recasts into modern terms the observations by the eminent Chinese scholar Zhu Dexi (1982: 207-213). He identified three distributional classes of SFPs whose relative order is fixed. The SFPs belonging to the first class, SFP1, occur nearest to the sentence proper (TP) and are said to "express tense/aspect"; they comprise SFPs such as le and láizhe (cf. (6a) below) and realize LowCP in (1). The SFPs of the second class, SFP2, to the right of the position for SFP1, convey notions such as yes/no question (ma) and imperative (ba) (cf. (5a) and (7a) below) and thus illustrate the ForceP in (1). The third, "outermost" class of SFP3, finally, is explicitly stated to be different from the two other classes, because it involves the speaker's attitude or feelings (hence the label AttitudeP in (1)); SFPs belonging to this class are e.g. a, ou etc. (cf. (7a), (8a) below). Zhu Dexi (1982: 208) emphasizes that co-occurring SFPs belong to hierarchically different levels, while SFPs of the same class are mutually exclusive, such as e.g. le and láizhe, which both belong to the innermost class, SFP1 (cf. (6b) below).

(4) [S …..] SFP1] SFP2] SFP3]
The ordering restrictions underlying the configuration in (4) are illustrated below:

(5) a. Starting with examples (8a) and (7a), an SFP3 such as ou, which expresses the speaker's impatience, must follow the SFP2 ba (expressing a "softened" imperative) in (7a) and the SFP1 le. Since it consists of a single vowel, ou fuses phonetically with the preceding SFP into a single syllable. 3 Likewise, the innermost SFP1 le must always precede SFP2 such as the interrogative ma (cf. (5a)), as shown by the unacceptability of the opposite order in (5b). (8a) further illustrates [START_REF] Zhu | Yǔfǎ jiǎngyì [On grammar[END_REF] basically uses the same reasoning in order to determine the relative order of SFPs as the cartographic approach does when establishing the hierarchy of functional projections. 4 Since for semantic reasons it is rather difficult to construe and find sequences where all the three classes co-occur, Zhu (1982: 208) applies the notion of transitivity: if a given SFP A is shown to precede the SFP B and the SFP B precedes the SFP C, then necessarily A likewise must precede C. This same notion of transitivity also underlies Zhu Dexi's (1982: 208) statement that the relative order always holds, i.e. also when a given SFP position remains empty, as in the combination of the SFP1 le with the SFP3 ou in (8a).

The article is organized as follows. Section 2 provides the general background for the analysis of SFPs as C-heads in Chinese. No exhaustive presentation is intended nor possible here. (For systematic overviews, cf. Paul 2015, ch. 7;[START_REF] Pan | Mandarin peripheral construals at the syntax-discourse interface[END_REF], 2019a;Paul & Pan 2017). Instead, we choose to highlight some aspects of SFPs which have either not received enough attention so far or have not been sufficiently spelt out. Section 2.1 on ClowP argues that the low Cs le, ne1 and láizhe contribute to the temporal interpretation, but themselves do not encode tense or aspect themselves. They are thus not on a par with the TP-internal aspectual heads, as also evidenced by their co-occurrence. Section 2.2 turns to the SFPs in ForceP realizing sentence types such as interrogative and imperative. Given that these SFPs have been extensively studied, claims in the literature that Chinese lacks such Force heads (cf. [START_REF] Li | Chinese Final Particles and the Syntax of the Periphery[END_REF][START_REF] Bailey | Word order and the syntax of question particles[END_REF][START_REF] Gobbo | On sentential particles: a crosslinguistic study[END_REF] are very surprising and shown not to be borne out by the data. Section 2.3 examines the third, highest layer in the split CP, i.e. AttitudeP. Section 3 briefly addresses the issue of acquisition. Importantly, by the age of two years, children have basically acquired all three types of SFPs, including Attitude heads, which are subject to rather complex semantic-pragmatic constraints. These data challenge Friedmann et al.'s (2021) hypothesis of an incremental step-by-step acquisition, both with respect to the relative order of TP and CP and the order within the periphery. Section 4 concludes the article and emphasizes the importance of the low Cs for future studies on tense and finiteness in Chinese.

The three-layered CP in Chinese: Overview and some in-depth case studies

The analysis of SFPs as complementisers goes back to Thomas Hun-tak [START_REF] Lee | Studies on Quantification in Chinese[END_REF] who was the first to claim C-head status for the yes/no question particle ma. The analysis of ma as C became the standard analysis and was confirmed by subsequent studies, which also introduced another C, i.e. ne (cf. L.-S. Lisa [START_REF] Cheng | On the Typology of Wh-questions[END_REF]. Tang Ting-chi (1989: 541) extended the Canalysis to SFPs in general. The architecture of the Chinese sentence periphery was developed in more detail within [START_REF] Rizzi | The fine structure of the left periphery[END_REF] split CP approach by [START_REF] Paul | Low IP area and left periphery in Mandarin Chinese[END_REF] Importantly, there are several cases of homonymy between low C-heads and Attitude-heads, hence our indexing the low C-heads ne1 and láizhe1 with 1 and the Attitude-heads ne3 and láizhe3 with 3. The two force heads ba, advisative ba (softening the imperative) and the question confirmation ba, are likewise homonyms, but can be told apart by the associated semantics and sentence intonation. Finally, the yes/no question force head ma and the dogmatic assertion attitude head ma (where the speaker insists on her/his opinion) can be easily distinguished by the resulting interpretation and different intonational contours. Although homonymy is a widespread phenomenon in Mandarin Chinese, the homonymy between SFPs belonging to different projections has led to quite a confusion in the literature and must be carefully controlled for. Finally, the table in (9) foremost captures the relative hierarchy between SFPs and is not meant to imply that they can all co-occur, given the semantic constraints observed for each SFP further discussed below.

2.1. Low CP 2.1.1. The C-heads láizhe1, ne1, le as "expressing tense" [START_REF] Zhu | Yǔfǎ jiǎngyì [On grammar[END_REF]) Zhu Dexi (1982: 208) Instead, these characterizations rather attempt to capture the semantic import of the SFPs, which is also reflected in the constraints observed for the type of TP each SFP can select, to be examined in detail further below.

As reflected in Zhu's comments and the translations provided, the low Cs inter alia differ in whether or not the event held in the past, and in whether the event holds at speech time or not. While these two values are obvious in the translations of (10a) and (10b), i.e. 'It's (still) raining.' and '(Look), it's raining (now).', (10c) with the low C láizhe requires a further comment. More precisely, for láizhe the default interpretation is that the event no longer holds at the speech time, as evidenced by the following mini-dialogue (but cf. (15) below):

(11) A: Wàimiàn dì zěnme shī le? outside ground how humid CLOW 'How come the ground is humid outside?' B: Wàimiàn xià yǔ láizhe.

outside fall rain CLOW 'It (just) rained outside.'

The second triple provided [START_REF] Zhu | Yǔfǎ jiǎngyì [On grammar[END_REF] with mén kāi 'door open' as lexical material allows us to further sharpen the differences between the three low Cs. We elaborate on (i) the interaction of low Cs with TP-internal properties as illustrated by certain incompatibilities, (ii) the difference between the low Cs and aspect as a verbal category, and (iii) thus make more precise the import and role of the SFPs.

We again start with the low C ne as the most straightforward case:

(12) Mén kāi -zhe ne.

Nǐ wèishénme qiāo mén? door open-IMP CLOW 2SG why knock door 'The door is (standing) open. Why do you knock?'

As stated for ne in (10) above, the eventuality holding now, i.e. state of standing open, already held in the past, as explicitly mentioned by Zhu Dexi (1982: 209).

This contrasts with le in (13), as shown by Zhu's comment enclosed in square brackets: Turning now to láizhe, we first illustrate (in a mini-dialogue) the default reading where the eventuality holding in the past no longer holds at the speech time.

Context: A says that B just went to C's office for some documents, but couldn't get in. ( 14) C answers: Shì ma? Mén kāi -zhe láizhe, tā wèishénme jìn -bù-lái?

be FORCE door open-IMP CLOW 3SG why enter-NEG-come 'Is that so? The door was open, (so) why couldn't he get in?' While in the default reading the eventuality holding in the past no longer holds at the speech time, it is not excluded for the eventuality to still hold at speech time; as a result, both continuations in (15) are felicitous: To wrap up our results so far, the crucial differences between the three low Cs consist in whether the event holds at speech time or not and whether the event held before or not. For ne1, the event still holds at speech time and likewise held in the past. For le, the event holds at speech time and did not hold in the past. For láizhe, the event held in the past and may or may not hold at speech time (with the latter as default case).

The selectional properties of the low Cs

Against this backdrop, we now examine the selectional properties of each low C, which at the same time highlight that the low Cs themselves can not be analysed as aspect markers (pace a.o. Niina Zhang 2019). 7

7 Niina Zhang (2019) concentrates on the finiteness issue in complement clauses and claims that when a complement clause does not allow for a low C (her "sentence-final aspect particles"), then it is automatically nonfinite. This claim is too simplistic and incorrect and not borne out by the data. Many matrix clauses are perfectly grammatical without any SFPs (cf. ( 18c), (19b), (26a)), and likewise acceptable in the same form as complement clauses. Furthermore, the SFPs le, ne, láizhe are mechanically tested by Niina Zhang in all kinds of sentences, without their associated semantic constraints being taken into account. Accordingly, in many cases, the SFP in question is simply incompatible with the TP-internal predicate in both the complement clause and the corresponding matrix clause; accordingly, this incompatibility cannot be taken as a diagnostic for the non-finite status of the clause at hand. The presence of the progressive aspect auxiliary zài in (18c) demonstrates that aspect as a verbal category is distinct from the low C ne. Importantly, ne in (18c) is optional, confirming our point just made. This contrasts with (18a-b) and with Zhu's (1982) (10a) above where ne is obligatory, given the bare nature of the activity predicate.

With respect to the alleged status of low Cs as aspect markers, the low C le has caused quite some confusion, due to its homonymy with the perfective aspect verb suffix -le . Although the distinctness of the SFP le and the aspectual suffix -le was established a long time ago (cf. a.o. Chao Yuen Ren 1968: 246, Teng Shou-hsin 1973, Marjorie K. M. [START_REF] Chan | Temporal reference in Mandarin Chinese: An analytical-semantic approach to the study of the morphemes le, zài, -zhe, and ne[END_REF][START_REF] Li | Mandarin Chinese. A Functional Reference Grammar[END_REF]: 296, Zhu Dexi 1982), claims that both items instantiate one and the same category regularly make their reappearance in the literature (like the famous Loch Ness monster). This seems particularly futile given the many cases provided in the literature where the aspectual suffix -le and the SFP le co-occur (cf. Le signals that the proposition 'I won't wait for him' obtains at the speech time (in the absence of any other reference time), which leads to 'I will no longer wait for him'.

Finally, when an explicit reference time (different from the speech time) is provided ('as soon as I rang the bell'), le relates the event to that time: Unlike le, láizhe by default indicates that the event that held in the past no longer holds at speech time. Accordingly, le in (22a) is unacceptable, because gāngcái 'just now, a moment ago' explicitly locates the event in the past, whereas le relates the very same event to the speech time. This is not the case for láizhe, hence its acceptability.

( This shows that the temporal interpretation of the event is based on the TP-internal material, a fact confirmed by the optionality of láizhe in (23a-b). Also note that "recent past" is a flexible notion and not limited to adverbs such as gāngcái 'just now' and zuìjìn 'recently'; instead, what counts as "recent past" also depends on the speaker's judgement of the immediacy of the event at hand, as witnessed by the acceptability of 'last month' in (23b) (cf. Song Yuzhu 1981: 272).

Secondly, in addition to the "recent past" feature, láizhe asserts that the event has taken place (cf. [START_REF] Song | Guānyú shíjiān zhùcí de hé láizhe [On the tense particles de and laizhe[END_REF]: 275, Lü Shuxiang 2000: 348-349). As a result, láizhe is incompatible with a TP whose predicate is negated. This well-known observation from the literature was confirmed by the acceptability judgement test with eight native speakers (average age around 28 years) who uniformly rejected negation in láizhe sentences (cf. the first clause in (25b) and fully accepted the assertion strengthening function of láizhe in (24b):9 (24) A: Nǐ shì bù shì qù kàn diànyǐng le? 2SG be NEG be go watch movie CLOW You went to the movies, didn't you? (Literally: 'Is it the case or not that you went to the movies?') B: Wǒ zài jiā zuò zuòyè láizhe, méi qù kàn diànyǐng. 1SG at home do homework CLOW NEG go watch movie '(In fact) I did my homework at home, I didn't go to the movies.' (25) A: Nǐ shì bù shì zài jiā zuò zuòyè le? 2SG be NEG be at home do homework CLOW 'You did your homework at home, didn't you?' B: *Wǒ méi zài jiā zuò zuòyè láizhe. (Wǒ qù kàn -le diànyǐng.) 1SG NEG at home do homework CLOW 1SG go watch-PERF movie '(In fact) I didn't do my homework at home. (I went to the movies.)' In B's response in (24b), láizhe strengthens the assertion and thereby corrects A's wrong assumption. In (25b), the first clause is unacceptable, due to the conflict between the assertion strengthening component of láizhe and the negated predicate.

Low CP: Interim summary

The low Cs láizhe1, le and ne1 all interact with TP-internal material and impose constraints on the properties of the extended verbal projection, including its aktionsart. However, they clearly occupy a TP-external position in the left periphery (contra Erlewine (2017); cf. Victor Junnan Pan (2019b) for a critical review). The low Cs themselves do neither encode aspect nor tense, as evidenced inter alia by their cooccurrence with aspect markers on the verb. Instead, low Cs indicate whether the event in question holds at the speech time and/or whether it held before. In joint ongoing work with Gillian Ramchand (University of Tromsø), this is taken to indicate that -roughly speakingthe low Cs are overt versions of the (non-default) anchor, the default anchor being NOW, a moment. Low Cs thus contribute to the finiteness of a sentence in the absence of aspect markers, which either turn the event into a state (able to be true at a moment) or indicate a temporal precedence relation (as in the case of -le). 10 The temporal interpretation of a sentence obtains as resulting from the interaction between the properties of the TP-internal predicate (bare or not bare, state or non-state), on the one hand, and the precise nature of (the stative intermediate reference situation introduced by) the low C. 20 year ago invent -PERF mouse CLOW/ CLOW FORCE 'Twenty years ago they had probably invented the computer mouse.' (36a) is read in a low contour, in accordance with ba expressing a conjecture rather than asking for a confirmation. The default stress lies on sānshí nián qián '30 years ago', but stressing méi yǒu 'not exist' or even shǔbiāo 'mouse' might also be possible. The analysis of ne as a low C here is confirmed by its unacceptability in (36b) with the telic predicate fāmíng-le 'have invented', given that ne requires atelic predicates in its TP-complement (cf. ( 16) -(18) above).

SFPs realizing

The Force head baIMP: advice or suggestion

The SFP baIMP is called "advisative" by Chao Yuen Ren (1968: 807) because of its "softening" effect. Accordingly, an imperative containing baIMP is understood as less harsh an order than the corresponding imperative sentence without baIMP (also cf. Finally, (39) below illustrates the role the semantic (in)compatibility plays, in addition to the hierarchy in the split CP. While the order 'low C > Force' in itself is correct, the sequence 'ne1 baadvis' is ruled out for semantic reasons: an event in the future, whence neither holding in the past nor ongoing in the present is incompatible with the low C ne1, while this type of event is fine for the imperative advisative ba. This conflict leads to an unacceptable sentence: This semantic incompatibility is a very robust phenomenon confirmed by all of the eighteen native speaker participants, who stated they could not assemble a correct sentence by using all of the lexical items provided, as required in this sentence assembly task.

ForceP: interim summary

The observations in this section, mainly based on widely used grammars and grammar manuals, straightforwardly invalidate Li Boya's (2006: 171) claim that the clause-typing heads always remain covert in Mandarin and Cantonese (whereas they may be realized overtly in Wenzhou).

Given the semantically transparent and extremely well-documented yes/no question Force head ma2 this is a very surprising statement. In particular , Li Boya (2006: 64-65) doesn't see that there are two SFPs ma, the yes/no question Force head ma2 and the Attitude head ma3 (cf. section 3 immediately below), despite the well-established difference between the two (cf. a.o. Chao Yuen Ren 1968: 801). Both del [START_REF] Gobbo | On sentential particles: a crosslinguistic study[END_REF] and [START_REF] Bailey | Word order and the syntax of question particles[END_REF] adopt Li [START_REF] Li | Chinese Final Particles and the Syntax of the Periphery[END_REF] incorrect claim that Chinese has no SFPs realizing Force such as imperative and interrogation. While Del Gobbo et al. (2015: 378) see this as a parallel with sentential particles in Romance, Bailey (2015: 420) considers it a general characteristic of final question particles in VO languages that they are in fact markers of "something other than interrogative force".

Attitude Phrase

The SFPs instantiating AttitudeP involve both speaker and hearer, via the speaker's assumptions concerning the beliefs of the hearer. Again, Chinese is not unique in this respect, given that e.g. Japanese (cf. Endo 2007: 175-198) as well as Romance and Germanic languages likewise display particles in the sentence periphery encoding properties of the speaker-hearer interaction. Examining Romanian and West-Flemish, [START_REF] Haegeman | The syntacticization of discourse[END_REF] postulate the projection DiscourseP, equivalent in function to AttitudeP in Chinese. Importantly, the characteristics of SFPs realizing DiscourseP established by [START_REF] Haegeman | The syntacticization of discourse[END_REF] also hold for Attitude SFPs in Chinese. First, AttitudeP does not concern nor affect the truth value of the proposition at hand. This contrasts with the SFPs instantiating ForceP, where as we have seen baQconfirmation conveys the speaker's belief that the proposition is true, and ma is a request as to the truth value of the proposition (yes/no). It is correct that an SFP such as the advisative baIMP also conveys the speaker's (friendly) attitude, but at the same time this SFP is linked to a particular sentence type, i.e. the imperative. Furthermore, its status as Force head is confirmed by its obligatorily preceding Attitude SFPs such as ou (cf. (7a) above). As for low C, láizhe 'recent past' was shown to be incompatible with TP-internal negation, due to its event assertion feature (cf. section 2.1.2 above). Attitude SFPs are thus fundamentally distinct from both low C and Force heads, an observation already made by Zhu (1982: 208), although not further elaborated upon.

Second, Attitude SFPs indicate the speaker's commitment to the sentence content; they are interactional and imply the obligatory presence of a hearer (hence infelicitous in broadcasts).

Third, Attitude SFPs are deictic, i.e. they are directly correlated with the speech act, but do not require a preceding utterance as "trigger". Finally, [START_REF] Haegeman | The syntacticization of discourse[END_REF] concede that it is difficult to determine exactly the interpretive properties of Attitude SFPs, even though their semantic import is clearly discernible when comparing sentences with and without them. This leads to the fourth characteristic, which is the "optionality" of Attitude heads. A caveat is necessary here, though; if one wants to signal the discourse function associated with a particular Attitude SFP, then the presence of this SFP is evidently required.

The Attitude heads ne3 and bàle

Note first of all that ne3 is not a "wh-question particle", i.e. it is not a Force head indicating the sentence-type (pace L.-S. Lisa Cheng 1991), a fact again well-documented in the literature (cf. a.o. Hu Mingyang 1981: 418;Paris 1981: 389;Li and Thompson 1981: 305;Lin William C. 1984: 220;also cf. Pan & Paul 2016). In other words, in a wh question (cf. ( 40)) or in an A-not-A polar question (cf. ( 41)), the Attitude head ne3 is not obligatory, for the simple reason that ne3 does not encode the interrogative force. However, if one wants to signal the discourse function associated with ne3, which inter alia is to solicit the co-speaker's attention, rendered here by "listen, and you…", it is evidently obligatory (cf. a.o. [START_REF] Wu | The discourse function of the Chinese particle ne in statements[END_REF] Being an Attitude head, ne3 can naturally also combine with a non-interrogative complement, further invalidating its alleged status as a "clause typer" for wh-questions. It then expresses an exclamation/exaggeration or conveys a boasting tone (cf. ( 43)) and is obligatory in the presence of the speaker-oriented emphatic adverb kě 'really' (cf. ( 44 14)) German linguist really many ATT 'There really are a lot of German linguists!' Zhu (1982: 213) also provides the neat minimal pair below (slightly changed) where ne3 alternates with bàle, the latter being paraphrasable as 'that's all there is to it' and having the effect of "downplaying", which is exactly the opposite of the boasting tone mediated by ne3:

(45) Tāmen yào wǔbǎi kuài qián ne! Bù shì ge xiǎo shùmù! 3SG want 500 CL money ATT NEG be CL small sum 'They want (as much as) 500 dollars! That's not a small sum!' The semantics of ne3 and its being able to co-occur with low Cs clearly distinguishes it from the low C ne1 and warrants the status of the former as an Attitude head. This result also challenges a uniform analysis of ne1 and ne3 (cf. a.o. Hu Mingyang 1981, [START_REF] Wu | The discourse function of the Chinese particle ne in statements[END_REF]). 11

The Attitude head ma

The Attitude head ma (henceforth maAtt) implies that the speaker presupposes the hearer not to be up to date and provides a correction of the hearer's belief, conveying something like 'this is self-evident', 'you should know' (cf. Chao Yuen Ren's 1968: 801 term "dogmatic assertion"):

(48) Tā bù shì Lǎolǐ ma?

Ràng tā jìnlái maAtt.

(Lü Shuxiang 2000: 375) 3SG NEG be Laoli FORCE let 3SG come.in ATT 'Isn't that Laoli? Let him come in. (Why do I have to tell you?)'

11 [START_REF] Constant | Contrastive topic: Meaning and Realizations[END_REF] goes even further and incorrectly conflates the Attitude head ne 3 with the topic head ne (cf. (i)). More precisely, both are claimed to be instances of the contrastive topic (CT) and realizations of the CT operator (distinct from the "aspectual" SFP ne 1 ) (p. 438). Cf. [START_REF] Paul | Why particles are not particular: Sentence-final particles in Chinese as heads of a split CP[END_REF]2015, ch. 6) for showing that the allegedly inherent contrastive value of the topic head ne is not borne out by the data; inter alia, Top° ne can host sentential adverbs (where [+ contrast] does not apply) in its specifier, and Top° ne can co-occur in the same sentence with ne 3 : (i) [START_REF] Constant | Contrastive topic: Meaning and Realizations[END_REF] conflation also glosses completely over the well-known fact that TopP is head-initial, while AttP is head-final, and over the associated consequences. Furthermore, Wei & Li (2018: 206) highlight an important tonal difference between the Top° ne and the Att° ne 3 , which holds regardless of the tone of the preceding syllable; while the Top° ne is always pronounced in a high tone, the Att° ne 3 is always pronounced in a low tone.

(49) Wǒ shuō jīntiān shì xīngqīsān maAtt! Nǐ shuō bù shì! 1SG say today be Wednesday ATT 2SG say NEG be 'I say it's Wedndesday today! You say it isn't!' (Zhu Dexi 1982: 213) The Attitude head maAtt is clearly distinct from the Force head ma encoding yes/no questions, as generally acknowledged in the literature (cf. a.o. Chao Yuen Ren 1968: 800-801, Zhu Dexi 1982: 211-213, Lü Shuxiang 2000: 375-376) and nicely illustrated by ( 48) with both SFPs in successive sentences. This invalidates Li Boya (2006: 64-65) who postulates a single ma "mark[ing] a high degree of the strength of the assertive or directive force". 12 2.3.3. The Attitude head láizhe As shown by Pan (2019a: 109), in addition to the low C láizhe 'recent past', there is also an Attitude head láizhe:

(50) [AttP [TP Tāmen liǎ shénme shíhou jié hūn ] láizhe] ? (Pan 2019a: 109, (40a); 3PL two what time join marriage ATT bracketing simplified) 'By the way, when will they get married?' 13 While Pan (2019a: 109) renders this láizhe as 'by the way', we think it rather refers to a former state of knowledge and accordingly can be paraphrased as 'What did you say' or 'What was + sentence', indicating that the speaker no longer exactly recalls the sentence or prior knowledge. This is particularly neat in (51a) below: This interlocutive láizhe is clearly different from the low C láizhe; accordingly, (51a) is not a question concerning somebody's family name in the past. The latter requires a temporal adverb such as yǐqián 'before, earlier' as in (51b), where the low C láizhe is optional.

Importantly, being an Attitude head, the interlocutive láizhe can co-occur with, i.e. follow the low C le, something completely excluded for the low C 'recent past' láizhe (cf. (6b) above):

(52) [AttP [CLOWP [TP Xiǎo Wáng qù nǎr mǎi cài
] le ] láizhe]? Xiao Wang go where buy vegetables CLOW ATT Wǒ xiǎng-bù-qǐlái le. 1SG think-NEG-rise CLOW 12 Li Boya (2006) also glosses over the intonational difference observed by Chao (1968: 801). While the Force had ma is associated with a fairly high intonation ending in a slight drawl, the Attitude head ma is always short. 13 Implementing the generalization in Paul (2015: 285) 'Where was it/did you say that Xiao Wang went buying groceries? I (simply) cannot recall.'

As to be expected, the inverse order 'láizhe le' is ruled out. This also holds for those speakers who only marginally accept (52); they categorically reject 'láizhe le', given that there is no Attitude head le and that accordingly, 'láizhe le' can only be parsed as the illegitimate sequence of two low Cs. Finally, note that the examples illustrating the interlocutive láizhe are all questions, showing that they involve the hearer, either a real or an imaginary one, because (52) can also be a self-directed question or musing.

2.3.4.The Attitude head a

The SFP a has rather complicated morphophonemics depending on the preceding word, which is often reflected in different transliterations: ia, (u)a, (n)a, (ng)a etc. (cf. [START_REF] Chao | A Grammar of Spoken Chinese[END_REF]: 803, Zhu Dexi 1982: 212, Yang-Drocourt 2007: 192-195 for detailed discussion). For ease of exposition, we gloss over these phonological alternations and use the transliteration a throughout.

The SFP a is rather ubiquitous and occurs with all kinds of sentence types (declaratives, questions, imperatives, exclamatives), which makes its semantic characterization very difficult. Scholars agree that a conveys the personal implication of the speaker and has a general softening effect; the different interpretations observed for a are then due to the different sentence types it combines with (cf. a.o. Chao Yuen Ren 1968: 803-806;Zhu Dexi 1982: 212, Li andThompson 1981: 313-317). For example, Chao Yuen Ren (1968: 804) observes that a question with the SFP a is less blunt than one without it, an effect which can be paraphrased as 'by the way' or 'excuse me' etc.

(53) Nǐ míngtiān chūqù bù chūqù a? 2SG tomorrow go.out NEG go.out ATT '(By the way) are you going out tomorrow?'

Likewise, an imperative with the SFP a has less the flavour of a command than an imperative without it (though according to Chao Yuen Ren [1968: 804] the softening effect with a is less strong than with the advisative baIMP discussed above):

(54) Shuō a , bié hàipà a! say ATT NEG be.afraid ATT 'Say it, don't be afraid! In an exclamative, a expresses the emotion of the speaker which, depending on the sentence meaning, can be anger, astonishment, enthusiasm etc.: (1982, ch. 16) for the three classes of SFPs can be easily recast as a split CP à la Rizzi, modulo the addition of the projection AttitudeP (absent from Rizzi's original hierarchy) above ForceP. Importantly, studies on Romance and Germanic languages within Rizzi's split CP approach independently argue for the necessity of such a speaker/hearer related Discourse projection. SFPs are clearly heads, because they impose selectional restrictions on their clausal complement (such as declarative or interrogative sentence type). Low Cs as (non-default) anchor interact with the properties of the extended verbal projection; depending on the (non-) bare nature of the predicate and its aktionsart (state vs non-state), they may be obligatory to make the sentence finite.

The detailed study of ne and láizhe has illustrated several problems encountered in the analysis of SFPs in general, among them the homonymy between C-elements instantiating different projections (here LowCP and AttitudeP). The SFPs baIMP and baQconfirmation reveal yet another analytic difficulty, namely the homonymy between SFPs belonging to the same projection, in this case ForceP.

The decision to be made for homonymous SFPs is further complicated by the interaction between the properties of each SFP, the sentence meaning itself, the sentence intonation and the context, all of which contribute to the interpretation obtained. As a consequence, it is not always easy to pin down the meaning component provided by the SFP itself. Besides, the use of SFPs, especially those realizing AttitudeP, is also subject to individual and regional differences which still remain to be elucidated. (In general, Northern speakers seem to use SFPs more frequently than Southern speakers.) These caveats notwithstanding, it is evident that SFPs are an integral part of the syntax and as such subject to syntactic constraints, the most visible being the hierarchy of the different projections reflected in their rigid order.

The cartographic approach and the acquisition of SFPs

Having recast Zhu Dexi's (1982) three SFP-classes into a split CP à la [START_REF] Rizzi | The fine structure of the left periphery[END_REF], one might wonder whether another tenet of the cartographic approach likewise holds for Chinese, viz. that acquisition is "incremental" and proceeds layer by layer "up the tree", i.e. first the TP and then the periphery (cf. Friedmann/Belletti/Rizzi 2021: §5.2.1). The left periphery in Hebrew is said to be acquired in two steps "defining two zones: first a lower LP zone including Fin, Mod, and Q and then a higher LP zone that includes Force, Int, and Top." (page 37) Note that neither a head nor an entire zone can be "skipped". At the same time, the authors concede that the two zones do not form natural classes characterizable by a common feature, "because it includes topics, force markers (embedding markers), and operators such as yes/no operators (in embedded questions), relative clause operators, and why".

Although we concentrate on SFPs here only and abstract away from the acquisition of Topic Phrase (included in Friedmann et al.'s study), the Chinese data might nevertheless shed some light on their hypothesis. In particular, we will see that low C, Force head and Attitude heads are more or less acquired simultaneously. Since Chinese is a pro-drop language, on the surface a TP often simply consists of a bare VP. It is therefore difficult to decide whether indeed the full structure of the TP (including aspect, auxiliaries and negation) is acquired before the CP. Given that the child data also include utterances consisting of NPs plus the Attitude head a (cf. (65c) below), it is equally plausible to postulate the simultaneous acquisition of TP and CP (something which has to be assumed for the acquisition of Germanic V2 languages with V-to-C movement in any case).

Tao Yu (2012) sets the onset for the productive use of SFPs at the age of 01;07 and reports the spontaneous use of the following SFPs before the age of two years by the four children examined: the low C ne1 and the Attitude ne3, the Force head ma (yes/no question) and the dogmatic assertion Attitude head ma, the two Force heads ba, i.e. advisative ba in imperatives and the confirmation request question ba.

(63) a. Māma zài zhè ma ? (WYF 1;10;16) mum be.at here FORCE 'Is mum here?' b. Hǎo chǒu a ! (WYF 1;09;15) so be.ugly ATT '(This) is so ugly!' (64) Wǒ zhǎodào māma le.

(ZZC 2;00;21) 1SG find mum CLOW 'I have found mum.' (65) a. Child: Yǒu jīmù.

(ZZC 1;10;20) exist toy.bricks 'There are toy bricks.' b. Father: Jīmù toy.bricks c. Child: Jīmù a! toy.bricks ATT 'Ha, toy bricks!' (63) illustrates the Force yes/no question head ma, distinct from the homonymous Attitude head ma in (60b) and (61b) above. ZZC's sentence of the form 'NP a' is rather intriguing, because unlike her/his father in (65b), ZZC does not use a one word utterance, but adds a. (Note that ZZC starts out with the complete sentence (65a)).Whether (65c) indeed represents an AttP (whose TP complement consists of an NP only) or rather an NP followed by the homonymous pause particle a must be left open here.

To summarize, by the age of 2-3 years, children have in principle acquired all the three types of SFPs, with their often very subtle semantics/pragmatics and the selectional restrictions on their complements. There is no real evidence for the "first TP, then CP" incremental acquisition hypothesis postulated by [START_REF] Friedmann | Growing trees: The acquisition of the left periphery[END_REF]. Upon further reflection, this is in fact a desirable result, because TP and CP delimit each other; for the child to acquire the TP projection requires the knowledge about the periphery beyond.

Conclusion SFPs in Mandarin

Chinese have been demonstrated to be complementisers and to realize the heads of three projections in the rigidly ordered head-final CP 'Low CP < ForceP < AttitudeP'. Importantly, this split CP only exists in root contexts, whereas in non-root contexts at most one C is allowed, if at all. More precisely, C-elements acceptable in non-root contexts are restricted to low C (láizhe1, le, ne1), to the exclusion of the Force and Attitude heads.

All SFPs display a complex feature make-up (among them the specification for [+ root]), thus challenging Huang, Li and Li's (2009: 35) view that such complex feature bundles are a characteristic of functional categories in Indo-European languages, but do not exist in Chinese.

Importantly, low Cs, by virtue of their acting as (non-default) anchors, have been shown to play an important role in determining the temporal interpretation and finiteness in Chinese, and can therefore no longer be neglected by studies addressing these issues, as has been the case so far (cf. a.o. Sun Hongyuan 2014[START_REF] Lin | Tenselessness[END_REF].

  in (1) for Chinese (cf. a.o. Benincà 2001 for Romance languages, Haegeman 2014 and Haegeman and Hill 2013 for West-Flemish):

( 13 )

 13 Mén kāi le. [Yuánlái guān-zhe.] Wǒmen jìnqù ba. door open CLOW before close-IMP 1PL enter FORCE 'The door is open (now). [It was closed before.] Let's go in.' As expected, (mén) yuánlái guān-zhe '(the door) was closed before' would be unfelicitous as a continuation for (12) Mén kāi-zhe ne 'The door is (still) open'.

( 15 )

 15 Mén kāi -zhe láizhe, xiànzài guān-shàng -le / xiànzài yě kāi -zhe ne. door open-IMP CLOW now close-ascend-PERF/ now also open-IMP CLOW 'The door was (standing) open, now it's closed/ and it's still open now.

  (21) [CPlow[TopP[TP Wǒ yī ān mén-líng] [Top'[TP tā jiù lái kāi mén] le]]] 1SG once ring door-bell3SG then come open door CLOW 'As soon as I rang the door bell, he came and opened the door.' (slightly modified example fromChao Yuen Ren 1968: 799)

(

  39) *[ForceP [ClowP [TP Wǒmen qù diànyǐngyuàn kàn diànyǐng] ne ] ba]! 1PL go movie.theatre watch movie CLOW FORCE

  )): (43) [ Tā huì kāi fēijī ] ne! (Zhu Dexi 1982: 213) 3SG can drive airplane ATT '(Imagine) he can fly an airplane!' (44) Déguó yǔyánxuéjiā kě duō *(ne)! (Paul and Pan 2017: 55, (

( 46 )

 46 Tāmen yào wǔbǎi kuài qián bàle! Méi yǒu shénme liǎobùqǐ! 3SG want 500 CL money ATT NEG have what extraordinary 'They (only) want 500 dollars! That's nothing extraordinary!' Finally, ne3 as an Attitude head can co-occur with low Cs such as le and must follow them : (47) [AttP [ClowP [TP Shànghǎi de gōngyuán kě dà ] le ] ne ]! Shanghai SUB park really big CLOW ATT 'Shanghai's parks are really extremely big!

  did you just say) is your family name?' 'What was your family name?' (I forgot.) (NOT: What was your family name before?') (51b) [Wǒ yǐqián xìng Zhāng] (láizhe), xiànzài xìng Bāo. 1SG before call Zhang CLOW now call Bao 'My family name used to be Zhang, now it's Bao.'

  that only low Cs may occur in non-root clauses, to the exclusion of Force and Attitude heads, Pan (2019a: 109) substantiates the Attitude head status of láizhe in (50) by showing its unacceptability in embedded contexts such as relative clauses: (i) *[ DP [ AttP [ TP Tāmen liǎ shénme shíhou jié hūn ] láizhe] de wèntí ] bù qīngchǔ. 3PL two what time join marriage ATT SUB question NEG clear ('The question (*by the way) when will they get married is not really clear.') (Pan 2019a: 109, (40b))

  characterized the three SFPs ne1, le, láizhe as "expressing tense", based on the different interpretations obtained in the triple below, where the (bare) lexical predicate xià yǔ 'fall rain' remains constant and only the SFPs vary. Note that the SFPs are obligatory here, a fact not explicitly mentioned[START_REF] Zhu | Yǔfǎ jiǎngyì [On grammar[END_REF].5 Láizhe indicates that the event has occurred in the recent past. Le signals that the situation at hand is (conceived of as) new. 6 Ne1 expresses a continuing situation or state. Importantly, this is not tantamount to postulating tense as a verbal category for Chinese.

	(10) a. [ClowP [TP Xià yǔ ] ne	Zhu Dexi (1982: 209)
	fall rain CLOW
	'It's (still) raining.'
	(Zhu Dexi's comment: It was raining before.)
	b. Xià yǔ le fall rain CLOW '(Look), it's raining (now).' (Zhu Dexi's comment: It didn't rain before.)
	c. Xià yǔ láizhe fall rain CLOW 'It (just) rained.' (Zhu Dexi's comment: It rained a moment ago.)
	On the basis of these examples, Zhu Dexi (1982: 209) proposes the following interpretative
	values for the three SFPs.

  Zhu Dexi's example (19a) nicely illustrates both the very common co-occurrence of the aspectual suffix -le and the SFP le and the semantic import of le. Given that le relates the event to the speech time, (19a) with le unambiguously states that my living here still obtains at the speech time. By contrast, as pointed outby Zhu Dexi (1982: 209), (19b) without the SFP le implies my no longer living here.8 (20) illustrates that the meaning of a sentence with an SFP is derived in a clearly compositional way, with le as C having scope over the entire TP:

	b. Wǒ zài zhèr zhù -le wǔ nián.
	1SG at here live -PERF 5 year
	'I lived here for five years.'
	(20) [ClowP[TopP Nà	[Top'[TP wǒ jiù bù děng tā ] le ]]]
	in.that.case	1SG then NEG wait 3SG CLOW
	'In that case I will no longer wait for him.'
		Paul 2015: 276-277 for further discussion):
	(19) a. Wǒ zài zhèr zhù -le wǔ nián le.	(Zhu Dexi 1982: 209)
	1SG at here live -PERF 5 year CLOW
	'I have been living here for five years now.'

  22) a. Tā gāngcái hái zài bàngōngshì láizhe / *le. As shown in (22b-d), láizhe, like ne, excludes telic activity predicates (cf. (22b)), but is compatible with stative predicates (cf. (22c-d)).The approximate, "shorthand" characterization of láizhe as 'recent past' makes it very tempting to consider it as a genuine tense marker. However, there are at least two pieces of evidence challenging this idea. First, in a sentence with láizhe, the presence of (past) temporal adverbs and of aspect is in fact preferred:

	(23) a. Wàimiàn gāngcái xià-guo yǔ (láizhe).
	outside just	fall-EXP rain CLOW
	'It just rained a moment ago.'
	b. Tā {zuìjìn / shàng ge yuè} qù-guo gùgōng	(láizhe).
	3SG recently/last CL month go-EXP imperial.palace CLOW
	'She went to the imperial palace recently/ a month ago.'
				(Paul & Pan 2017: 58, (24))
	3SG just.now still at office	CLOW / CLOW
	'He was in his office just now.'
	b. [ClowP[TP Xiǎo Wáng cānguān/*líkāi gōngchǎng] láizhe] .
	Xiao Wang visit	/ leave factory	CLOW
	'Xiao Wang visited/left the factory.'
	c. Tā yǐqián xǐhuān wǒ láizhe
	3SG before like	1SG CLOW
	'She liked me before.'
	d. Tā qùnián hěn pàng láizhe.
	3SG last.year very fat CLOW
	'He was overweight last year.'

  ForceP 2.2.1. The yes/no question Force head ma2 The SFP ma2 indicating the yes/no question status of a sentence (cf. (26b)) was the first SFP to be analysed as a complementiser (cf. Lee Hun-tak Thomas 1986, Tang Ting-chi 1989: 540):The Force head status of ma is confirmed by its position above, i.e. to the right of, low Cs such as le (cf. (28a)) and ne (cf. (28b)): While (32a) with ma is a genuine information request, this is not the case for (32b) where a positive answer is expected. Accordingly, only baQconfirmation, but not ma is compatible with adverbs such as dàgài 'probably', yěxǔ 'perhaps', shuōbùdìng 'possibly, perhaps':

	(28a) [ForceP[ClowP[TP Tā bù chōu yān	] le ] ma]?
		3SG NEG inhale cigarette CLOW FORCE
	'Does he no longer smoke?' (28b) [ForceP[ClowP[TP Tā hái méi zǒu ] ne1 ] ma] ?! 3SG still NEG leave CLOW FORCE (33) [ Tā dàgài yǐjīng zǒu -le ] ba /*ma? 3SG probably already leave-PERF FORCE/ FORCE 'She has already left, I guess?'
	'Hasn't he left yet?!' (28c) Kuài le , kuài le , tā ná -wán shū mǎshàng quick CLOW quick CLOW 3SG take-finish book immediately then leave jiù zǒu. (34) [Xiànzài shuōbùdìng jìngguò-le shí'èr diǎn] le {ba /*ma}? now perhaps pass -PERF 12 o'clock CLOW FORCE/ FORCE 'It might very well be past twelve o'clock now?'
	'Almost there, almost there (i.e. 'He's nearly ready to leave), he finishes taking his books and then leaves at once.' When baQconfirmation occurs with declarative sentences, its conjecturing component results in a weakening of the assertion (cf. Hu Mingyang 1981: 416):
	As indicated by the question-plus-exclamation mark, (28b) requires an angry or surprised intonation and can be continued by another speaker's uttering (28c). (35) Nǐ tīngcuò-le ba. 2SG mishear-PERF FORCE 'You must have misheard.'/ 'You probably have misheard.'
	2.2.2. The Force head baQconfirmation: confirmation request or conjecture A yes/no question with baQconfirmation is not neutral, but implies the speaker's expectation to Being a Force head, ba -be it as question confirmation or conjecture -occurs above low Cs receive a positive answer to her/his request: such as le and ne1:
	(26) a. Tā huì shuō zhōngwén. (29) Jīntiān xīngqīsān ba? (36) a. [ForceP[ClowP[TP Sānshí nián qián hái méi yǒu shǔbiāo] ne1 ] ba]. (Zhu Dexi 1982 : 211) today Wednesday FORCE 30 year ago still NEG exist mouse CLOW FORCE 'It is Wednesday today, correct?' 'Thirty years ago there probably didn't exist any computer mice yet.' 3SG can speak Chinese 'He can speak Chinese.' b. [CPforce [TP Tā huì shuō zhōngwén] ma ]? (30) Nǐ xiànzài míngbái le ba ? (Paul &Pan 2017 : 67, (50)) (Yang-Drocourt 2007: 312) 2SG now understand CLOW FORCE 'You understand now, don't you?' b. [ForceP[ClowP[TP Èrshí nián qián fāmíng-le shǔbiāo] {le /*ne1 }] ba].
	3SG can speak Chinese It is this component of confirmation request which explains why baQconfirmation is incompatible with wh questions and yes/no question in the 'A-not-A' form, both being genuine information seeking questions.
	(31) a. * Shéi míngbái ba? who understand FORCE
	b.	* Nǐ míngbái bù míngbái ba? 2SG understand NEG understand FORCE
	(27) a. [TP Nǐ wèn-le shéi ] (*ma)? 2SG ask-PERF who FORCE Lü Shuxiang (2000: 57) provides neat minimal pairs where either both baQconfirmation and ma are possible (modulo the associated meaning differences) or where only baQconfirmation is acceptable:
	'Whom did you ask?' b . [TP Tā dǒng bù dǒng 3SG understand NEG understand problem FORCE wèntí ] (*ma)? (32) a. Zhèi zuò fángzi shì [xīn gài de] ma? this CL house be new build SUB FORCE 'Is this house a new one?
	'Does he understand the problem?' b. Zhèi zuò fángzi shì [xīn gài de ] ba ? this CL house be new build SUB FORCE

FORCE

'Can he speak Chinese?' Since ma turns a declarative sentence into a yes/no question, it must have scope over the entire sentence, whence the analysis of ma as a C-head taking a clausal complement (TP or ClowP, cf. (28) below). The complement status of TP and the head status of ma are confirmed by the fact that ma imposes selectional restrictions: it can only select a non-interrogative TP and is therefore incompatible with wh-questions (cf. (27a)) and TP-internal yes/no questions in the 'A-bù 'not'-A' form (cf. (27b)). 'This house is a new one, isn't it?'

  Again, the rigid ordering with respect to the low C le (cf. (37b) above) and the Attitude head ou (cf. (38) below) confirms the status of baIMP as a Force head in the second CP-layer:

	(38) Zǒu b'ou go SFP(fusion) FORCE+ATT. [= ba + ou] 'You better go!'	(Zhu Dexi 1982: 208)
		Hu Mingyang 1981: 416):
	(37) a. [ Kuài diǎnr zǒu] ba! quick a.bit go FORCE 'Better hurry up and go!'	(Chao Yuen Ren 1968: 807)
	b. [[[Bié chàng] le ] ba ]! NEG sing CLOW FORCE 'Better stop singing.'	(Hu Mingyang 1981: 416)

  [ TopP Quèshí/ qíshí [ Top' [ Top° ne ] [ TP tā de nénglì shì bǐ

			wǒ qiáng]]]
	indeed/ in.fact	TOP	3SG SUB ability be compared.to 1SG strong
	'Indeed/In fact, his abilities are greater than mine.'
	(ii) [ AttP [ ClowP [ TopP Nǐ [ Top' [ Top° ne] [ TP nǐ wèn shéi ] le ] ne ]?
	2SG	TOP	2SG ask who CLOW ATT
	'And you, whom have you asked?

Conjunctions in adverbial clauses also instantiate Cs and project a head-initial CP: rúguǒ 'if', jíshǐ 'even if', jiùsuàn 'even though', jìrán 'since', suīrán 'although', yīnwèi 'because' (cf.Pan & Paul 2018: 147). By contrast, Chinese lacks an embedding C equivalent to English that (cf. Paul 2015:

for further discussion).

This phonetic fusion only applies to spelt-out SFPs in the correct linear order (cf. the unacceptability of (7b), (8b)). It is limited to SFP 3 simply because only the latter consist of a single vowel.

For example,Cinque's (1999: 41) complete hierarchy of the functional projections hosting adverbs relies on the stepwise application of the relative order established for a given pair of adverbs, the full hierarchy not being attested.

Unlike statives, activity predicates must bear aspect markers for a non-habitual, episodic reading (cf.[START_REF] Kong | Yǐngxiǎng hànyǔ jùzi zìzú de yǔyán xíngshì [Linguistic forms that affect sentence completeness in Chinese[END_REF][START_REF] Sun | Temporal Construals of Bare Predicates in Mandarin Chinese[END_REF]. Otherwise, a low C is required (cf. Paul 2018).

"Conceived of as new" refers to the subjective perception of the speaker, i.e. (10b) is also compatible with a situation where it might have rained before, but that the speaker notices it only at this moment (henceLi & Thompson's (1981: 238) label "currently relevant state").

For some speakers (19b) might be ambiguous and then also has the reading in (19a).

This observation seemed worthwhile checking, given that the relevant literature is from 40 years ago (the first edition ofLü (2000) dating back to 1980).

Assertability in a root context is the most language general and theory neutral definition of finiteness. Furthermore, habituals and negation of events can be likened to states, as widely assumed in the literature.

(57) -( 61) show a sample of the sentences produced by the children (cf. The children distinguish between the low C ne1 in (59b) and the Attitude head ne3 in (58), with both sentences exactly corresponding to the target adult grammar. Their mastering of the Attitude head ma is particularly noteworthy, because this implies their contradicting the previous adult utterance and insisting on their own utterance as the only truthful statement.

Guo ( 2016) and Peng Lulu (2016) report similar results from three Beijing Mandarinspeaking children aged between 1;3 and 3;1; in general, SFPs are acquired by the age of 2 years. For reasons of space, we only illustrate phenomena not included in Tao Yu's sample.

(62) Méi diàn.

Méi diàn la ! [= le + a]! (ZZC 1;10;13) NEG electricity NEG electricity SFP-fusion CLOW + ATT 'There is no electricity. There is no electricity!' (Peng Lulu 2016: 118-119) According to Peng Lulu (2016), this fused form of the low C le and the Attitude head a is the first SFP acquired by the children in her sample. Given that the same children also produce sentences with the low C le (cf. (64a) below), they clearly know the difference between the two.