Olivier Bournez
email: olivier.bournez@lix.polytechnique.fr

Walid Gomaa
email: walid.gomaa@loria.fr

Emmanuel Hainry
email: emmanuel.hainry@loria.fr

Implicit complexity in recursive analysis

Recursive analysis is a model of analog computation which is based on type 2 Turing machines. Various classes of functions computable in recursive analysis have recently been characterized in a machine independent and algebraical context. In particular nice connections between the class of computable functions (and some of its sub and supclasses) over the reals and algebraically defined (sub-and sup-) classes of R-recursive functions à la Moore have been obtained. We provide in this paper a framework that allows to dive into complexity for functions over the reals. It indeed relates classical computability and complexity classes with the corresponding classes in recursive analysis. This framework opens the field of implicit complexity of functions over the reals. While our setting provides a new reading of some of the existing characterizations, it also provides new results: inspired by Bellantoni and Cook's characterization of polynomial time computable functions, we provide the first algebraic characterization of polynomial time computable functions over the reals.

Introduction

Building a well founded theory of computations over the reals is a crucial task. However, computation theory over the reals is not as well understood as classical discrete computation theory. In particular, unlike what happens for discrete computations where the Church-Turing thesis yields a clear equivalence between models, when talking about real or analog computations, several approaches have been developed, with various motivations, but with not so-clear relations. This includes the Blum-Shub-Smale model [START_REF] Blum | Complexity and Real Computation[END_REF][START_REF] Blum | On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines[END_REF], Shannon's General Purpose Analog Computer (GPAC) [START_REF] Shannon | Mathematical theory of the differential analyzer[END_REF], algebraically defined classes of functions over the reals à la Moore 96 [START_REF] Moore | Dynamical recognizers: real-time language recognition by analog computers[END_REF] (R-recursive functions), as well as the recursive analysis approach. Recursive analysis has been introduced by Turing [START_REF] Turing | On computable numbers, with an application to the Entscheidungsproblem[END_REF], Grzegorczyk [START_REF] Grzegorczyk | On the definitions of computable real continuous functions[END_REF], Lacombe [START_REF] Lacombe | Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles III[END_REF]. In this framework, a function f : R → R over the reals is considered as computable, if there is some computable functional, or Type 2 machine, that maps any sequence quickly converging to some x to a sequence quickly converging to f (x), for all x. That means that this notion of computability requires a priori to deal with functionals, or higher order Turing machines.

While there is no hope to unify the Blum-Shub-Smale approach with recursive analysis point of view, some recent works have shown strong connections between recursive analysis, Shannon's General Purpose Analog Computer model, and R-recursive functions. These results basically say that all these paradigms of computations are more or less equivalent: see [START_REF] Bournez | Polynomial differential equations compute all real computable functions on computable compact intervals[END_REF][START_REF] Bournez | Recursive analysis characterized as a class of real recursive functions[END_REF] or survey [START_REF] Bournez | New Computational Paradigms. Changing Conceptions of What is Computable, chapter A Survey on Continuous Time Computations[END_REF]. These results also provide machine independent descriptions of recursive analysis and of the GPAC which are both deeply rooted on machinery.

However, up till now discussions have mainly been restricted to the computability level, and not to complexity level. While there is a well developed and rather well understood theory of complexity for real computations (over compact domains) [START_REF] Ker | Complexity Theory of Real Functions[END_REF], talking about complexity for analog models of computations is often very problematic. One reason is that there is no robust and well defined notions of time and space for these models [START_REF] Moore | Dynamical recognizers: real-time language recognition by analog computers[END_REF][START_REF] Asarin | Reachability analysis of dynamical systems having piecewise-constant derivatives[END_REF][START_REF] Ruohonen | Event detection for ODEs and nonrecursive hierarchies[END_REF][START_REF] Bournez | New Computational Paradigms. Changing Conceptions of What is Computable, chapter A Survey on Continuous Time Computations[END_REF].

In this paper, we aim at providing a framework for implicit complexity in recursive analysis. We claim that this framework gives relations between recursive analysis and algebraical classes of functions over the reals at the complexity level. We also apply this framework to re-obtain results at the computability level. This framework is then both well founded and a step towards a sane complexity theory of functions over the reals.

To do so, we actually relate (polynomial-time) computable functions over the reals to (polynomial-time) computable functions over the integers, and provide some statements that allow to state that a class of functions over the reals that approximates in some defined sense computable functions over the integers yields naturally an algebraic characterization of the corresponding class over the reals.

First, our results provide a new understanding of some of the recent constructions relating recursive analysis to Shannon's General Purpose Analog Computer, and to R-recursive functions [START_REF] Bournez | Polynomial differential equations compute all real computable functions on computable compact intervals[END_REF][START_REF] Bournez | Recursive analysis characterized as a class of real recursive functions[END_REF].

Second, our results provide, to our knowledge, the first algebraic machineindependent characterization of polynomial time computable functions over the reals. Potential applications include the possibility of proving whether a given function can be computed in polynomial time without resorting to effectively program it.

More concretely, we first express how recursive analysis relates the notion of (polynomial-time) computable functions over the integers to the corresponding notion over the reals. While the obtained results can be seen as rather basic, they yield a direct understanding of how algebraic characterizations of computability and complexity classes over the integers can be lifted to algebraic characterizations of corresponding classes over the reals.

Indeed when talking about computability and complexity over the integers, several machine-independent characterizations of computable functions are known [START_REF] Clote | Computational models and function algebras[END_REF]: in particular, Kleene's functions are well known to be exactly the functions computable by Turing machines. Cobham [START_REF] Cobham | The intrinsic computational difficulty of functions[END_REF], and later Bellantoni and Cook [START_REF] Bellantoni | A new recursion-theoretic characterization of the polytime functions[END_REF] were among the first to propose algebraically defined characterizations of polynomial time computable functions. See survey [START_REF] Clote | Computational models and function algebras[END_REF] for some other machine independent characterizations of classical computability and complexity classes over the integers.

Our setting is actually proved to be robust to approximations: one does not need to be able to compute exactly the corresponding class over the integers, but only some defined approximation of it to be able to compute the corresponding class over the reals. This provides a way to reformulate/reprove/reread very nicely some constructions already used in [START_REF] Bournez | Polynomial differential equations compute all real computable functions on computable compact intervals[END_REF][START_REF] Bournez | Recursive analysis characterized as a class of real recursive functions[END_REF].

Notice that our framework is definitively different from the one proposed by Campagnolo and Ojakian in [START_REF] Manuel | The methods of approximation and lifting in real computation[END_REF], and has the main advantage to allow to talk not only about the computability level but also about the complexity level. It should be also noted that although recursive analysis can be seen as a specific type 2 computation, our characterisation relies exclusively on functions on the reals and hence cannot be compared with approaches such as [START_REF] Kapron | A new characterization of type-2 feasibility[END_REF]. Algebraic characterizations of functions over more general domains, including the reals, have been obtained in [START_REF] Brattka | Computability over topological structures[END_REF]. However, the obtained characterization in this latter paper is rather different in spirit to the ones discussed here: on one hand, a more abstract setting that is not restricted to real functions is considered there, but on the other hand the discussion is also restricted to the computability level, and less close in spirit to above mentioned models of analog computations.

Potential applications include the possibility of proving whether a given function can be computed in polynomial time without resorting to effectively program it, as well as the possibility of building methods to automatically derive computational properties of programs/systems, in the lines of [START_REF] Hofmann | Type systems for polynomial-time computation[END_REF][START_REF] Neil | The expressive power of higher-order types or, life without CONS[END_REF][START_REF] Marion | Efficient first order functional program interpreter with time bound certifications[END_REF] for discrete programs.

Basic Definitions from Recursive Analysis

We first recall some definitions from recursive analysis [START_REF] Weihrauch | Computable Analysis: an Introduction[END_REF][START_REF] Ker | Complexity Theory of Real Functions[END_REF].

Let D = {r ∈ Q : r = a 2 b f or integers a, b} (these are the rationals with finite binary representation). We adopt the following representation of real numbers. Definition 1. Assume x ∈ R. Then x can be represented by a Cauchy sequence ϕ x : N → D that converges at a binary rate:

∀n ∈ N : |x -ϕ x (n)| ≤ 2 -n . (1)
Given x ∈ R, let CF x denote the class of Cauchy functions that represent x.

Definition 2. (Modulus of continuity)

1. Assume a function f : [0, 1] → R. Then f has a modulus of continuity if there exists a function m : N → N such that for all x, y ∈ [0, 1] and for all n ∈ N:

if |x -y| ≤ 2 -m(n) , then |f (x) -f (y)| ≤ 2 -n .
2. Assume a function f : [0, ∞) → R. Then f has a modulus of continuity if there exists a function m : N 2 → N such that for all k, n ∈ N and for all x, y ∈ [0, 2 k ] the following holds

: if |x -y| ≤ 2 -m(k,n) , then |f (x) -f (y)| ≤ 2 -n .
The notions of computability and complexity of real functions have been characterized as will be shown below.

Definition 3. Assume a function f : I → R where I is either [0, 1] or [0, ∞).
We say that f is computable if there exists a function-oracle Turing machine M () such that for every x ∈ I, for every ϕ x ∈ CF x , and for every n ∈ N the following holds:

|M ϕx (n) -f (x)| ≤ 2 -n . (2)
Notice that we need to talk about functions defined over unbounded (noncompact) domains, unlike what is done for example in [START_REF] Ker | Complexity Theory of Real Functions[END_REF]: Computability over compact domains is characterized by the existence of a computable modulus and a computable approximation function (see corollary 2.14 in [START_REF] Ker | Complexity Theory of Real Functions[END_REF]). Computability over unbounded domains can be characterized in a similar way as indicated by the following proposition.

Proposition 1. Assume a function f : [0, ∞) → R. Then f is computable iff there exist two computable functions m : N 2 → N and ψ : D ∩ [0, ∞) × N → D such that 1. m is a modulus of continuity for f , 2. ψ is an approximation function for f , that is, for every d ∈ D ∩ [0, ∞) and every n ∈ N the following holds: |ψ(d, n) -f (d)| ≤ 2 -n .
Proof. The proof is a simple extension of the proof of Corollary 2.14 in [START_REF] Ker | Complexity Theory of Real Functions[END_REF].

Definition 4. (Polynomial time complexity of real functions)

1. Assume a function f : [0, 1] → R. Then f is polynomial time computable if it is computable in the sense of Definition 3, and there exists an oracle machine N () (n) that computes f whose computation time is bounded by p(n)

for some polynomial function p.

Assume a function

f : [0, ∞) → R. Then f is polynomial time computable
if it is computable in the sense of Definition 3, and there exists an oracle machine N

() (n) that computes f (x) whose computation time is bounded by q(k, n) for some polynomial q where k = min{j : x ∈ [0, 2 j ]}.
For a domain that is a combination of compact and unbounded components computability/complexity can be defined and characterized in the obvious way.

The following proposition characterizes polynomial time computability of real functions over unbounded domains. Using an extension of Theorem 2.19 in [START_REF] Ker | Complexity Theory of Real Functions[END_REF] the proof is similar to that of Proposition 1.

Proposition 2. Assume a function

f : [0, ∞) → R. Then f is polynomial time computable iff there exist two functions m : N 2 → N and ψ : D ∩ [0, ∞) × N → D such that
1. m is a modulus function for f and it is polynomial with respect to both the extension parameter k and the precision parameter

n, that is, m(k, n) = O((k + n) a ) for some a ∈ N. 2. ψ is an approximation function for f , that is, for every d ∈ D ∩ [0, ∞) and
for every n ∈ N the following holds:

|ψ(d, n) -f (d)| ≤ 2 -n (3) 3. ψ(d, n) is computable in time p(|d| + n) for some polynomial p.

Transferring Computability and Complexity over The Integers to the Reals

Proofs of some of the results in this section can be found in the appendix.

General Case

We now state some results that yield ways to transfer notions of computability/complexity over the integers to corresponding notions over the reals.

We first give a way to relate computability over some compact domain to computability over this domain times reals.

Proposition 3 (Computability over I vs Computability over I ×R). The following are equivalent.

a function

f : [0, 1] → R is computable 2. there exists a computable function g : [0, 1] × R ≥0 → R such that ∀x ∈ [0, 1], ∀y ∈ R ≥0 : |g(x, y) -yf (x)| ≤ 1 (4)
3. there exists a computable function g

: [0, 1] × R ≥0 → R such that, ∀x ∈ [0, 1], ∀y ∈ N : |g(x, y) -yf (x)| ≤ 1 (5)
These statements works fine also at the complexity level5 :

Proposition 4 (Complexity over I vs Complexity over I × R). The following are equivalent:

1. a function f : [0, 1] → R is polynomial time computable, 2.
there exists a polynomial time computable function g : [0, 1] × R ≥0 → R such that (4) holds.

there exists a polynomial time computable function

g : [0, 1] × R ≥0 → R such that (5) holds.

Lispchitz Functions

For Lipschitz functions, it is possible to relate computability over compact domains to computability over R 2 .

Proposition 5 (Computability over I vs Computability over R 2 ). Fix an arbitrary constant ǫ. Assume a function f : [0, 1] → R that is Lipschitz. Then the following are equivalent:

1. f is computable 2. there exists some computable function g :

R ≥0 × R ≥0 → R such that ∀x ∈ N, ∀y ∈ N ≥1 , x ≤ y : |g(x, y) -yf ( x y )| ≤ ǫ (6)
This can still be transfered at the complexity level

Avoiding the Lispchitz Hypothesis

This is indeed possible to avoid the Lipschitz hypothesis, and to yet talk about complexity, at the price of a little bit of complications.

Definition 6 (# k ). Fix some integer k. Denote by # k the function

# k : R ≥1 → R ≥0 defined by # k [x] = 2 ((log 2 x) k ) .

Definition 7 (Polynomial Time Computable Integer Approximation).

A function g : R d → R is said to have a polynomial time computable integer approximation if there exists some polynomial time computable function h :

N d → N with |h(x) -⌊g(x)⌋| ≤ 1 for all x ∈ N d .
We then have.

Proposition 7 (Complexity over I vs Complexity over R 2 ). Fix an arbitrary constant ǫ. The following are equivalent.

1. a function f : [0, 1] → R is computable 2. there exists some function g : R ≥0 × R ≥0 → R such that (a) g has a polynomial time computable integer approximation (b) for some integer k,

∀x ∈ [0, 1], ∀y ∈ R ≥1 : |g(x.# k [y], y) -yf (x)| ≤ ǫ, (8)
(c) for some integer M ,

∀x 1 , x 2 ∈ R ≥0 , y ∈ R ≥1 : |x 1 -x 2 | ≤ 1 ⇒ |g(x 1 , y) -g(x 2 , y)| ≤ M (9)
Notice that ( 8) is equivalent to (6) for k = 1, by some obvious change of variable.

Proof. (2) ⇒ (1) : For simplicity, assume ǫ = 1. Assume there exists a function g that satisfies the above conditions. Assume some x ∈ [0, 1] and n ∈ N. Let y = 2 n . From condition (2b) we have

|g(2 n k x, 2 n ) -2 n f (x)| ≤ 1 |2 -n g(2 n k x, 2 n ) -f (x)| ≤ 2 -n (10)
Let h be some polynomial time computable function with |h(x, y)-⌊g(x, y)⌋| ≤ 1 for all x, y ∈ N that exists by (2a).

Then

|g(⌊2 n k x⌋, 2 n ) -h(⌊2 n k x⌋, 2 n )| ≤ 2 (11)
From (2c) we have

|g(⌊2 n k x⌋, 2 n ) -g(2 n k x, 2 n )| ≤ M (12)
From the previous two equations

|g(2 n k x, 2 n ) -h(⌊2 n k x⌋, 2 n )| ≤ M + 2 |2 -n g(2 n k x, 2 n ) -2 -n h(⌊2 n k x⌋, 2 n )| ≤ 2 -n (M + 2) (13)
From Equations ( 10) and ( 13)

|f (x) -2 -n h(⌊2 n k x⌋, 2 n )| ≤ 2 -n (M + 3) (14)
This gives an approximation to f (x) to within the desired precision 2 -n . The computation time of h(⌊2 n k x⌋, 2 n ) is bounded by p(n) for some polynomial p, hence, f (x) is polynomial time computable.

(1) ⇒ (2) : Assume that f : [0, 1] → R is polynomial time computable. Hence f has a polynomial modulus m(n) = n k for some constant k ∈ N. Define g as follows:

g(x, y) = yf ( x # k [y] ) x ≤ # k [y], y ≥ ǫ yf (1) otherwise (15)
Then for every x ∈ [0, 1] and y ∈ R ≥1 we have

|g(x.# k [y], y) -yf (x)| = 0 ≤ 1, hence condition (2b) is satisfied. Now assume x 1 , x 2 ∈ R ≥0 , y ∈ R ≥1 such that |x 1 -x 2 | ≤ 1.
There are three cases. case 1:

x 1 ≤ # k [y] and x 2 ≤ # k [y], then |g(x 1 , y) -g(x 2 , y)| = |yf ( x 1 # k [y] ) -yf ( x 2 # k [y] )| = y|f ( x 1 # k [y] ) -f ( x 2 # k [y] )| We have | x1 # k [y] -x2 # k [y] | = 1 # k [y] |x 1 -x 2 | ≤ 1 # k [y] = 2 -(log 2 y) k . Hence, using the modulus of continuity of f , |f ( x1 # k [y] ) -f ( x2 # k [y] )| ≤ 2 -log 2 y = 1 y implying |g(x 1 , y) -g(x 2 , y)| ≤ 1 and condition (2c) is satisfied for M = 1. case 2: x 1 > # k [y] and x 2 > # k [y], then |g(x 1 , y) -g(x 2 , y)| = |yf (1) -yf (1)| = 0 and condition (2c) is satisfied for M = 1. case 3: x 1 ≤ # k [y] and x 2 > # k [y], then |g(x 1 , y) -g(x 2 , y)| ≤ |g(x 1 , y) -g(# k [y], y)| + |g(# k [y], y) -g(x 2 , y)| ≤ 1 + 0 = 1
by above two cases, and hence condition (2c) is satisfied for M = 1.

Note that all division, multiplication, and f are all computable. Hence, g is computable.

Assume i, j ∈ N such that i ≤ # k [j]. Then g(i, j) = jf ( i # k [j] ). The computation of the floor of the last function involves the following:

1. Shift left the binary representation of i by |j| k positions. The result would be a dyadic rational d. 2. Simulate the computation of f (d) assuming large enough though fixed precision. When simulating the oracle d is presented exactly. 3. Multiply the output of the previous step by j. Finally, truncate the result to extract the integer part.

All of these steps can be performed in polynomial time. The fixed precision of step 2 can be calculated from the modulus of f . Since the output of step 2 is an approximation there is a possibility that the floor is computed with an error that can be bounded by 1. The case when i > # k [j] is similar. Hence, Condition (2a) is satisfied.

For ease of notation, let's consider that interval

[a, b] is [b, a] if b < a. Definition 8 (Peaceful Functions). -A function g : R ≥0 × R ≥0 → R ≥0 is said to be peaceful if ∀x ∈ R ≥0 , ∀y ∈ N ≥1 , : g(x, y) ∈ [g(⌊x⌋, y), g(⌈x⌉, y)]. (16)
-We will say that a class C of functions peacefully approximates some class D of functions, if the class of peaceful functions from C approximates D.

Theorem 3 (Complexity over I vs Approximate Complexity over N 2 ).

Consider a class C of functions that peacefully approximates polynomial time computable discrete functions, and whose functions have polynomial time computable integer approximation 6 . Then the following are equivalent.

1. a function f : [0, 1] → R is polynomial time computable, 2. there exists some peaceful function g ∈ C such that (a) for some integer k,

∀x ∈ N, ∀y ∈ N ≥1 , x ≤ # k [y] : |g(x, y) -yf ( x # k [y] )| ≤ 3, ( 17
) (b) for some integer M , ∀x, x ′ ∈ R ≥0 ,∀y ∈ R ≥1 , x, x ′ ≤ # k [y], |x -x ′ | ≤ 1 : y|f ( x # k [y] ) -f ( x ′ # k [y] )| ≤ M ( 18
)
Remark 1. Condition (2b) is a property of function f , and hence is a necessary condition to get computability of f .

Proof. (1) ⇒ (2) : by Proposition 7 for ǫ = 3/4, there exists some function g with a polynomial time computable integer approximation h such that (8) holds. Now, by hypothesis, there exists some peaceful h ∈ C such that

∀x, y ∈ N : | h(x, y) -h(x, y)| ≤ 1/4 Hence ∀x, y ∈ N : | h(x, y) -⌊g(x, y)⌋| ≤ 1 + 1 4 = 5 4 ( 19
)
We have |g(x, y) -⌊g(x, y)⌋| ≤ 1, then | h(x, y) -g(x, y)| ≤ 9 4 , for all x, y ∈ N. Finally, we have (through change of variables in Eq. ( 8))

∀x ∈ N, ∀y ∈ N ≥1 , x ≤ # k [y] : | h(x, y) -yf ( x # k [y] )| ≤ 9 4 + 3 4 = 3 (20)
Now, by (2c) of Proposition 7, we know that for all x, y ∈ N, δ ∈ [0, 1], |g(x + δ, y) -g(x, y)| ≤ M for some integer M . From Eq. ( 8), clearly condition (2b) must hold.

(2) ⇒ (1) : This follows from Proposition 7 with ǫ = 3, observing that the peacefulness of g and condition (2b) implies condition (2c) of Proposition 7.

The previous theorems can be generalized to any complexity class as indicated by the following corollary. Consider a class C of functions that peacefully approximates discrete functions computable in time D; and whose functions have integer approximations computable in time D 7 .

Then the following are equivalent.

a function

f : [0, 1] → R is computable in time D, 2.
there exists some peaceful function g ∈ C such that (a) for some

T ∈ D ∀x ∈ N, ∀y ∈ N ≥1 , x ≤ # T [y] : |g(x, y) -yf ( x # T [y] )| ≤ 3, (21)
(b) for some integer M , ∀x, x ′ ∈ R ≥0 ,∀y ∈ R ≥1 , x, x ′ ≤ # T [y], |x -x ′ | ≤ 1 : y|f ( x # T [y] ) -f ( x ′ # T [y] )| ≤ M (22)
Proof. The proof is similar to that of the previous theorem. It should be noted that if f is computable in time bounded by D then it has a modulus in D. This is a direct consequence of Theorem 2.19 in [START_REF] Ker | Complexity Theory of Real Functions[END_REF].

Applications

We now present applications of our previous theorems and corollaries to characterize algebraically some computability and complexity classes of functions over the reals. The main new results of this sections are theorems 4 and 5 which give characterizations of polynomial-time computable functions on the reals as the functions described by a specific class W.

To do so, we propose the following terminology.

Definition 9 (Definability). Let C be a class of functions from

R ≥0 × R ≥0 → R ≥0 . A function f : [0, 1] → R is said to be C-definable if there exists some total function g ∈ C such that: ∀x ∈ N, ∀y ∈ N ≥1 , x ≤ y : |g(x, y) -yf ( x y )| ≤ 3 (23)
Let T be a function from N to N.

Definition 10 (T, M -Bounded). A function f : [0, 1] → R is said to be T, M - bounded if ∀x, x ′ ∈ R ≥0 ,∀y ∈ R ≥1 , x, x ′ ≤ # T [y], |x -x ′ | ≤ 1 : y|f ( x # T [y] ) -f ( x ′ # T [y] )| ≤ M (24)
Definition 11 (T -Definability). Let C be a class of functions from

R ≥0 × R ≥0 → R ≥0 . A function f : [0, 1] → R is said C-T -definable if there exists some total function g ∈ C such that ∀x ∈ N, ∀y ∈ N ≥1 , x ≤ # T [y] : |g(x, y) -yf ( x # T [y] )| ≤ 3 (25)

GPAC, Polynomial IVP, and computable functions

The General Purpose Analog Computer, introduced by Claude Shannon in [START_REF] Shannon | Mathematical theory of the differential analyzer[END_REF] to model a mechanical device, consists of circuits interconnecting basic blocks that can be constants, adders, multipliers, and integrators. GPAC computable functions have been characterized in different ways since the creation of this model. In the following, we will use Graça and Costa's characterization by PIVP (Polynomial Initial Value Problems) [START_REF] Graça | Analog computers and recursive functions over the reals[END_REF].

Definition 12. A function is said to be PIVP if it is a component of the solution of a differential equation of the following form:

y(t 0 ) = y 0 y ′ (t) = p(t, y)
with y : R n → R and p is a vector of polynomials.

Lemma 1 ([14]

). A function is generated by a GPAC iff it is PIVP.

Lemma 2 ( [START_REF] Graça | Robust simulations of Turing machines with analytic maps and flows[END_REF]). PIVP functions is a class of computable functions that peacefully approximates total (discrete) recursive functions.

Proof. It is proved in [START_REF] Graça | Robust simulations of Turing machines with analytic maps and flows[END_REF] than Turing machines can be robustly simulated by PIVP functions. Robust means that even with noise (that does not exceed 1/4) the computation is conducted satisfactorily. This lemma implies that discrete functions that are computable can be generated by GPACs with precision 1 4 . Hence the class of PIVP functions approximates the discrete recursive functions.

We get the following corollaries (that can be seen as a new reading of [START_REF] Bournez | Polynomial differential equations compute all real computable functions on computable compact intervals[END_REF]) as a direct application of Theorem 1 and Corollary 1.

Proposition 8. A Lipschitz function f : [0, 1] → R is computable iff it is PIVP- definable.
Proposition 9. Let f : [0, 1] → R be some T, M -bounded function, for some total recursive function T . Then f is computable iff it is PIVP-T -definable.

Real recursive functions revisited

Some characterizations of computable functions in the context of real recursive functions [START_REF] Moore | Dynamical recognizers: real-time language recognition by analog computers[END_REF] are already known, see for example [START_REF] Bournez | Recursive analysis characterized as a class of real recursive functions[END_REF][START_REF] Manuel | The methods of approximation and lifting in real computation[END_REF]. They make use of limits that have restrictive constraints. We can dispense with those limits by using theorem 1 with a simpler class of functions. Definition 13. Let L µ be the smallest set of functions containing 0, 1, projections, θ 3 : max(0, x 3 ) and closed under the operations of composition, controlled linear integration (CLI) and unique minimization (UMU).

CLI is defined for functions g, h and c, with the norm of the first partial derivative of h bounded by c, as a solution to the following differential equation ∂ y f (x, y) = h(x, y)f (x, y) with initial condition f (x, 0) = g(x).

Given a differentiable function f : D × I ⊆ R k+1 → R where D × I is a product of closed intervals, if for all x ∈ D, y → f (x, y) is a non-decreasing function with a unique root y 0 that lies in the interior of I and

∂ y f | (x,y0) > 0, then UMU(f) is defined as D -→ R x → y 0 Lemma 3 ([7]
). Functions in L µ is a class of computable functions that peacefully approximate total recursive functions.

We get from Theorem 1 and Corollary 1.

Proposition 10. A Lipschitz function f : [0, 1] → R is computable iff it is L µ -definable.
Proposition 11. Let f : [0, 1] → R be some T, M -bounded function, for some total recursive function T . Then f is computable iff it is L µ -T -definable.

Similarly, we know that this class without the UMU operator closely matches discrete elementary functions. Definition 14. Let L be the smallest set of functions containing 0, 1, -1, π, projections and θ 3 and closed under composition and controlled linear integration.

Lemma 4 ([9]

). L is a class of total functions computable in elementary time that peacefully approximates total discrete elementary computable functions.

We get from a generalization of Theorem 2 and Corollary 1.

Proposition 12. A Lipschitz function f : [0, 1] → R is computable in elemen- tary time iff it is L-definable. Proposition 13. Let f : [0, 1] → R be some T, M -bounded function, for some elementary function T . Then f is computable in elementary time iff it is L-T - definable.

Polynomial Time Computable Functions

We define a class of polynomial time computable real functions. These functions are essentially extensions to R of the Bellantoni and Cook class [START_REF] Bellantoni | A new recursion-theoretic characterization of the polytime functions[END_REF]. Definition 15. Define functions algebra W = [0, U, s 0 , s 1 , pr 0 , pr 1 , θ 1 , e, o; SComp, SI, Lin] 1. a zero-ary function for the constant 0, 0(; ) = 0, 2. a set of projection functions U m+n i (x 1 , . . . , x m ; x m+1 , . . . , x m+n ) = x i , 3. successor functions, s i (; x) = 2x + i for i ∈ {0, 1}, 4. two predecessor functions Notice that for simplicity we misused the basic functions so that their arguments are now in normal positions (the alternative is to redefine a new set of basic functions with arguments in normal positions). 9. A linearization operator Lin: given functions g, h, define a new function f by f (x, ȳ; z) = δh(2pr 0 (x; ) + 1, ȳ; z) + (1 -δ)g(2pr 0 (x; ), ȳ; z) e(; x) ≥ o(; x) δ ′ g(2pr 1 (x; ), ȳ; z) + (1 -δ ′ )h(2pr 1 (x; ) -1, ȳ; z) o(; x) ≥ e(; x) where δ = x -2pr 0 (x; ), δ ′ = x + 1 -2pr 1 (x; ).

pr 0 (; x) = n 2n ≤ x ≤ 2n + 1, n ∈ N n + (ǫ -1) 2n + 1 ≤ x ≤ 2n + ǫ, 1 ≤ ǫ ≤ 2 pr 1 (; x) = n + ǫ 2n ≤ x ≤ 2n + ǫ, 0 ≤ ǫ ≤ 1 n + 1 2n + 1 ≤ x ≤ 2n + 2 5
By induction the following can easily be shown.

Proposition 14. Every function in W is polynomial time computable.

From the fact that the built functions contain piecewise linear extensions to R of the Bellantoni and Cook class [START_REF] Bellantoni | A new recursion-theoretic characterization of the polytime functions[END_REF], we have.

Proposition 15. Every polynomial time computable discrete function has a peaceful extension in W.

We get from Theorem 2 and and Corollary 1. (2) ⇒ (1) : Since g is computable, there exists an oracle machine N () which computes g. Assume an input x ∈ [0, 1] and a Cauchy sequence ϕ x ∈ CF x .

Assume n ∈ N and consider an oracle machine M ϕx (n) that does the following:

1. Simulate the operation of N ϕx,ϕy (0) (for any oracle ϕ y ), 2. Whenever N () queries ϕ x (i), M () queries its own oracle and returns d = ϕ x (i). Whenever N () queries ϕ y (j), M () returns 2 n+1 .

3. Repeat the last step as long as N () keeps querying, 4. Let e be the output of N () . Output 2 -(n+1) e.

From this procedure we have

|e -g(x, 2 n+1 )| ≤ 1 |2 -(n+1) e -2 -(n+1) g(x, 2 n+1 )| ≤ 2 -(n+1) (26)
From the proposition hypothesis: (2) ⇒ (3) : Obvious.

|g(x, 2 n+1 ) -2 n+1 f (x)| ≤ 1 |2 -(n+1) g(x, 2 n+1 ) -f (x)| ≤ 2 -(n+1) (27)
(3) ⇒ (1) : Same as the proof (2) ⇒ (1) since the value of y used in this proof, namely 2 n+1 , is a natural number.

A.2 Proof of Proposition 4

Proof. The proof is similar to that of Proposition 3 only replacing computability by polynomial time computability and observing: (1) multiplication can be done in polynomial time and (2) the procedure given in Proposition 3 is actually polynomial time computable in terms of the precision parameter n.

Corollary 1 .

 1 Let D be some class of functions from N to N above the class of polynomial functions and closed under composition. For a function T ∈ D, consider # T as the function # T : R ≥1 → R ≥0 defined by # T [x] = 2 (T (log 2 x)) .

Theorem 4 .Theorem 5 .

 45 A Lipschitz function f : [0, 1] → R is polynomial-time computable iff it is W-definable. Let f : [0, 1] → R be some n k , M -bounded function for some k. Then f is polynomial-time computable iff it is W-n k -definable.A ProofsA.1 Proof of Proposition 3Proof. (1) ⇒ (2) : is obtained directly by letting g(x, y) = yf (x).

26 ≤ 2 -

 262 Then |M ϕx (n) -f (x)| ≤ |M ϕx (n) -2 -(n+1) g(x, 2 n+1 )| + |2 -(n+1) g(x, 2 n+1 ) -f (x)| = |2 -(n+1) e -2 -(n+1) g(x, 2 n+1 )| + |2 -(n+1) g(x, 2 n+1 ) -f (x)| ≤ 2 -(n+1) + |2 -(n+1) g(x, 2 n+1 ) -f (x)| from Inequality (n+1) + 2 -(n+1) from Inequality 27 ≤ 2 -n

Or at any level above polynomial time. That is to say, polynomial time computable can be replaced by computable in elementary time in following proposition for example.

A sufficient condition for that is that restrictions to integers of functions from C are polynomial time computable.

A sufficient condition for that is that restrictions to integers of functions from C are computable in time D.

and piecewise linear for non-integer values. Clearly, g is computable and satisfies (6).

(2) ⇒ (1) : For simplicity assume ǫ = 1. Since f is Lipschitz there exists a nonnegative constant M such that for all x, y ∈ [0, 1] the following holds:

Hence, for all x, y ∈ [0, 1] the following holds: |f (x) -f (y)| ≤ 2 a |x -y|. Since g is computable, there exists an oracle machine N () which computes g. Assume an input x ∈ [0, 1] and a Cauchy function ϕ x ∈ CF x . Assume n ∈ N and consider an oracle machine M ϕx (n) that does the following:

hence, it can be assumed without loss of generality that (for example by truncating extra bits),

Repeat the last step as long as N () keeps querying, [START_REF] Bournez | Polynomial differential equations compute all real computable functions on computable compact intervals[END_REF]. Let e be the output of N () . Output 2 -n ′ e.

Then

From ( 6) with ǫ = 1

From Inequalities (29) and (30) we have

From the fact that f is Lipschitz we have

From Inequalities (31) and (32) we have

This completes the proof that f is computable.

A.4 Proof of Proposition 6

Proof. Similar to the proof of Proposition 5 replacing computability by polynomial time computability.

A.5 Proof of Theorem 1

Proof. (1) ⇒ (2) : by Proposition 5, there exists some computable g such that (6) holds with ǫ = 3 4 . Computing g with precision 1/2 , one can easily build some total recursive function h : N 2 → N such that |h(x, y) -⌊g(x, y)⌋| ≤ 1. Then h is total recursive, and hence by hypothesis there exists some g ∈ C such that

We have |g(x, y) -⌊g(x, y)⌋| ≤ 1, then |g(x, y) -g(x, y)| ≤ Proof. Similar to the proof of Theorem 1 replacing computability by polynomial time computability.


Fabienne Martin

Hongyuan Sun

Liu Jinhong

Hamida Demirdache

On the Zero-Change Construal of Causative Simple Verbs in Mandarin Chinese

2 Lin (2004) already acknowledges the existence of exceptions to his generalization that no SVs are change-of-state verbs in Mandarin. Tham (2019) also acknowledges the existence of change-of-location SVs as well as change-of-state SVs, albeit underlining that they are few. The existence of causative SVs is also argued for by Han (2007, p. 178 & section 6.6.2).

. This issue, not addressed here for lack of space, is taken up in Martin et al. (2020b).

On the zero-change construal of causative simple verbs in Mandarin Chinese Fabienne Martin, Hongyuan Sun, Jinhong Liu and Hamida Demirdache 1 On the typology of simple verbs in Mandarin

In a tradition going back to [START_REF] Tai | On the equivalent of 'kill' in Mandarin Chinese[END_REF] and defended by [START_REF] Talmy | Path to realization: A typology of event conflation[END_REF][START_REF] Talmy | Toward a cognitive semantics, vol. 2: Typology and process in concept structuring[END_REF] or [START_REF] Chen | Interpreting state-change: Learning the meaning of verbs and verb compounds in Mandarin[END_REF][START_REF] Chen | When transparency doesn't mean ease: Learning the meaning of resultative verb compounds in Mandarin Chinese[END_REF] among others, Mandarin simple verb (henceforth SV) counterparts of English lexical causatives such as shāo 'burn', guān 'close' do not have a causative meaning.1 Rather these SVs are taken to denote a set of activities performed in order to trigger a certain result state in the theme's referent, though, crucially, the result state itself is not part of the SV's denotation. Thus for instance, [START_REF] Chen | When transparency doesn't mean ease: Learning the meaning of resultative verb compounds in Mandarin Chinese[END_REF] translates Mandarin SVs such as guān by 'do.closing' rather than by 'close', precisely to convey the idea that these SVs are activity verbs devoid of causative semantics. Mandarin SVs such as shāo 'burn', guān 'close' thus behave like transitive activity (manner) verbs of a particular subtype, namely those that defeasibly implicate the occurrence of a result state that obtains when the event described is successful [START_REF] Talmy | Toward a cognitive semantics, vol. 2: Typology and process in concept structuring[END_REF][START_REF] Brisson | The Licencing of Unexpressed Objects in English Verbs[END_REF][START_REF] Hovav | Building verb meanings[END_REF]. Wash and wipe are paradigmatic examples of such verbs, as illustrated in (1) for English and in (2) for Mandarin. The result state implicated in (1)-( 2) is that of being clean(er). This expected/result state is 'conceptually associated' and 'pragmatically favored', but not entailed, since its occurrence can be denied without yielding a contradiction. We call this class of activity verbs 'Result-State (RS) oriented activity verbs'.

(1) Peter washed the window, but it is as dirty as before! In this paper, we contest the position that Mandarin SVs such as shāo 'burn', guān 'close' and shā 'kill' have a radically different meaning from their English counterparts and should be collapsed into one class with RS-oriented activities. Although this position is not in of itself novel 2 , what is new and will come perhaps as a surprise are the arguments that we bring to bear on this issue. Indeed, we will argue that so-called failed-attempt construals [START_REF] Tatevosov | Subevental structure and non-culmination[END_REF] which we refer to as zero-change construals, provide compelling evidence for the existence of causative SVs, while in the literature, the mere availability of zero-change readings is typically taken as an argument against the existence of causative SVs. This construal is illustrated with the Mandarin sentences in (3)-( 4) built with the perfective marker le and a monomorphemic SV, respectively shāo 'burn' and shā 'kill'. The first clause in (3) with the perfective accomplishment VP shāo yì-gēn mùtou 'burn a piece of wood' by default implicates that the piece of wood was successfully burnt, but as the second clause explicitly states, it can also be used to describe an event that does not cause any state of the wood being burnt, since the piece of wood in question did not undergo any burning whatsoever. The first clause of (4) with the prototypical causative verb 'kill' by default implicates that several killing attempts ended up provoking the death of the chicken, but event culmination is not entailed, since the death of the chicken can be explicitly denied in the subsequent clause without yielding a contradiction. The fact that perfective sentences built with SVs such as shāo 'burn', shā 'kill' or guān 'close' fail to entail the occurrence of a result state has also been experimentally established by [START_REF] Liu | Non-culminating accomplishments in child and adult Chinese[END_REF]; the corpus data gathered in [START_REF] Chief | Scalarity and incomplete event descriptions in Mandarin Chinese[END_REF] and Chen (2018) also corroborate this conclusion. We nonetheless argue that shā 'kill' have causative meanings in Mandarin, just as their English counterparts have, and in so doing, distinguish causative SVs associated with a complex event structure, from activity SVs associated with a simplex event structure, in Mandarin just like in English. Figure 1 recapitulates the finer-grained typology of SVs in Mandarin that we propose. We probe the meaning and (simple vs. complex) event structure of these classes of SVs in Mandarin through the diagnostics presented in sections 4 to 6.

2 Degree of change vs. degree of event realization [START_REF] Koenig | Scalarity and state-changes in Mandarin (and other languages)[END_REF] offer an interesting take on the meaning and aspectual profile of SVs in Mandarin. They start from the hypothesis that only verbs that denote a change-of-state may give rise to what they call the incompleteness effect, that is, be used in perfective sentences that 'describe killings in which no death occurred, repairs in which nothing gets fixed' (p. 243). They thus take change-of-state verbs to exist in Mandarin, as we do. Our proposal, however, differs crucially from theirs in one core respect: though they recognize the existence of causative change-of-state SVs in Mandarin, they nonetheless do not assume that Mandarin causative SVs have the same meaning as their English counterparts. In English, a lexical causative verb such as kill denotes a set of complete, 'causally successful' events leading to death. An event is complete with regard to the property denoted by kill if it reaches its endpoint -that is, the moment at which death occurs. In contrast, for Koenig and Chief, a Mandarin change-of-state verb such as shā 'kill' denotes a set of complete or incomplete killing events. Importantly, the set of events denoted by the verb thus also includes events that cause the theme to be hurt, but do not develop until causing death proper. The analysis we argue for is in this respect radically different: we take the null hypothesis to be that Mandarin SVs such as shā 'kill' have exactly the same semantics as their English causative counterparts. We locate the source of the incompleteness effect for non-gradable causative SVs, not in the lexical semantics of the verb, but in outer aspect (Koenig andMuansuwan 2000 on Thai, Altshuler 2014 on Hindi). We thus distinguish alongside RS-oriented activity SVs (e.g., xǐ 'wash'), analysed as in (5), non-gradable causative SVs such as shā 'kill', analysed as in (6), and gradable causative SVs such as shāo 'burn', analysed as in (7b).

(5) xǐ 'wash' ↝ λyλe.wash(e) ∧ theme(e, y) Our analysis of causative gradable SVs builds on [START_REF] Piñón | Aspectual composition with degrees[END_REF] analysis of incremental theme verbs. In particular, such verbs, according to Piñón, encode a degree of event realization and, crucially, the degree of event realization is not to be confused with the degree of change (endured by the theme). This proposal allows us to capture the idea that a causation event involving an agent (e.g., Lisi burning a piece of wood ) can be realized to a positive degree without the theme actually enduring a change (e.g., without the wood starting to burn). In this scenario, Lisi has started burning the wood as soon as he prepared the fire to do so and put the wood into the fire (the event is realized to a positive degree). But maybe the wood is so damp that it is able to withstand high temperature without starting to burn. In this case, Lisi has started burning the wood but the wood hasn't started burning. We assume that gradable causative simple verbs such as shāo 'burn' encode gradable properties which are measure functions µ yielding degrees d as values, tracking the degree of realization of events, as in (7a). The argument d gets bound either by the positive binding operator or by the degree maximizing operator (see (7c) or (7d) respectively, and more generally, Piñón 2008 on incremental theme verbs). When the value of d in (7b) is set to the maximum (d =1) -i.e. the (burning of y ) event is realized to degree 1 -the meaning postulate in (7e) captures that e causes some state of y being burnt. Following Piñón, we assume that the degree maximizing operator is preferred as a binder over the positive degree binding operator, since the former yields a stronger meaning than the latter would yield: if d =1, then d > 0, but not vice-versa (Kennedy and Levin 2008 make a similar point regarding the preference that a subset of degree achievements show for telic readings). This proposal accounts for why, in the first place, sentences such as the first clause of (3) by default implicate the occurrence of some result state. By contrast, non-gradable causative SVs such as shā 'kill' do not project a degree argument, as illustrated in (6). This is essentially where our proposal differs from that of [START_REF] Koenig | Scalarity and state-changes in Mandarin (and other languages)[END_REF] since for the latter causative SVs (shā 'kill') are taken to be gradable, while on our proposal they share the same meaning as English non-gradable causatives.

(6) shā 'kill' ↝ λyλe.∃(cause(e, s) ∧ dead(s) ∧ theme(e, y)) (

A finer-grained typology of SVs in Mandarin

The typology for (transitive) SVs that we argue for is summarized and illustrated in Figure 1. We achieve this typology by manipulating six diagnostics. Our first diagnostic is compatibility with a time-span adverbial, a standard diagnostic for telicity which will serve to distinguish SVs that yield telic VPs from those yielding atelic VPs -thus giving us the first level of classification in Figure 1. Both RS-oriented activity SVs and causative SVs will come out as yielding telic VPs on this test. But our next three diagnostics will crucially serve to distinguish RS-oriented activity SVs from causative SVs. Two of these are compelling, novel diagnostics involving the availability of so-called zero-change construals -namely, the time-span adverbial test, once again, but serving this time to distinguish RS-oriented activity from causative SVs on their zero-change construals, and the intransitive-zero-change construal test. Our forth diagnostic involves decomposition adverbs such as again, a classic test for causative event structure. The next diagnostic, gradability, allows us to distinguish two subclasses of causative SVs: gradable vs. non-gradable. Finally, our sixth and last diagnostic, temporal extendness, will distinguish non-gradable causative SVs from achievement verbs. 4 SVs yielding telic VPs: the time-span adverbial test

We identify SVs forming telic VPs, by which we mean VPs encoding an inherent terminal point [START_REF] Garey | Verbal aspects in French[END_REF], by using the standard time-span adverbial test: compatibility of adverbials such as X fēngzhōng ('X minute') in preverbal position with a VP containing a quantized object signals a telic interpretation of the VP. 4 As shown in ( 10)-( 11), this test confirms (as expected) that pure activity SVs, such as chúi 'hammer' or mō 'pet' never yield telic VPs, even when combined with a quantized object: In contrast, predicates which, according to our classification, are either RSactivity SVs (xǐ 'wash') or (by hypothesis) causative SVs (shāo 'burn'), yield telic construals of their VP when combined with a quantized object, as shown below. The availability of these telic construals for VPs headed by an SV undermines a widespread view according to which telicity in Mandarin can only be expressed with result verbal compounds (see, e.g., [START_REF] Lin | Event structure and the encoding of arguments: The syntax of the Mandarin and English verb phrase[END_REF]). The time-span adverbial test allows us to distinguish predicates denoting pure activities, never allowing telic construals even with a quantized object (chúi yíge pánzi 'hammer a plate' and mō yìzhī māo 'pet a cat'), from predicates which cannot be classified as such, since they do allow telic construals. There are however important differences among the latter class of SVs: determiner choice impacts telicity with RS-activity SVs such xǐ 'wash', as the contrast between ( 12) and ( 14) reveals, but not with causative SVs, as the grammaticality of ( 13) and ( 15 nèi-gēn that-piece mùtou. wood 'Lisi burned the piece of wood in ten minutes.' position, they yield a time-span interpretation (but see [START_REF] Xiao | Can completive and durative adverbials function as tests for telicity? evidence from English and Chinese[END_REF][START_REF] Xiao | Can completive and durative adverbials function as tests for telicity? evidence from English and Chinese[END_REF]Lin 2008, 38 for some exceptions), while in post-verbal position, they yield a durative interpretation.

The difference between ( 12) and ( 14) is that the cardinal indefinite determiner yī 'one' in (12) necessarily yields a quantized interpretation of the direct object, thus triggering telicity (see [START_REF] Wu | The semantics of the perfective le and its contextdependency: An SDRT approach[END_REF][START_REF] Zhang | Expressions duratives en chinois mandarin[END_REF], 185 for related observations), while demonstrative nèi 'that' is compatible with both quantized and cumulative reference. Consequently, the availability of a telic construal in ( 14) is context dependent and, thus, degraded in the absence of sufficient appropriate context. In sum, the distribution of judgments in ( 12)-( 15) tells us that the presence of a truly quantized direct object is essential for the derivation of telic interpretations with RS-activity (non-scalar) verbs but not with causative (scalar) SVs. We take this contrast in turn to show that telicity obtains differently with these two classes of predicates. In particular, adapting to Mandarin Rappaport [START_REF] Hovav | Lexicalized meaning and the internal temporal structure of events[END_REF] analysis of English telic VPs built with non-scalar verbs such as eat or wash, we assume that, with xǐ 'wash' type SVs, telicity arises via the object serving to measure out the progress the described event, thus delimiting its bounds and yielding an incremental interpretation of the predicate. In contrast, shāo 'burn' is a scalar verb (see ( 7) and section 6 below), and as such able to yield an incremental interpretation of the VP on its own. A telic construal with a time-span adverbial will thereby be available even if the internal argument does not impose a quantized interpretation by itself. We now provide further critical evidence for the proposal that xǐ 'wash' type SVs instantiate RS-oriented activity verbs, while shāo 'burn' type SVs instantiate causative verbs, just like their counterparts in English, by manipulating three diagnostics probing the respective meaning and event structure of these two classes of SVs.

Result-state oriented activity vs. causative SVs

We start by proposing two novels diagnostics, both involving the availability of the zero-change construal illustrated in (3)-( 4) above. The third test discussed here involves decomposition adverbs (such as, e.g., again), a traditional test for probing event structure.

Zero-change construals with time-span adverbials

We established in section 1 that a perfective (agentive) sentence built with a SV such as shāo 'burn' implicates -but does not entail -event culmination, since the occurrence of any change-of-state whatsoever in the referent of the theme argument can be explicitly denied in the subsequent discourse, as was illustrated in (3). This is unexpected if indeed such verbs are causative verbs, as we contend, and not RS-oriented activity verbs, as others contend. We further established in section 3, with the time-span adverbial test in ( 12)-( 13), that both shāo 'burn' and xǐ 'wash' type SVs yield telic construals of their VPs. We now ask what happens if we try to simultaneously enforce a zero-change and a telic construal in the same sentence, as illustrated in ( 16)-( 17 As shown in ( 17), the zero-change construal remains felicitous in perfective sentences involving an RS-oriented SV, combining with a quantized direct object and the adverbial in preverbal position yì fēngzhōng 'one minute' interpreted as a time-span adverbial. Crucially, however, for SVs that we take to be causative, the zero-change construal becomes infelicitous in the presence of a time-span adverbial modifying the VP, as shown in ( 16). That telic RS-oriented predicates such as xǐ wàzi 'wash the socks' need not describe efficient (wash-the-socks) events is rather unsurprising, for it is standardly assumed that these VPs do not encode the occurrence of the associated result state. But on the widespread view that shāo 'burn' is an activity SV, the result entailment observed in ( 16) is plainly unexpected. No such difference is expected to tease apart telic VPs built with xǐ 'wash' from those built with shāo 'burn' -if both instantiate RS-oriented activities. If, however, we are dealing here with two different classes of verbs, RS-activity vs. causative SVs, then such a contrast is no longer surprising. The question is why the occurrence of a result state with a causative SV could be successfully denied in (3), but not when we add a time-span adverbial as in ( 16). Recall the semantics attributed to a gradable causative SV such as burn, repeated below for convenience. The proposal in (7) will straightforwardly explain why zero-change construals fail to survive, in the presence of time-span adverbials, with VPs headed by gradable causative SVs. This will be the case simply because a time-span adverbial requires the predicate to which it applies to have quantized reference [START_REF] Krifka | Thematic relations as links between nominal reference and temporal constitution[END_REF][START_REF] Krifka | The origins of telicity[END_REF]. Crucially, however, whether the reference of the VP headed by shāo 'burn' combining with a quantized internal argument is ultimately quantized or not 5 , depends foremost on the value obtained for the degree argument encoded in its meaning. 6 There are two options for binding the verb's degree argument. Suppose that d gets bound by the degree maximizing operator (option (7d)), then the meaning postulate in (7e) (according to which, if an event e of burning y is realized to its maximal degree, then e causes some state of y being burnt) kicks in. That is to say, if the degree maximizing operator sets the value of d to the maximum, the VP shāo yì-gēn mùtou 'burn a piece of wood' denotes the set of burning events causing some state of a piece of wood being burned. This VP has quantized reference, for no such event in which a piece of wood is successfully burnt contains an event in which a piece of wood is successfully burnt. It thus follows that when we add a time-span adverbial to (13) as in ( 16), the zero-change construal will not survive: the time-span adverbial requires the predicate to which it applies to have quantized reference, which in turn requires the predicate's d argument to be bound by the degree maximizing operator, thus entailing the occurrence of a result state of the theme being burned (via the meaning postulate (7e)). Now, suppose that d is bound by the positive degree binding operator (option (7c)). Since the latter merely restricts d 's value to being greater than 0, the VP may get an atelic, cumulative interpretation, for the sum of two incomplete events of burning a piece of wood counts also an incomplete event of burning a piece of wood, if a specific piece of wood is at issue. Recall furthermore that if 1 > d > 0, then the burning event need not actually trigger any change in the theme (this is the scenario where Lisi has started burning the wood by putting it in the fire but the wood is to damp to start burning, to endure any change). 7

Intransitive zero-change construals

Our second novel diagnostic for distinguishing RS-oriented activity from causative SVs also involves zero-change construals. This time we ask what happens if we try to enforce a zero-change construal on the intransitive use of SVs (where the verb projects a single internal argument appearing in subject position). Will the zero-change construal survive when we switch from the transitive to the intransitive frame of the SV? Once again, we will see that the zero-change reading survives with RS-activity SVs, but not with causative SVs. Thus consider the contrast between ( 18) and ( 19 6 This idea goes back to Piñón 2008's discussion of how to capture the aspectual flexibility of VPs such as as eat the apple.

7 For obvious reasons, this explanation for why zero-change construals are possible with gradable verbs such as shāo 'burn' does not carry over to non-gradable causative verbs such as shā 'kill', but as specifically mentioned in footnote 1, zero-change construals are harder to obtain with non-gradable causative SVs. We refer the reader to [START_REF] Liu | Non-culminating accomplishments in child and adult Chinese[END_REF] and Martin et al. (2020b) for a more detailed empirical picture of the licensing of zero-change construals across gradable vs. non-gradable causative SVs. Suffice it say that the zero-change construal with non gradable SVs comes about differently, via the partitive semantics of perfective -le, analysed as non-completive partitive aspectual operator (Martin and Gyarmathy 2019 and references therein; Martin et al. 2020b As shown in ( 19), sentences built with causative SVs used intransitively are incompatible with zero-change scenarios. This is in striking contrast with the (agentive) transitive use of these verbs which licenses zero-change construals, as we saw in (3) and ( 4). (Zhang 2018, 130 makes the same observation for guān 'close'.) We thus have a two-way contrast: with a causative (gradable) SV, the zero-change construal is available on its transitive agentive use, but not on its intransitive use, while with an RS-oriented activity SV, it is available across the board. What about with non-gradable causative SVs such as shā 'kill' ? Recall, from footnote 3, that zero-change construals with such verbs are more restricted, requiring the presence of a cardinality adverbial, e.g., once, or a temporal durative adverbial. Yet again, we see that the zero-change reading does not survive on the intransitive use, even in the presence of the enhancing adverbial. In particular, (21) weirdly suggests that the chicken came to life again after dying. From the above distribution of zero-change construals, we conclude that Mandarin RS-activity SVs do not entail the occurrence of a change towards a conventionally associated result state, be it in transitive or intransitive frames. In contrast, Mandarin causative SVs do not entail the occurrence of a change towards a lexically encoded state in (agentive) transitive frames, but they do entail such a change when used intransitively. We take the result entailments that kill and burn SVs show on their intransitive use to further support our claim that they do not fall in the same class as wash-verbs in Mandarin -that is, they are not RS-oriented activities, but rather have causative semantics. We very briefly summarize [START_REF] Martin | Aspectual differences between agentive and nonagentive uses of causative predicates[END_REF] analysis of the result entailment of causative SVs used intransitively in the following subsection, turning next to RS-activity verbs. In a nutshell, we argue that these two classes of SVs in Mandarin yield distinct types of intransitive alternants. Verbs such as shāo are anticausative SVs when used intransitively. They have a causative semantics, and are basically semantically and syntactically similar to anticausatives in English (Alexiadou et al. 2006[START_REF] Alexiadou | External arguments in transitivity alternations: A layering approach[END_REF]. SVs such as xǐ 'wash' used intransitively are what we henceforth call antiagentives.

Anticausative verbs

Under the approach adopted here, causatives and anticausatives have the same event structure with two components, a causing event and a result state, semantically differing only in the presence vs. absence of Voice [START_REF] Kratzer | Building resultatives[END_REF][START_REF] Alexiadou | Instrument subjects are agents or causers[END_REF][START_REF] Schäfer | The Syntax of (Anti-)Causatives. External arguments in change-of-state contexts[END_REF]. On its anticausative use, shā Fido 'Fido get kill/die' thus receives the meaning ( 22), while on its agentive causative use, shā Fido 'kill Fido' receives the meaning in (23b). 8 The core idea shared by the proponents of this view in the literature is that anticausatives are just plain causatives, and [START_REF] Martin | Aspectual differences between agentive and nonagentive uses of causative predicates[END_REF] proposal is that the causing event described by anticausatives is some internal change involving the verb's sole argument, the theme. ( 22 So why is the zero-change construal no longer available with the anticausative alternant of shā 'kill' or shāo 'burn' ? [START_REF] Martin | Aspectual differences between agentive and nonagentive uses of causative predicates[END_REF] answer is as follows. When Voice is active licensing the projection of a second (external) argument, e.g., the agent in (23b), the causing event is necessarily understood as involving an action performed by the latter (for x cannot be the agent of e without doing anything). When, however, Voice is not active, and an agent argument is not licensed, then the causing event is necessarily understood as the internal event (the change-of-state) undergone by the theme. Therefore asserting in the subsequent discourse (as in (19) or in ( 21)), that the theme has undergone no change-of-state whatsoever, thus that such change was not even initiated, is infelicitous, and can only but generate a contradiction.

Antiagentive verbs

A typologically striking property that Mandarin shares with other languages such as Hindi [START_REF] Bhatt | Causative derivations in Hindi-Urdu[END_REF], Brazilian Portuguese [START_REF] Carvalho | What causes the alternation of agentive verbs in Brazilian Portuguese? University of Pennsylvania Working Papers in Linguistics[END_REF] or Salish [START_REF] Davis | On lexical verb meanings: Evidence from Salish[END_REF] is that not only core (causative) SVs, but also non-core (non-causative) SVs have intransitive alternants where the single internal argument of the verb appears in subject position [START_REF] Tai | Verbs and times in Chinese: Vendler's four categories[END_REF][START_REF] Aldridge | Ergativity and unaccusativity[END_REF]. 8 Intransitive shā Fido is difficult to translate in English because it remains highly agentive just like on its transitive use. That is, used transitively, it can only take a human subject or a non-human one that can be construed as an instrument (and as such is agent-like, see Alexiadou and Schäfer 2006, e.g., shāchóngyào 'pesticide'). Used intransitively, shā differs from sǐ 'die, dead' in that it entails the existence of an implicit agent, remaining syntactically and semantically inactive (see Martin et al. 2020a and references therein).

12On the zero-change construal of causative simple verbs in Mandarin Chinese

The intransitive alternant of SVs such as xǐ 'wash' are not anticausative since such verbs are RS-oriented activities devoid of causative semantics. We coin the term antiagentive to refer to the intransitive use of RS-activities. Antiagentives denote the subcomponent of the activity involving the theme exclusively. For instance, when used intransitively, xǐ 'wash' describes the subpart of the washing process which involves the theme exclusively. The 'patientive' subcomponent of the activity is distinct from the subcomponent involving the agent. In the case of wash, these two subcomponents typically have different locations. For instance, the getting-washed patientive subevent may take place within a sink, while the active washing subevent typically occurs in front of the sink rather than inside of it. Tellingly, the locative PP zài shuǐcháo qián 'in front of the sink' can felicitously modify the VP xǐ nèi-shuāng wàzi 'wash that pair of socks' when used transitively (for the action described could indeed be taking place in front of the sink). But the same locative PP is not felicitous when modifying the same VP used intransitively. Only the locative PP zài shuǐcháo lǐ 'in the sink' is felicitous on this intransitive use of the same VP (for the patientive getting-washed component is indeed taking place in the sink): We call the intransitive alternant of RS-oriented activity SVs antiagentive because they focus on the patientive subpart of the manner event, with the subpart of the activity involving the agent proper 'stripped off' and, as such, not accessible for modification by locative adverbials (see ( 25)). Thereof also the unvailability of modification by agent-oriented adverbials or purpose clauses (Levin andRappaport Hovav 1995, Schäfer 2008), contrary to what is observed with bèi -passives (as also observed by Sybesma and den Dikken 1998): Since antiagentives denote a subpart of an activity, and not a change-of-state as anticausatives do, denying that the outcome of the described activity was successful, does not yield any contradiction, as illustrated in (18).

Decomposition adverbs

We now turn to our third diagnostic for event structure, decomposition adverbs [START_REF] Rapp | Fast 'almost' and the visibility parameter for functional adverbs[END_REF], and specifically for Mandarin, the adverb yòu 'again' which gives rise to sharper judgments than chàdiǎn or jīhū 'almost'. As is well-known, the readings that such adverbs display serve as a classic diagnostic for probing (simple vs. complex) event structure representations. For instance, the adverb again displays different readings with at least a subset of accomplishment verbs, readings distinguished by the presuppositions they are associated with [START_REF] Von Stechow | Lexical decomposition in syntax[END_REF][START_REF] Von Stechow | The different readings of wieder 'again': A structural account[END_REF][START_REF] Rapp | Fast 'almost' and the visibility parameter for functional adverbs[END_REF][START_REF] Pedersen | Inchoative verbs and adverbial modification: Decompositional and scalar approaches[END_REF][START_REF] Lechner | On deriving the typology of repetition and restitution[END_REF]. For instance, ( 27) either presupposes that the door was previously opened by John before (repetitive reading), or presupposes that the door was in a previous state of being open (restitutive reading). The restitutive reading is not available with activity VPs, which do not involve a state component, see ( 28). Only those accomplishment VPs whose event structure involves a result state component clearly display the restitutive reading. Verbs that do not lexicalize, but are only 'conceptually associated' with such a state, do not allow the restitutive reading (see von Stechow 2009 on putzen 'wash' vs. säubern 'clean' in German). In Mandarin Chinese, yòu 'again' occurs preverbally only. The RS-oriented activity SV chuī 'blow [e.g., a candle]' and the causative SV xī 'blow out [e.g., a candle]' have a very close meaning, and essentially differ in that a result state is lexically encoded by xī, but not chuī. We therefore predict the restitutive reading to be available with xī 'extinguish' but not chuī 'blow'. This is indeed the case, as the following scenario shows. Assume that I bought a brand new candle. I lighted it and blew it out once only. In this context, which blocks the repetitive reading of yòu, (29b) is acceptable, while (29a) is not.

(29) a.

[

Gradable vs. non-gradable causative SVs

We now distinguish two sub-classes of causative SVs by invoking a fifth parameter of classification: gradability. To distinguish SVs that yield gradable VPs when combined with an object with a quantized use from those that do not, we test their compatibility with adverbials of completion such as yíbùfen 'partly', yìdiǎn 'a little' which presuppose that the relation to which they apply may yield degrees greater than 0 but less than 1 [START_REF] Piñón | Adverbs of completion in an event semantics[END_REF]. This test splits the class of causative SVs into two classes. Gradable causative SVs, e.g. shāo 'burn', rǎn 'dye', or guān 'close', are acceptable with adverbials of completion (wánquán/quán 'completely') or degree complements (yíbùfen/yìdiǎn 'partly/a little') when combined with a quantized object, as shown in (33). 10 9 Beck (2005) reports that out of the three subjects tested, only one fully accepts the restitutive reading of this example. The other two speakers find it questionable (without plainly rejecting it). We think Beck's test sentence does not sound very felicitous for a reason orthogonal to the interpretation of yòu, which may have biased the speakers' judgments. The most usual way of expressing what the sentence means is to use a BA construction and a RVC, where the object is placed in a preverbal position: (i) Sally yòu ba mén dǎ-kāi le.

Sally again BA door open PFV However, we tested (32) with some additional speakers and they mainly find the restitutive reading acceptable (including both Mandarin speaking authors of this paper).

10 Either object topicalization or the BA construction is needed to make adverbials of completion with SVs fully acceptable. For instance, (i) below is quite odd. We now turn to the last parameter of classification in our typology of SVs (Figure 1), which serves to distinguish causative accomplishment SVs from achievement SVs. Our first test is compatibility with the progressive markers zài and zhèngzài. Mandarin achievements cannot be progressivized [START_REF] Smith | The parameter of aspect[END_REF], 357, Klein et al. 2000, 764, Chief 2008, 217, Lu et al. 2019 Although we do not have an account for this restriction, it remains orthogonal to our main point which is to distinguish two classes of causative SVs according to their gradability. On adverbials of completion in Mandarin Chinese, see e.g. Chief (2008, 73-75). Some predicates see their aspectual properties vary with their syntactic frame. Take for instance shā 'kill/ die/ get killed'. When this predicate is used transitively (and thus agentively, for recall from footnote 8 that shā requires an agentive subject), it is an accomplishment, denoting an event with at least two sub-components: an action and an (instantaneous) change-of-state. In contrast, when shā 'kill' is used intransitively as an anticausative, it denotes a set of (instantaneous) changes-of-state, i.e., dying events (from an agentive cause, for the involvement of an agent is also entailed in intransitive frames, although the agent is not present in the structure). Precisely because these changes-of-state are instantaneous, the progressive is infelicitous, as seen in (41a), just like with sǐ 'die' (as seen in ( 41b)). Our second diagnostic is compatibility with the completive suffix wán/hǎo 'finish', which selects predicates describing events having some duration. As such, it is incompatible with achievement verbs, as shown in (42), since the latter by definition denote instantaneous events (Piñón 1997). In contrast, causative SVs -whether they are gradable (shāo 'burn') or not (shā 'kill') -do not denote punctual events and, as such, can combine with the completive suffix wán/hǎo, as shown in (43). Finally, achievements differ crucially from non-gradable causatives in that they never allow zero-change construals even in the presence of a cardinality adverbial. Thus compare the achievement paradigm in (44) with the non-gradable causative paradigm (4) repeated below: adding a cardinality adverbial in (44) does not rescue the zero-change reading of the achievement, as it did for the non-gradable causative in (4). We thus conclude that, while cardinality adverbials modifying perfective accomplishment SVs may quantify over non-culminating events, as shown in (4), cardinality adverbials modifying perfective achievement SVs may not. That is to say, perfective achievements (whether modified or not by cardinality adverbials) necessarily denote culminated events, and this is why negating the culmination of the reported event in a subsequent clause yields a contradiction. We close by pointing out that the contrast between ( 44) and(4) illustrates two canonical properties of achievement across all languages reported to productively allow non-culminating readings for accomplishments, as documented for instance for Hindi [START_REF] Singh | Perfectivity, definiteness, and specificity: A classification of verbal predicates in Hindi[END_REF][START_REF] Altshuler | A typology of partitive aspectual operators[END_REF]), German [START_REF] Bott | The processing of events[END_REF], Salish languages [START_REF] Bar-El | Aspectual distinctions in Skwxwú7mesh[END_REF][START_REF] Kiyota | Situation Aspect and Viewpoint Aspect: From Salish to Japanese[END_REF] or Thai [START_REF] Koenig | How to end without ever finishing: Thai semi-perfectivity[END_REF]: achievements denote atomic events and do not allow incomplete event readings (be it zero or partial change) in the perfective.

  that pair of socks, but they are not at all clean.'

  3

  a piece of wood but it didn't get burned at all.' a chicken several times, but it is still alive.'

  7) a. burn µ (e, y) 'the degree to which a burning event e of y is realized' b. shāo 'burn' ↝ λyλdλe.burn µ (e, y) = d c. burn + µ (e, d, y) ∶= burn µ (e, y) = d ∧ d > 0 d. burn(e, y) ∶= burn µ (e, y) = d ∧ d = 1 e. ∀e∀y(burn(e, y)) → ∃s(cause(e, s) ∧ burned(s, y))

  Dandan petted a cat in one minute.'

  a piece of wood in ten minutes.'

  (7) a. burn µ (e, y) 'the degree to which a burning event e of y is realized' b. shāo 'burn' ↝ λyλdλe.burn µ (e, y) = d c. burn + µ (e, d, y) ∶= burn µ (e, y) = d ∧ d > 0 d. burn(e, y) ∶= burn µ (e, y) = d ∧ d = 1 e. ∀e∀y(burn(e, y)) → ∃s(cause(e, s) ∧ burned(s) ∧ theme(s, y))

  the chicken once, but the chicken is still alive.' [Li tried once to kill it, but it was unsuccessful.chicken got killed once.'

  ate.' [i.e., the cake got eaten]

  It was in front of the sink that the pair of socks washed.in the sink that the pair of socks washed.'

  ] socks (were) washed cautiously.'

( 27 )

 27 It is possible that John opened the door again. a. Presupposition on the repetitive (rep) reading: John has opened the door before. b. Presupposition on the restitutive (rest) reading: The door had been open before. (28) It is possible that John ran again. a. Presupposition on the repetitive reading: John has run before. b. No restitutive reading.

16On

  the zero-change construal of causative simple verbs in Mandarin Chinese burning the leaves.'

  That chicken is dying.'

  The president arrived in Paris several times, but did not arrive.'(The president went to Paris several times, but got lost, finally he failed to arrive there.)

  ).

	(18) Nèi	wàzi	xǐ-le,	dàn	gēnběn	méi	xǐ-gānjìng.
	that	sock	wash pfv	but	at all	neg.pfv	wash-clean
	'These socks washed, but they didn't get clean at all!'

  ).

	10On the zero-change construal of causative simple verbs in Mandarin Chinese
	(19) Nèi-fēng	xìn	shāo-le,	#dàn	gēnběn	méi	shāo-zháo
	that-CL	letter	burn pfv	but	at all	neg.pfv	burn-ignite
	Intended: 'That letter burned, but it didn't get burned at all.'

  ) shā Fido 'Fido get killed/die' ↝ λe.∃s(cause(e, s) ∧ dead(s) ∧ theme(s, fido)) (23) a. Voice ag ↝ λP λxλe.agent(e, x) ∧ P (e) b. Voice ag shā Fido 'kill Fido' ↝

[λP λxλe.agent(e, x) ∧ P (e)] (λe.∃s(cause(e, s) ∧ dead(s) ∧ theme(s, fido)) = λxλe.∃s(agent(e, x) ∧ cause(e, s) ∧ dead(s) ∧ theme(s, fido))

  Nor is the restitutive reading of yòu 'again' available either with accomplishment VPs headed by the RS activity SV xǐ 'wash'. For instance, (30a) is odd in a situation where Momo bought a pair of brand new socks, and washed them only once after they got dirty. As expected, however, in this very same context (blocking the repetitive reading), a sentence with the corresponding result verbal compound xǐ-gānjìng 'wash clean' is fine.These tests thus confirm that neither xǐ 'wash', nor chuī 'blow [e.g., a candle]' lexically encode a result state, as expected if they are RS-oriented activities. Conversely, the restitutive reading is available with kāi 'open', as expected if it has causative semantics. 9In summary, the restitutive reading is acceptable with a subset of Mandarin SVs, namely causative SVs which by hypothesis encode a result state at the lexical level.

		(30) a.	Mòmo	yòu	xǐ	le	nèi-shuāng	wàzi.	[rep only]
				Momo	again	wash	pfv	that-pair	sock
				'Momo washed that pair of socks again.'
		(31) a.	Mòmo	yòu	xǐ-gānjìng	le	nèi-shuāng	wàzi.	[rep/rest]
				Momo	again	wash-clean	pfv	that-pair	sock
				'Momo washed that pair of socks clean again.'
		(32)	Sally	yòu		kāi	le	mén.	[rep/rest]
			Sally	again	open	pfv	door
			'Sally opened the door again.'
		Nèi-gēn	làzhú	tā		yòu	chuī-le.	rep only]
		that-cl	candle	3sg	again	blow-pfv
		'He blew the candle again.'
	b.	Nèi-gēn	làzhú	tā		yòu	xī-le.	[rep/rest]
		that-cl	candle	3sg	again	extinguish-pfv
		'He blew out the candle again.'

This paper is submitted to the Proceedings of Triple A 7 (version of Nov. 6,

2020). We would like to thank Florian Schäfer for invaluable discussion and input, as well as the reviewers and audience of Triple A 7 and Sinn und Bedeutung 20 for their feedback, especially Giorgos Spathas. F.Martin's research is financially supported by DFG award AL 554/8-1 (Leibniz-Preis 2014) to A. Alexiadou, and H. Demirdache's research by the LLING UMR 6310 (Nantes University/CNRS). Abbreviations used: cl: classifier, dp: determiner phrase, dur: durative aspect, neg: negation, pfv: perfective, prog: progressive, rs: result state sg: singular, sv: simple verb, vp: verbal phrase. 1

Prepositionless adverbials in Mandarin (such as X fēngzhōng 'X minute') allow both a time-span and a durative interpretation. Simplifying, these interpretations are determined by position relative to the verb and context[START_REF] Xiao | Can completive and durative adverbials function as tests for telicity? evidence from English and Chinese[END_REF] Mcenery 2006, Zhang 2016). In pre-verbal

A VP has quantized semantics if no proper part of the event it denotes can be an event of the same kind as the whole event[START_REF] Krifka | Thematic relations as links between nominal reference and temporal constitution[END_REF][START_REF] Krifka | The origins of telicity[END_REF].