Jérémy Omer
email: jeremy.omer@insa-rennes.fr

Michael Poss
email: michael.poss@lirmm.fr

A polynomial algorithm for minimizing travel time in consistent time-dependent networks with waits

Keywords: Time-dependent networks, Shortest paths, Label-setting algorithms, Concavity, Breakpoint, Wait

A polynomial algorithm for minimizing travel time in consistent time-dependent networks with waits

Jérémy Omer, Michael Poss

Introduction

We consider a variant of the time-dependent shortest-path problem (TDSP). Let G = (V, A) be directed graph with n nodes and m arcs. The travel time of each arc is a continuous piecewise linear function of the departure time from its tail, which satisfies the consistency assumption, preventing from reaching the head of an arc earlier by departing later from its tail. The objective is to find a path from o ∈ V to d ∈ V that has the lowest travel time. We additionally consider that waiting is allowed at nodes belonging to the set U ⊆ V , but the total waiting time may not exceed a given bound W . Finally, the waiting time is not considered in the cost so only the travel time needs to be minimized.

The problem has diverse applications in transportation, starting with the limitation of emissions in urban environments, given that the emissions of a vehicle are roughly proportional to its travel time, see for instance [START_REF] Jabali | Analysis of travel times and co2 emissions in time-dependent vehicle routing[END_REF] for details. It can also be used for planning salesman trips, avoiding peak hours by stopping at specific places to perform other activities, therefore avoiding to loose time 1 in traffic. In that case, W models the total amount of other activities the salesman has to realize while at rest, such as accounting, preparing presentations or reports. Finally, the problem also has applications in planning long tourism trips where waits can be seen as opportunities to visit minor attractions located on the route between the main spots whereas traffic kills the pleasure of holidays. In that case W represents the amount of time the tourists are willing to spend visiting the minor attractions.

Context and previous works

The study of the time-dependent shortest path problem (TDSP) dates back to Cooke and Halsey [START_REF] Cooke | The shortest route through a network with time-dependent internodal transit times[END_REF] who introduced an extension of Bellman's equations [START_REF] Bellman | On a routing problem[END_REF] to the time-dependent context. This early work has been followed by articles introducing the aforementioned consistency assumption. Also called FIFO (first-in first-out), this assumption leads to polynomial-time algorithms for the problem [START_REF] Dreyfus | An appraisal of some shortest-path algorithms[END_REF][START_REF] Orda | Shortest-path and minimum-delay algorithms in networks with timedependent edge-length[END_REF][START_REF] Kaufman | Fastest paths in time-dependent networks for intelligent vehicle-highway systems application[END_REF], through straightforward extensions of the algorithms for classical shortest path problem.

Allowing to wait (or park) at nodes makes the problem more complex since one must decide how long to wait at each node, in addition to choosing the path. Early variants for the TDSP with waiting include [START_REF] Orda | Shortest-path and minimum-delay algorithms in networks with timedependent edge-length[END_REF][START_REF] Orda | Minimum weight paths in time-dependent networks[END_REF] where it is shown that the shortest path may well be infinite. As these early papers could not handle certain kind of discontinuities, [START_REF] Dell'amico | Shortest paths in piecewise continuous timedependent networks[END_REF] proposed a new approach able to solve the problem for any kind of discontinuity. A general approach to the TDSP with waiting has been proposed by Cai et al. [START_REF] Cai | Time-varying shortest path problems with constraints[END_REF] who consider that each arc has a time-dependent cost, in addition to the time-dependent traversing time, and that waiting incurs a cost, also modeled by a time-dependent function. Their model also requires that the path reaches the destination within a given time horizon. Different dynamic programming algorithms have been proposed for this variant [START_REF] Cai | Time-varying shortest path problems with constraints[END_REF][START_REF] Chabini | Shortest path problems in discrete-time dynamic networks: complexity, algorithms and implementations[END_REF][START_REF] Dean | Algorithms for minimum-cost paths in time-dependent networks with waiting policies[END_REF]. The resulting algorithms run in time polynomial in n, m, and the length of the time horizon, making them pseudo-polynomial. Related works consider alternative settings such as minimizing the excess time (over the minimum travel time) [START_REF] Ahuja | Dynamic shortest paths minimizing travel times and costs[END_REF] or road networks with traffic lights [START_REF] Ahuja | Minimum time and minimum cost-path problems in street networks with periodic traffic lights[END_REF].

Other variants of the TDSP with waiting have been considered by [START_REF] Foschini | On the complexity of time-dependent shortest paths[END_REF] and [START_REF] Omer | Time-dependent shortest path with discounted waits[END_REF]. Both papers consider only traversing time functions and relax the time horizon constraint. On the one hand, if waiting is allowed only at the source node, Foschini et al. [START_REF] Foschini | On the complexity of time-dependent shortest paths[END_REF] show that the problem remains polynomially solvable. On the other hand, if waiting is allowed at each node, and bounds not greater than W are considered on each node, the problem becomes N P-hard [START_REF] Omer | Time-dependent shortest path with discounted waits[END_REF] and can be solved polynomially in n, m and W . Interestingly, the reduction provided in [START_REF] Omer | Time-dependent shortest path with discounted waits[END_REF] does not extend to the case where the waiting times are bounded only by one global constraint. The purpose of this paper is to fill this gap: we prove that the TDSP allowing waiting at each node and bounding the waiting time only by one global constraint can be solved in polynomial time.

In what follows, we define a path from u to v as p = (ν; v 1 (= u), v 2 , . . . , v σ(p) = v) where ν indicates the starting time at node v 1 , and σ(p) denotes the number of nodes of p. We say that node w belongs to p if there is i ∈ {1, . . . , σ(p)} such that v i = w. To simplify the notations used throughout, we assume that one can wait at all nodes of the graph (U = V ), and define a pathwith-waits as the couple (p, w), where p is a path and w = (w 1 , . . . , w σ(p)-1 ) is a (σ(p) -1)-tuple indicating the waiting time at each node along p. We further denote t p,w (i) as the departure time from the i th node in path-with-waits (p, w) and t p (i) as the departure time from the i th node in path p. For the last node of a path p (resp. path-with-waits (p, w)), t p (σ(p)) (resp. t p,w (σ(p))) denotes the arrival time at the node.

For v ∈ V , we define PW v (ω) be the set of paths-with-waits from o to v which satisfy

σ(p)-1 i=1
w i ≤ ω. Since we wish to minimize total travel time, the cost of (p, w) can be expressed as

C(p, w) = σ(p)-1 i=1 C v i v i+1 (t p,w (i)),
Let T v (ω) = min (p,w)∈PWv(ω) C(p, w) be the minimum travel time among all paths-with-waits from o to v with total waiting time at most ω. Given W ≥ 0, the aim of the article is to provide a polynomial-time algorithm for the optimization problem

T d (W ) = min (p,w)∈PW d (W )

C(p, w). (TDSPW)

We can assume without loss of generality that W ∈ Ω as it is usless to wait more than max e∈A τ re-1 e . We conclude the section by introducing further notations used throughout. Given ω < ω , we denote by p u→v (ω, ω ) the shortest path (without waits) from u to v, leaving u at T u (ω) + ω . The total number of breakpoints of all travel time functions is denoted as R = e∈A (r e -1). For e = (u, v) ∈ A and 0 ≤ ω ≤ W , we denote the index of the right and left breakpoints of function C e at T u (ω) + ω as s e (ω) and s - e (ω), respectively. Formally, s e (ω) = min s {s : T u (ω) + ω < τ s e } and s - e (ω) = s e (ω) -1.

(

) 1
To keep concise notations, we also define

τ u (ω) = min (u,v)∈A τ suv(ω) uv and τ - u (ω) = max (u,v)∈A τ s - uv (ω) uv . (2)
Next, given a one-variable function f (x), we denote its left and right derivatives as ∂ -f (x) and ∂ + f (x), respectively. Finally, we denote by by SP P (α, β) the complexity of solving a static shortest path problem on a digraph with α nodes and β edges, which is the same as solving a time-dependent shortest path problem without waiting on a digraph (e.g. [START_REF] Orda | Shortest-path and minimum-delay algorithms in networks with timedependent edge-length[END_REF]). Similarly, we let ASP P (α, β) be the complexity for solving a static shortest path problem on an acyclic digraph.

Contributions

The purpose of the article is to prove the following theorem.

Theorem 1. TDSPW can be solved in O(n × R × SP P (n, m)).

Similarly to the method developed by Foschini et al. [START_REF] Foschini | On the complexity of time-dependent shortest paths[END_REF], our algorithm exploits the breakpoints of the travel time functions. Yet, our problem needs to handle the possibility of waiting at every node of the graph, unlike in [START_REF] Foschini | On the complexity of time-dependent shortest paths[END_REF] where it is allowed to wait only at the source node. Hence, even when the path is given, the optimization problem considered herein involves n variables, one for each node, while the counterpart from [START_REF] Foschini | On the complexity of time-dependent shortest paths[END_REF] is a one-dimensional optimization problem.

We address this difficulty by decomposing optimal paths-with-waits into alternating sequences of waits and paths. This decomposition is done by gradually increasing the allowed amount of waiting time, starting from ω 1 = 0. Specifically, at each iteration k of our algorithm, we will define ω k as the allowed amount of waiting time, and we compute the breakpoint τ v (ω k ) for each node v ∈ V . Iteration k then examines what is the value of the maximum possible wait at each node u that, when followed by a shortest path from u to some other node v, hits the breakpoint τ v (ω k ). Taking the minimum among all nodes of these maximum possible waits, we obtain the additional waiting time allowed at iteration k, and adding that waiting time to ω k yields ω k+1 . Once ω k+1 is known, we compute

{T v (ω k+1 ), v ∈ V } from {T v (ω k ), v ∈ V } by applying a classical shortest path algorithm.
A different approach has been followed simultaneously and independently by [START_REF] He | Computational complexity of timedependent shortest path problems[END_REF][START_REF] He | Dynamic discretization discovery algorithms for time-dependent shortest path problems[END_REF]. Whenever there is no waiting limit (setting W large enough), the authors of [START_REF] He | Computational complexity of timedependent shortest path problems[END_REF] decompose optimal pathswith-waits into alternating sequences of waits and paths by expanding forward and backward shortest path trees from each breakpoint and computing shortest paths on the resulting timeindexed networks. The resulting algorithm solves the problem in O(R × SP P (n, m) + ASP P (nR, mR)).

(

) 3
They further extend their approach to handle bound W in [START_REF] He | Dynamic discretization discovery algorithms for time-dependent shortest path problems[END_REF] essentially by solving up to O(n×R 2 ) variants of the problem with no wait limits, resulting in an algorithm running in

O(n × R 3 × SP P (n, m) + R 2 × ASP P (nR, mR)). (4)
We see that our result, stated in Theorem 1, compares in the general case favorably with the result of [START_REF] He | Dynamic discretization discovery algorithms for time-dependent shortest path problems[END_REF], having the complexity stated in (4), while the case without waiting (obtained by setting W large enough) is solved more efficiently by the result of [START_REF] He | Computational complexity of timedependent shortest path problems[END_REF], having the complexity stated in (3).

Outline

The rest of the paper is structured as follows. In the next section, we state basic properties of the optimal paths-with-waits and the recurrence relations satisfied by T v (ω). The section also shows that if we are able to construct a sequence ω 1 , ω 2 , . . . , ω K for which the following recurrence relation holds

T v (ω k+1 ) = min T v (ω k ), min (u,v)∈A T u (ω k+1 ) + C uv (T u (ω k+1 ) + ω k+1 ) , (5)
then we obtain a polynomial-time algorithm for the problem. Section 3 further analyzes the structure of the paths-with-waits realizing T v (ω). The first important result of the section is to show that when ω 1 , ω 2 , . . . , ω K are such that

T u (ω k+1 ) + ω k+1 ≤ τ u (ω k ), (6)
holds for each k ∈ {1, . . . , K -1}, then the discrete recurrence relation (5) holds. The section then decomposes any path-with-waits realizing T v (ω k+1 ) into a concatenation of a path-with-waits realizing T u (ω k ), an additional wait ω k+1 -ω k at node u, and a shortest path from u to v. Section 4 leverages that decomposition to construct dynamically a sequence ω 1 , ω 2 , . . . , ω K satisfying property [START_REF] Cooke | The shortest route through a network with time-dependent internodal transit times[END_REF]. Hence, using the result from Section 3, we know that the recurrence relation [START_REF] Chabini | Shortest path problems in discrete-time dynamic networks: complexity, algorithms and implementations[END_REF] holds, and the latter can be solved as explained in Section 2. The main ingredient of the construction of the sequence is an algorithm that backpropagates the values τ u (ω k ) for each u ∈ V . Section 4 also presents the overall algorithm solving the problem.

Preliminaries

In what follows, we introduce a dynamic programming recursions for TDSPW. These recursions involve infinitely many states and cannot be used directly to solve TDSPW. However, we show that if we can guarantee that only a polynomial number of these states (which will be indexed by k = 1, . . . , K) is needed to obtain the optimal solution, then TDSPW can be solved in polynomial time by applying K times a shortest path algorithm. The section also presents key properties of the value-functions involved in the recursions, which will be used often along the manuscript. Let v ∈ V and ω ≤ W . Our algorithm is based on the recurrence relation that relates T v (ω) to the minimum travel time to the predecessors of v. To derive the relation, we introduce T = v (ω) as the minimum travel time among all paths from o to v with total waiting time exactly ω, not including the time waited at v. Formally,

T = v (ω) = min (p,w)∈PWv(ω)    C(p, w) : σ(p)-1 i=1 w i = ω    .
For this quantity, one can verify that the following recurrence holds.

T = v (ω) = min (u,v)∈A min ω ≤ω T = u (ω ) + C uv (T = u (ω ) + ω) .
Using the consistency assumption, we observe that

T = u (ω ) + C uv (T = u (ω ) + ω) is minimum if T = u (ω ) is minimum. Since T u (ω) = min ω ≤ω T = u (ω )
, the above recurrence relation can be equivalently written as

T = v (ω) = min (u,v)∈A T u (ω) + C uv (T u (ω) + ω). (7)
As a consequence, we can distinguish two cases in the computation of T v (ω), depending on whether it is achieved with a total wait equal to or lower than ω. If there exists ω < ω such that

T v (ω) = T = v (ω ), then T v (ω) = T v (ω ). (8)
Otherwise, T v (ω) = T = v (ω), so we can directly rewrite [START_REF] Dean | Algorithms for minimum-cost paths in time-dependent networks with waiting policies[END_REF] as

T v (ω) = min (u,v)∈A T u (ω) + C uv (T u (ω) + ω). (9)
Grouping relations ( 8) and ( 9), T v (ω) satisfies the recurrence relation

T v (ω) = min inf 0≤ω <ω T v (ω ), min (u,v)∈A T u (ω) + C uv (T u (ω) + ω) . (10)
The bottom line of our algorithm is to build a sequence with polynomial length 0 = ω 1 , ω 2 , . . . , ω K = W such that relation [START_REF] Foschini | On the complexity of time-dependent shortest paths[END_REF] can be simplified to

T v (ω k+1 ) = min T v (ω k ), min (u,v)∈A T u (ω k+1 ) + C uv (T u (ω k+1 ) + ω k+1 ) , (11)
which can be equivalently formulated as

T v (ω k+1 ) = min {T v (ω k ), T = v (ω k+1 )} . (12)
Indeed, we show below that for such a sequence, {T u (ω k+1 )} u∈V can be computed in polynomial time from {T u (ω k )} u∈V using classical shortest path algorithms.

Proposition 1. Let {T v (ω k ), v ∈ V } be given and {T v (ω k+1 ), v ∈ V }
be a set of numbers that satisfy [START_REF] He | Computational complexity of timedependent shortest path problems[END_REF] and the initial conditions T o (ω k+1 ) = 0. Then, {T v (ω k+1 ), v ∈ V } can be computed by classical shortest path algorithms in O(SP P (n, m)).

Proof. We create a new instance of the problem defined on the graph G = (V , A ) and denote the travel time functions as C e for each e ∈ A . The new graph contains a copy of each node v different from the source, connected only to o and v, namely

V = V ∪ {v , ∀v ∈ V \ {o}} and A = A∪{(o, v ), ∀v ∈ V \{o}}∪{(v , v), ∀v ∈ V \{o}}. We further define the travel time functions as C ov (t) = 0 and C v v (t) = T v (ω k ) for all t ≥ 0 and v ∈ V \ {o}, while C uv (t) = C uv (t + ω k+1 ) for each (u, v) ∈ A. Denoting T v (ω k+1 ) as d v for each v ∈ V ,
and initializing d o = 0, and d v = +∞ for each v ∈ V \ {o}, one readily verifies that (11) can be reformulated as

d v = min (u,v)∈A d u + C uv (d u ),
the classical recurrence relations for the shortest path-problem in time-dependent networks. As G contains 2n -1 nodes and m + 2n -2 arcs, the problem can be solved in SP P (2n -1, m + 2n -2) ∈ O(SP P (n, m)) when the consistency assumption is satisfied (e.g. [START_REF] Orda | Shortest-path and minimum-delay algorithms in networks with timedependent edge-length[END_REF]).

We conclude the section by introducing useful properties of T v (ω) and TDSPW. First, we show that the consistency assumption implies that the left-derivative of T v (ω) is bounded below by -1.

Proposition 2. ∂ -T v (ω) ≥ -1 for all ω>0 and v ∈ V . Hence, ω → T v (ω) + ω is a non-decreasing function.
Proof. Consider ω > 0 and let (p, w) ∈ PW v (ω) be a path-with-waits from o to v that achieves T v (ω), so C(p, w) = T v (ω). Let v j be the last node along p for which wj > 0 and define w ∈ R n as w i = wi for i = j and w j = wj -δ for some 0 < δ ≤ wj , as well as ω = σ(p)-1 i=1

w i = ω -δ. We claim that C(p, w) -C(p, w) δ ≥ -1. (13)
Therefore,

T v (ω + (-δ)) -T v (ω) (-δ) = T v (ω) -T v (ω -δ) δ = T v (ω) -T v (ω) δ = C(p, w) - min (p ,w )∈PWv(ω) C(p , w ) δ ≥ C(p, w) -C(p, w) δ ≥ -1.
and the results follows by taking the limit for δ → 0 + . Let us now prove the claim [START_REF] Jabali | Analysis of travel times and co2 emissions in time-dependent vehicle routing[END_REF]. By definition, t p,w (j) = t p, w(j) -δ and, since ρ min ≥ -1, t p,w ( ) ≤ t p, w( ) for each j ≤ ≤ σ(p). In particular, t p,w (σ(p)) ≤ t p, w(σ( p)), and the claim follows from the relation C(p , w ) = t p ,w (σ(p )) -σ(p )-1 i=1 w i valid for any path-with-waits (p , w ).

Remark 1. The function T v (ω) is non-increasing for each v ∈ V . In contrast, function T = v (ω) may be increasing, as can be seen in the two-nodes example where V = {o, d} and A = {(o, d)} and C od (t) = min(t, W ). In that example, T = v (ω) = ω for each 0≤ω ≤ W .

Next we show that we can restrict our attention to acyclic solutions.

Proposition 3. TDSPW admits an acyclic optimal solution.

Proof. Consider a solution (p, w) such that p = (ν;

o = v 1 , . . . , v σ(p) = d) contains a cycle c = (ν c ; v i , v i+1 , . . . , v j )
, where v i = v j . Let C(c) be the travel time of cycle c in (p, w). By nonnegativity of arc travel times, we know that C(c) ≥ 0. As a consequence, if j = σ(p), we get a solution with smaller or equal cost by removing c and the associated waiting times from (p, w). If j < σ(p), let µ k = k =1 w and (p(k), w(k)) is the subpath-with-waits of (p, w) that goes from o to v k , for all k ∈ {2, . . . , σ(p)}. Assumption 1 ensures that

∂ + C uv ≥ -1, ∀(u, v) ∈ A, so C (p(j + 1), w(j + 1)) = C (p(i), w(i)) + C(c) + C v j v j+1 (C(p(i), w(i)) + C(c) + µ j ) ≥ C(p(i), w(i))) + C v j v j+1 (C(p(i), w(i))) + µ j ) = C (p(i), w(i)) + C v i v j+1 (C(p(i), w(i))) + µ i + (µ j -µ i )) ,
where the last expression is the travel time from o to v j+1 along (p, w) if we remove c and and wait an additional µ j -µ i at v i = v j . This shows that c can be removed without increasing the total travel time nor the total waiting time along the path-with-waits.

Structure of optimal paths

The sequence ω 1 , . . . , ω K will be constructed so that for all k = 1, . . . , K there is some arc (u, v) such that a breakpoint of C uv is reached at T u (ω k ) + ω k . The practical algorithm that identifies this sequence, provided in the next section, is based on the structure of the paths-with-waits that realize the minimum travel time T v (ω). For this, if (p, w) ∈ PW v (ω), we define (p(i), w(i)) and (p(i), w(i)) as the subpaths-with-waits of (p, w) respectively ending and starting at the i-th node of p. In this section, we provide key properties of the paths-with-waits that realize T v (ω) for each v ∈ V and ω ≥ 0. Specifically, we identify that these paths-with-waits can be split into two subpaths, the second of which contains no more waiting. This property will be essential to compute the values ω 1 , . . . , ω K by back-propagation in the following section. Definition 1. Let v ∈ V , 0 ≤ ω ≤ W and (p, w) ∈ PW v (ω) where p = (ν; v 1 := o, v 2 , . . . , v σ(p) = v) and w = (w 1 , . . . , w σ(p)-1 ). If there is i ≤ σ(p) -1 such that i k=1 w k = ω and i-1 k=1 w k = ω < ω, then (p(i), w(i)) is the saturated subpath of (p, w). By extension the nodes v i , . . . , v σ(p) = v are said to be saturated in (p, w) and v i is the first saturated node in (p, w).

From this definition, one can notice that the first saturated node of a path-with-waits is also the last one where the wait is positive. The introduction of this saturated subpath allows for a more precise characterization of optimal paths.

Proposition 4. Let v ∈ V , 0 ≤ ω ≤ W such that T v (ω) = T = v (ω). Then, there exists (p, w) ∈ PW v (ω) such that • C(p, w) = T v (ω), σ(p)-1 =1 w = ω, and
• C(p(j), w(j)) = T v j (ω) for every saturated node v j in (p, w).

In particular, T v j (ω) = T = v j (ω) for every saturated node v j after the first saturated node.

Proof. Let (p, w) ∈ PW v (ω) such that C(p, w) = T v (ω) and

σ(p)-1 =1 w = ω.
Assume that there is v j , a saturated node in (p, w), such that C(p(j), w(j)) > T v j (ω). There is (p j , w j ) ∈ PW v j (ω) such that C(p j , w j ) = T v j (ω) and σ(p j )-1 =1 w j = ω j ≤ ω. We can then build a path-with-waits (p , w ) from o to v with total wait ω, by appending (p(j), w(j)) to (p j , w j ) and waiting an additional ω -ω j at v j . Node v j is saturated in both (p, w) and (p , w ), so the departure time from v j is C(p(j), w(j))+ω in (p, w) and T v j (ω)+ω in (p , w ). And since (p, w) and (p , w ) are identical from v j to v, the consistency assumption and C(p(j), w(j))+ω > T v j (ω)+ω yields C(p, w) ≥ C(p , w ). From C(p, w) = T v (ω), we deduce that C(p , j ) = T v (ω). We thus obtain the desired path-with-waits by applying the above approach recursively on the saturated nodes until C(p(j), w(j)) = T v j (ω) for every saturated node v j .

The last assertion follows from the fact that the total wait along (p(j), w(j)) is exactly equal to ω.

Remark 2. We observe that if i is the first saturated node in (p, w), there is no wait from v i+1 to v in (p, w). If C(p, w) = T v (ω), this means that p(i) is the shortest path (without wait) from v i to v among those departing from v i at T v i (ω) + ω.

Remark 3. In the proof of Proposition 4, we use the consistency assumption to show that C(p(j), w(j))+ ω > T v j (ω) + ω implies C(p, w) ≥ C(p , w ). Actually, it can happen that C(p, w) = C(p , w ) only if there is an arc (v , v +1 ) in p such that ≥ j and C , +1 has a slope equal to -1 at C(p( ), w( ))+ω. As a consequence, if there is no such arc in the saturated subpath of (p, w), we can show that C(p, w) = T v (ω) directly implies that C(p(j), w(j)) = T v j (ω) for every saturated node v j .

Next we prove a property which, if satisfied by sequence ω 1 , . . . , ω K , directly implies that (12) holds.

Proposition 5. Let ω k+1 ≥ ω k be such that for all u ∈ V ,

T u (ω k+1 ) + ω k+1 ≤ τ u (ω k ). ( 14
)
Then for all v ∈ V , ω → T v (ω) is a continuous piecewise linear and concave function on [ω k , ω k+1 ].

Proof. See detailed proof in Appendix A.

Corollary 1. Let ω k+1 ≥ ω k be such that (14) holds. Then for all v ∈ V , (12) holds, i.e.,

T v (ω k+1 ) = min {T v (ω k ), T = v (ω k+1 )} . Proof. By concavity of T v on [ω k , ω k+1 ], T v is either constant on [ω k , ω k+1 ] or there is ω ∈ [ω k , ω k+1 ] such that T v is decreasing on [ω, ω k+1 ].
In the latter case, we get that

T v (ω) = T = v (ω) for all ω ∈ [ω, ω k+1 ]. In particular, T v (ω k+1 ) = T = v (ω k+1 ). To summarize, T v (ω k+1 ) = min {T v (ω k ), T = v (ω k+1 )}.
The above result allows to get more specific in the characterization of the first saturated node of the path exhibited in Proposition 4 when ω = ω k+1 for some integer k.

Corollary 2. Let 0 ≤ ω k < ω k+1 ≤ W such that (14) holds and consider v ∈ V such that T v (ω k+1 ) = T = v (ω k+1 ).
Then, there exists (p, w) ∈ PW v (ω k+1 ) such that

• C(p, w) = T v (ω k+1 ) and σ(p)-1 =1 w = ω k+1 ; • C(p(i), w(i)) = T v i (ω k )
, where v i is the first saturated node in (p, w);

• and C(p(j), w(j)) = T = v j (ω k+1 ) for every other saturated node v j .

Proof. Proposition 4 guarantees that there is (p, w) ∈ PW v (ω) such that C(p, w) = T v (ω k+1 ), σ(p)-1 =1 w = ω k+1 , and C(p(j), w(j)) = T v j (ω k+1 ) for every saturated node v j . Denoting the first saturated node as v i , we know that the total wait up to it in (p, w),

ω i = i-1 =1 w , is less than ω k+1 . As a consequence, C(p(i), w(i)) = T v i (ω k+1 ) yields T v i (ω) = T v i (ω k+1 ) for all ω ∈ [ω i , ω k+1 ], so that ∂ + T v i (ω) = 0 for ω ∈ [ω i , ω k+1 [. By concavity of T v i on [ω k , ω k+1 ], ∂ + T v i (ω) = 0 for ω ∈ [ω k , ω k+1 [, so we conclude that T v i (ω) = T v i (ω k+1 ) for all ω ∈ [ω k , ω k+1 ], and therefore, C(p(i), w(i)) = T v i (ω k ).
The above two results immediately yield the concluding result of the section, which is essential to the justification of the polynomial algorithm described in next section. Indeed, the path-withwaits realizing T v (ω k+1 ) can now be expressed as the concatenation of a path-with-waits up to some node u for a total wait not greater than ω k , and a path-without-waits leaving u at T u (ω k ) + ω k+1 . In particular, this means that given T u (ω k ) for all u ∈ V , we will be able to focus on such paths during the search for ω k+1 .

Theorem 2. Let 0 ≤ ω k < ω k+1 ≤ W such that (14) holds and consider v ∈ V . Then,

T v (ω k+1 ) = min T v (ω k ), min u∈V \{v} {T u (ω k ) + C (p u→v (ω k , ω k+1 ))} .
Observe that C (p v→v (ω k , ω k+1 )) = 0, ∀v ∈ V, so the above result can be equivalently written as

T v (ω k+1 ) = min u∈V {T u (ω k ) + C (p u→v (ω k , ω k+1 ))} .

Building the sequence

We describe next how to construct the sequence ω 1 , . . . , ω K = W , starting from ω 1 = 0 and increasing the value of ω k along the iterations. From Proposition 5, we wish to define the next iterate ω k+1 as the largest value (not greater than W ) such that for all v ∈ V , condition ( 14) is satisfied, i.e.,

T v (ω k+1 ) + ω k+1 ≤ τ v (ω k ).
Stated otherwise, ω k+1 is the next waiting value such that a breakpoint of an edge cost function is reached by T v (ω k+1 ) + ω k+1 for some v ∈ V . This leads us to define the sequence ω 1 , . . . , ω K = W as in the following theorem. With this definition, we guarantee that ( 14) is satisfied for all v ∈ V and that the sequence contains at most as many elements as the total number of breakpoints in the edge cost functions.

Theorem 3. Let ω 1 = 0 and consider the sequence defined recursively as

ω k+1 = min W, min v∈V max ω∈Ω {ω : T v (ω) + ω ≤ τ v (ω k )} (15)
Then, there is K ∈ {1, . . . , R} such that ω K = W , and ∀k ∈ {1, . . . , K -1}

T v (ω k+1 ) + ω k+1 ≤ τ v (ω k ), ∀v ∈ V. Proof. Let k ∈ {1, . . . , R -1}. Let v * ∈ arg min v∈V {max ω∈Ω {ω : T v (ω) + ω ≤ τ v (ω k )}} and ω v * = max ω∈Ω {ω : T v * (ω) + ω ≤ τ v * (ω k )}. If ω v * ≥ W , then (15) yields ω k+1 = W with k + 1 ≤ R. Otherwise, we get ω k+1 = ω v * , so T v * (ω k+1 ) + ω k+1 = τ v * (ω k ). By definition of τ v * (ω k+1 ), we know that τ v * (ω k+1 ) > T v * (ω k+1 ) + ω k+1 , so τ v * (ω k+1 ) > τ v * (ω k ).
Moreover, for any ω, τ v (ω) is the breakpoint of a cost function of an arc leaving from v. As a consequence, τ v * (ω k ) and τ v * (ω k+1 ) correspond to two different breakpoints.

Since the function ω → T v (ω)+ω is non-decreasing for all v ∈ V , we deduce that each breakpoint of each arc cost function can correspond to at most one element of the sequence ω 1 , . . . , ω K , hence K ≤ R.

Finally, the recursive definition of ω k+1 directly yields

T v (ω k+1 ) + ω k+1 ≤ τ v (ω k ), ∀v ∈ V.
We now wish to build the sequence ω 1 , . . . , ω K by using the recursive relation [START_REF] Omer | Time-dependent shortest path with discounted waits[END_REF]. Assuming that ω 1 , . . . , ω k are known for some k ≥ 1, it is not clear though how to use [START_REF] Omer | Time-dependent shortest path with discounted waits[END_REF] to actually compute ω k+1 , because we do not know the value of T v (ω) for ω > ω k . The contribution of this section is to construct a back-propagation algorithm that will be essential in computing these values. Ideally, such a back-propagation algorithm would construct reverse shortest paths from any given node v at time t based on the cost function C e for every e ∈ A; for instance, if (u, v) is an edge in such a shortest path, the algorithm would relate t and t through t = t + C uv (t ). An important difficulty faced by such an algorithm is that when back-propagating some time t along an arc (u, v), we do not know in which piece of the cost function C uv the arc has been entered. Somewhat surprisingly, we show in the section that for each arc, the only piece that matters is s e (ω k ) (see ( 1)), defined on the interval [τ

se(ω k )-1 e , τ se(ω k ) e
]. This allows to back-propagate the values of τ v (ω k ) along particulars paths that reach v at τ v (ω k ). Those are defined as follows.

Definition 2. Let u ∈ V, v ∈ V and ω ∈ [0, W ]. We denote as P back u→v (ω) the set of paths such that p = (ν; v 1 , . . . , v σ(p) ) ∈ P back u→v (ω) if and only if:

• v 1 = u, v σ(p) = v,
• p reaches v at τ v (ω), and

• t p (v i ) ∈ [T v i (ω) + ω, τ v i (ω)], for i = 1, . . . , σ(p) -1.
The departing time from u of the shortest path among P back u→v (ω) is then denoted as t u→v (ω), i.e.,

t u→v (ω) = τ v (ω) -min{C(p) : p ∈ P back u→v (ω)}, if P back u→v (ω) = ∅, + ∞, otherwise.
Out of completeness in the proofs, we also set t v→v (ω) = τ v (ω). The above also implies that

P back u→v (ω) = ∅ when τ v (ω) = +∞ (so t u→v (ω) = +∞ in that case).
Let us denote

V (ω k ) = arg min v∈V max ω∈Ω {ω : T v (ω) + ω ≤ τ v (ω k )} .
Before moving to the description of the actual back-propagation algorithm, we show below that ω k+1 can indeed be computed by searching for shortest paths in P back u→v (ω k ) for u ∈ V and v ∈ V (ω k ).

Proposition 6. Let ω 1 , . . . , ω K be constructed as in Theorem 3. Then, for each k ∈ {1, . . . , K -1} and v ∈ V (ω k ),

ω k+1 = min W, max u∈V {t u→v (ω k ) -T u (ω k )} . ( 16
)
Proof. See detailed proof in Appendix B.

Algorithm 1 details the back-propagation that will be used to search for shortest paths in P back u→v (ω k ). The algorithm requires that T u (ω k ) and τ u (ω k ) be already computed for all u ∈ V . Then for each input node v, it back-propagates the departure time τ v (ω k ) along paths of P back u→v (ω k ) for each u ∈ V with the aim of computing t u→v (ω k ). One additional difficulty is that Proposition 6 is only concerned with nodes that belong to V (ω k ), which are not known at this stage. The focus of what follows will thus be to show that Algorithm 1 returns max u∈V {t u→v (ω k ) -T u (ω k )} for at least one input node v ∈ V (ω k ), and that it returns a larger or equal value for every other node (see Lemma 1). As a consequence, Proposition 6 guarantees that ω k+1 will be found by considering the smallest value returned by Algorithm 1 among every node.

For more insight into the back-propagation, first observe that by definition of τ u (ω k ) and

τ - u (ω k ) (see (2)), we know that τ - u (ω k ) ≤ T u (ω k ) + ω k < τ u (ω k ) for all u ∈ V . As a consequence, if p ∈ P back u→v (ω k ), then t p (v j ) ∈ [τ - v j (ω k ), τ v j (ω k )] for all v j ∈ p. If (u, w
) is an edge of a path in p ∈ P back u→v (ω k ), we can then relate t p (u) and t p (w) through the formula

t p (w) = t p (u) + C uw (t p (u)) = t p (u) + ρ suw(ω k ) uw t p (u) + c suw(ω k ) uw . (17)
This formula justifies that steps 6-16 of Algorithm 1 describe a backward label-setting algorithm.

In these steps the departure times at u ∈ V , t u , is updated until the shortest path in P back u→v (ω k ) is found or until we can prove that the back-propagation of τ v (ω k ) is not useful. The non-marked node with largest departure time, w, is selected and marked at steps 7-10, among which steps 8 and 9 ensure that t w ∈ [T w (ω k ) + ω k , τ w (ω k )]. As we will show in Lemma 2 presented in Appendix C, if the conditions checked at these steps are both wrong, then t w = t w→v (ω k ). Formula ( 17) is then used to update t u for every arc (u, w) at steps 11-16, wherein steps 15-16 address the special case ρ suw(ω k ) uw = -1. When this happens, (17) becomes t p (w) = c suw(ω k ) uw , so the departure time at w does not depend on the departure time at u. If c suw(ω k ) uw > t w , this means that w can never be reached early enough to get to v at τ v (ω k ) by taking arc (u, w). We can thus skip this iteration in the for loop. If c suw(ω k ) uw ≤ t w , we show in Lemma 2 presented in Appendix C that the back-propagation of τ v (ω k ) can be stopped here to treat another node.

The execution of the back-propagation loop is described formally in the following proposition. This will be essential to prove the overall validity of Algorithm 1.

We are now ready to prove that the overall approach is valid, that is, ω k+1 = min{W, min v∈V ω v }, where ω v is the value returned by Algorithm 1 when back-propagating τ v (ω k ).

Lemma 1. For all v ∈ V , denote as ω v the value returned by Algorithm 1 when back-propagating

τ v (ω k ). There is v * ∈ arg min v∈V {max ω∈Ω {ω : T v (ω) + ω ≤ τ v (ω k )}} such that 1. ω v * = max u∈V {t u→v * (ω k ) -T u (ω k )}, and 2. ω v ≥ ω v * , ∀v ∈ V .
Proof. See detailed proof in Appendix C. Corollary 3. Let ω 1 , . . . , ω k be defined recursively as in Theorem 3. For all v ∈ V , denote as ω v the value returned by Algorithm 1 when back-propagating τ v (ω k ). Then,

min v∈V {ω v } = min v∈V {max u∈V {t u→v (ω k ) -T u (ω k )}}.
Proof. The result is the direct consequence of Lemma 1 and Proposition 6.

input: ω k , v ∈ V, τ u (ω k ), T u (ω k ), ∀u ∈ V, 1 V ← V 2 S ← ∅ // set of marked nodes 3 t u ← -∞, ∀u ∈ V 4 t v ← τ v (ω k ) 5 if τ v (ω k ) = +∞ then ω v ← +∞, go to step 18 6 while S = V do 7 select w in arg max u∈V \S {t u } 8 if t w > τ w (ω k ) then ω v ← +∞, go to step 18 // τw(ω k ) is reached before τv(ω k ) 9 if t w < T w (ω k ) + ω k then V ← V \ {w},
(ω k ) uw > -1 then t u ← max t u , tw-c suw (ω k ) uw 1+ρ suw (ω k ) uw 14 else 15 if c suw(ω k ) uw ≤ t w then ω v ← +∞, go to step 18 // τu(ω k ) is reached before τv(ω k ) 16
else continue // tw will not be reached with this arc, skip arc (u, w)

17 ω v ← max u∈V {t u -T u (ω k )} 18 return ω v Algorithm 1: Back-propagation of τ v (ω k ).
The above shows that we can solve TDSPW by executing Algorithm 2. The construction of the sequence ω 1 , . . . , ω K is done by repeated executions of Algorithm 1 (step 4) so Corollary 3 ensures that the sequence satisfies the recursive definition of Theorem 3. According to Theorem 3 and Corollary 1, we then know that Proposition 1 applies, so the computation of T v (ω k ), ∀v ∈ V, can be done by executing a shortest path algorithm. This yields the main result of the article, stated in Theorem 4.

initialization: k = 1, ω 1 = 0, ω 0 = -1, T v (ω 0 ) = +∞ ∀v ∈ V \ {o}, T o (ω 0 ) = 0 1 repeat 2 for v ∈ V do compute T v (ω k ) using a shortest path algorithm 3 for v ∈ V do compute τ v (ω k ) 4 for v ∈ V do ω v ← result of the back-propagation of τ v (ω k ) with Algorithm 1 5 ω k+1 = min (W, min v∈V ω v ) 6 k ← k + 1 7 until ω k = W 8 return T v (W ), ∀v ∈ V Algorithm 2: Computing T d (W ). Theorem 4. Algorithm 2 solves TDSPW in O(n × R × SP P (n, m)).
Proof. The validity of the algorithm has already been justified in the discussion preceding the statement of the theorem. So we only prove the complexity result.

Corollary 3 shows that the sequence ω 1 , . . . , ω K is constructed as expected, so Theorem 3 justifies that K is at most equal to the total number of breakpoints in the arc cost functions. At each iteration, a shortest path algorithm is called once to compute T v (ω k ), ∀v ∈ V , and Algorithm 1 needs to be called n times. Furthermore, Algorithm 1 is essentially a time-dependent shortest path problem without waiting on a digraph, which can be solved in SP P (n, m).

Acknowledgements

We thank the referees for their constructive comments that have helped improving the presentation of the paper.

A Proof of Proposition 5

We prove the result by contradiction, so assume that there is v ∈ V such that ω → T v (ω) is not concave on [ω k , ω k+1 ]. We have already observed that T v is a continuous piecewise linear function, so it is not concave if and only if there is ω ∈ ]ω k , ω k+1 [ such that T v is not differentiable at ω and

∂ -T v (ω) < ∂ + T v (ω) (18)
In particular, (18) involves that ∂ -T v (ω) < 0, so T = v (ω) = T v (ω). According to Proposition 4, this means that we can build (p, w) ∈ PW v (ω) such that C(p, w) = T v (ω), σ(p)-1 =1 w = ω, and, denoting p = (ν; v 1 (= o), v 2 , . . . , v σ(p) = v), C(p(j), w(j)) = T v j (ω) for every saturated node v j in (p, w). Let v i be the first saturated node in (p, w). To exhibit the contradiction, we study the function

f : [-w i , W -ω] → R + → C (p, w + δ(i)) ,
where δ(i) is the i-th vector of the canonical basis of R σ(p) (δ i (i) = 1 and δ j (i) = 0, for j = i). Stated otherwise, f ( ) is the cost of (p, w + δ(i))), the path-with-waits from o to v obtained from (p, w) by waiting an additional at node v i . Since the arc cost functions are piecewise linear and continuous, so is f . As a consequence, we can compute the left and right partial derivative of f at 0 as

       ∂ -f (0) = lim →0- C(p, w + δ(i)) -C(p, w) = lim →0- C(p, w + δ(i)) -T v (ω) ∂ + f (0) = lim →0+ C(p, w + δ(i)) -C(p, w) = lim →0+ C(p, w + δ(i)) -T v (ω)
Observing that (p, w + δ(i)) is a path-with-waits from o to v with total wait ω + , we get C(p, w + δ(i)) ≥ T v (ω + ) which yields

       ∂ -f (0) ≤ lim →0- T v (ω + ) -T v (ω) = ∂ -T v (ω) ∂ + f (0) ≥ lim →0+ T v (ω + ) -T v (ω) = ∂ + T v (ω)
Together with (18), we get

∂ -f (0) ≤ ∂ -T v (ω) < ∂ + T v (ω) ≤ ∂ + f (0),
which implies in particular that f is non-differentiable at 0. By definition, f ( ) is the sum of composites of the piecewise-linear arc cost functions C v j v j+1 , j = 1, . . . , σ(p) -1. For j = 1, . . . , i the term related to C v j v j+1 is taken at C(p(j), w(j)) + j-1 k=1 w k , which does not depend on . For j = i + 1, . . . , σ(p) -1 the term related to C v j v j+1 is taken at C(p(j), w(j) + δ(i)) + ω + . Let v j be a saturated node (j ∈ {i, . . . , σ(p)}): using that C(p(j), w(j)) = T v j (ω) and

ω k ≤ ω ≤ ω k+1 , we get τ - v j (ω k ) ≤ C(p(j), w(j)) + ω ≤ τ v j (ω k ). Recalling that C v j v j+1 is differentiable on ]τ - v j (ω k ), τ v j (ω k )[
, for all (v j , v j+1 ) ∈ A, we get that f is non-differentiable at = 0 only if there is a saturated node v j such that the piece where C v j v j+1 is evaluated changes at = 0, i.e., i. T v j (ω) + ω = τ - v j (ω k ) and ∃α > 0 : C(p(j), w(j) -νδ(i)) + ω -ν < τ - v j (ω k ) for all 0 < ν < α; or ii. T v j (ω) + ω = τ v j (ω k ) and ∃α > 0 : C(p(j), w(j) + νδ(i)) + ω + ν > τ v j (ω k ) for all 0 < ν < α.

If T v j (ω) + ω = τ - v j (ω k ), τ - v j (ω k ) ≤ T v j (ω k ) + ω k yields T v j (ω) + ω = T v j (ω k ) + ω k , hence ∂ -T v j (ω) = -1. Function T v j is piecewise linear, so there is α > 0 such that for all 0 < ν < α, T v j (ω -ν) = T v j (ω) + ν. Using that C(p(j), w(j) -νδ(i)) ≥ T v j (ω -ν), we obtain C(p(j), w(j) -νδ(i)) + ω -ν ≥ T v j (ω) + ω ≥ τ - v j (ω k ), so item i. is never true. If T v j (ω)+ ω = τ v j (ω k ), then T v j (ω)+ ω = T v j (ω k+1
)+ω k+1 by [START_REF] Kaufman | Fastest paths in time-dependent networks for intelligent vehicle-highway systems application[END_REF]. A path-with-waits from o to v j that realizes T v j (ω k+1 ) with total wait ω k+1 will then arrive at T v j (ω k+1 )+ω k+1 = T v j (ω)+ω. So if we follow p from there without additional waits, v will also be reached at T v (ω)+ ω, just like in (p, w). Denoting this new path-with-waits as (p , w ), we get that

C(p , w ) = T v (ω) + ω -ω k+1 . Finally, C(p , w ) ≥ T v (ω k+1 ), hence T v (ω k+1 ) + ω k+1 ≤ T v (ω) + ω. This is only possible if ∂ + T v (ω) = -1 for all ω ∈ [ω, ω k+1 ], which is in contradiction with ∂ -T v (ω) < ∂ + T v (ω)
. We conclude that item ii. is never true either, hence f is differentiable at 0: a contradiction.

B Proof of Proposition 6

Let k ∈ {1, . . . , K -1}, and v ∈ arg min u∈V {max ω∈Ω {ω : T u (ω) + ω ≤ τ u (ω k )}}. If τ v (ω k ) = +∞, then both ( 15) and ( 16) yield ω k+1 = W , proving the desired equality.

Thus, we suppose next that τ v (ω k ) < +∞ and define

ω = max ω∈Ω {ω : T v (ω) + ω ≤ τ v (ω k )}. ( 19
)
Theorem 3 states that we are in the conditions of application of Corollaries 1 and 2. Using Corollary 1, we get

T v ( ω) = min {T v (ω k ), T = v ( ω)} . 1. If T v ( ω) = T v (ω k ), we use that t v→v (ω k ) = τ v (ω k ) = T v ( ω) + ω (by definition of v and t v→v ) to observe that ω = t v→v (ω k ) -T v (ω k ). 2. Otherwise, T v ( ω) = T = v ( ω), so by Corollary 2, there are v i ∈ V and a path p from v i to v such that t p (v i ) = T v i (ω k )+ ω, t p (v j ) = T v j ( ω)+ ω, ∀v j ∈ p, v j / ∈ {v i , v} and T v i (ω k )+C(p) = T v ( ω). By definition of ω, T w ( ω) + ω ≤ τ w (ω k ), ∀w ∈ p. Since ω → T w (ω) + ω is non-decreasing for all w ∈ V , we see that p reaches v at τ v (ω k ) and every intermediary node v j in the time interval [T v j (ω k ) + ω k , τ v j (ω k )]. Stated otherwise, p ∈ P back v j →v (ω k ). This means in particular that τ v (ω k ) -min{T u (ω k ) + C(p) : u ∈ V, p ∈ P back u→v (ω k )} ≥ τ v (ω k ) -T v ( ω) = ω.
By definition of t u→v (ω k ), we get that in both cases above:

ω ≤ max u∈V {t u→v (ω k ) -T u (ω k )}. ( 20
)
To show the reverse equality, let u ∈ V and p ∈ P back u→v (ω k ), and let ω = τ v (ω k ) -(T u (ω k ) + C(p)) (notice ω ≥ ω k by definition of P back u→v (ω k )). Then T u (ω k ) + C(p) is the the cost of a path-with-waits from o to v that reaches u at T u (ω k ) and v at τ v (ω k ) with a total wait equal to ω. We thus get that T v (ω) + ω ≤ τ v (ω k ). Using (19), this implies that ω ≤ ω, and since the above is valid for any u and any p ∈ P back u→v (ω k ): To prove item 3., assume that t w > τ w (ω k ) at some execution of step 7. Let p be the path from w to v constructed by the back-propagation. First we have, by non-negativity of arc travel times, t w ≤ τ v (ω k ), so τ w (ω k ) < τ v (ω k ).

Then, denote as v + the successor of w in p. Let ω = max ω {T w (ω) + ω ≤ τ w (ω k )} and let (p w , w w ) ∈ PW w (ω ) be a path-with-wait from o to w that reaches w at τ w (ω k ) < t w with a total wait equal to ω . Taking arc (w, v + ) immediately after p w (no wait at w), v + is reached at To prove item 4., first observe that if we are back-propagating the value of t w , this means that T w (ω k ) + ω k ≤ t w ≤ τ w (ω k ), hence t w = t w→v (ω k ). Now let (u, w) ∈ A such that ρ suw(ω k ) uw = -1 and c suw(ω k ) uw ≤ t w . Let ω u = max ω∈Ω {ω : T u (ω) + ω ≤ τ u (ω k )}. There is a path-with-wait (p u , w u ) ∈ PW u (ω u ) such that C(p u , w u ) = T u (ω u ). For any path-with-wait (p, w) that goes though arc (u, w), if τ - u (ω k ) ≤ t p,w (u) ≤ τ u (ω k ), then by definition of (u, w), t p,w (w) = c suw(ω k ) uw ≤ t w . As a consequence, we can extend (p u , w u ) by

t + =
• departing from u at T u (ω u ) + ω u = τ u (ω k ),

• waiting an additional ω = t w -c suw(ω k ) uw at w,

• and taking the shortest path in P back w→v (ω k ) to reach v at τ v (ω k ).

Denoting this path-with-wait as (p v , w v ), we see that it accumulates a total wait ω v = ω u +ω ≥ ω u . Given that (p v , w v ) reaches v at τ v (ω k ), we have We are now ready to prove Lemma 1.

T v (ω v ) + ω v ≤ C(p v , w v ) + ω v = τ v (ω k ).
Proof of Lemma 1. To prove item 1., let v * ∈ arg min v∈V (ω k ) {τ v (ω k )}. We then consider the backpropagation of τ v * (ω k ) by Algorithm 1. By contraposition of item 3. of Lemma 2, we know that

10 S

 10 go to step 7 // impossible to backtrack to w late enough ← S ∪ {w} // mark node w 11 for (u, w) ∈ A // back-propagation loop of tw to its predecessors

ω

  ≥ τ v (ω k ) -min (T u (ω k ) + C(p)) : u ∈ V, p ∈ P back u→v (ω k ) = max u∈V {t u→v (ω k ) -T u (ω k )}. (21)Combining (20) and (21) and yieldsω = max u∈V {t u→v (ω k ) -T u (ω k )}.Finally, we can rely on (19) to see that the above actually proves that maxω∈Ω {ω : T v (ω) + ω ≤ τ v (ω k )} = max u∈V {t u→v (ω k ) -T u (ω k )},proving the result whenever τ v (ω k ) < +∞.

  (22) Stated otherwise, we haveτ v (ω k ) = C(p , w ) + ω (p ,w ) where C(p , w ) ≥ T v (ω (p ,w ) ), so T v (ω (p ,w ) ) + ω (p ,w ) ≤ τ v (ω k ). This yields that max ω∈Ω {ω : T v (ω) + ω ≤ τ v (ω k )} ≥ ω (p ,w ) ≥ ω = max ω∈Ω {ω : T w (ω) + ω ≤ τ w (ω k )}.

  v (ω) + ω ≤ τ v (ω k )} ≥ ω v ≥ ω u = max ω∈Ω {ω : T u (ω) + ω ≤ τ u (ω k )}.

  τ w (ω k ) + ρs wv + (ω k ) wv + τ w (ω k ) + c s wv + (ω k ) wv +. By τ w (ω k ) < t w , we know that v + is reached earlier in this path than in p, i.e., t + ≤ t v + . If we then wait t v + -t + at v + , we can take the end of p from v + to reach v at τ v (ω k ). Now, if (p , w ) is the path-with-wait from o to v constructed above, we get that (p , w ) reaches v at τ v (ω k ) with a total wait ω (p ,w ) = ω + t v + -t + ≥ ω .

C Proof of Lemma 1

Before proving the lemma, we introduce the following technical result that will be instrumental in proving Lemma 1.

Lemma 2. Consider the node w selected at an execution of step 7 of Algorithm 1, i.e., w ∈ arg max u∈V \S {t u }. We have that 1. if T w (ω k ) + ω k ≤ t w ≤ τ w (ω k ), t w = t w→v (ω k ); 2. if t w < T w (ω k ) + ω k , then P back w→v (ω k ) = ∅;

3. if t w > τ w (ω k ), then τ w (ω k ) < τ v (ω k ) and

Proof. One can verify that the first three items are satisfied if the conditions checked at steps 8 and 9 have been false since the beginning of the execution of Algorithm 1. Indeed, in such case, the algorithm is a plain back-propagation for the computation of shortest paths with affine arc costs.

The complete proof of items 1. and 2. is by induction on the number of executions of step 7. At the first execution of this step, w = v, so t w = τ v (ω k ) = t v→v (ω k ) by definition. Hence items 1. and 2. are true.

We now consider a later execution of step 7, where w ∈ arg max u∈V \S {t u }, assuming that the two items hold at each previous iteration. For every node u selected at a previous execution of step 7, the definition of the algorithm involves that u

This means that for all marked nodes u ∈ S, t u = t u→v (ω k ), and that no path in P back u→v (ω k ) goes through a node of V \ V . Moreover, t u > τ u (ω k ) did not happen, otherwise the algorithm would have been terminated.

To show item 1., observe that we would have obtained the same value for t w if the backpropagation had been run on the subgraph induced by V . Moreover, the nodes of V \ V are not involved in the paths of P back w→v (ω k ), so t w→v (ω k ) can be computed by considering the subgraph induced by V . In this subgraph, the conditions checked at steps 8-9 would have been false at every previous iteration, so if

The proof of item 2. is by contradiction. Assume that t w < T w (ω k ) + ω k and that there is p ∈ P back w→v (ω k ) = ∅. Then let p = (t p ; v 1 (= w), v 2 , . . . , v σ (p)(= v)) be the shortest path in P back w→v (ω k ). If every node in p is marked, then let i = 1. Otherwise, let v i be the first non-marked node in p, i.e., v i / ∈ S and v j ∈ S for j ∈ {i + 1, . . . , σ(p)}. Since p is a shortest path, then t p (v j ) = t v j →v (ω k ) for every marked node v j = w of p. Moreover, the back-propagation along the arcs of v i+1 ensures that t v i ≥ t p (v i ). By definition, w ∈ arg max u∈V \S {t u }, so t w ≥ t v i ≥ t p (v i ). And given that p goes through w before v i , t p (w) ≤ t p (v i ). As a consequence, t p (w) ≤ t w < T w (ω k ) + ω k , which is in contradiction with the definition of P back w→v (ω k ).

for all w selected at step 7 of Algorithm 1, t w ≤ τ w (ω k ). As a consequence, items 1. and 2. of Lemma 2 guarantee that at step 17 of Algorithm 1

We now prove that

At step 4 of Algorithm 1, we initialize t v to τ v (ω k ), and this value is not modified in the rest of the algorithm, hence

, and let (p, w) be a path-with-waits constructed as in Corollary 2 so that

, where v i is the first saturated node in (p, w);

• and C(p(j), w(j)) = T v j (ω v * ) for every other saturated node v j .

In particular, (p, w) connects v i to v without waits (after v i ) with a cost equal to

We claim that the subpath of p leaving from v i , p(i), is in P back v i →v (ω k ). By definition of t v i →v (ω k ), τ v (ω k ) -t v i →v (ω k ) is the minimum cost of a path in P back v i →v (ω k ), so the claim yields

Moreover, if ω v < +∞, then Lemma 2 yields that t u = t u→v (ω k ) for all v ∈ V and P back u→v (ω k ) = ∅ for u ∈ V \ V . As a consequence, ω v = max u∈V {t u→v (ω k ) -T u (ω k )}. In particular, this means that

where the last inequality follows from τ

To prove the claim, observe that (p, w) reaches

we observe that if we back-propagate τ v (ω k ) from v to v i along p(i), we necessarily reach the intermediary nodes v j later than when backpropagating T v (ω v * ) + ω v * , i.e., later than T v j (ω v * ) + ω v * . Moreover, if one intermediary node is reached later than τ v j (ω k ), then Algorithm 1 necessarily stops at step 8, which is not possible if ω v < +∞. By T v j (ω v * ) + ω v * ≥ T v j (ω k ) + ω k , we get that every intermediary node v j is also reached in the time interval [T v j (ω k ) + ω k , τ v j (ω k )] when back-propagating τ v(ω k ) from v to v i along p(i).


Marta Barbero

Inés M Gómez-Chacón
email: igomezchacon@mat.ucm.es

Ferdinando Arzarello

BACKWARD REASONING AND EPISTEMIC ACTIONS IN STRATEGIC GAMES PROBLEMS

Keywords: Teaching and learning of specific topics in university mathematics, Teaching and learning of logic, reasoning and proof, backward reasoning, epistemic actions, strategy games

This paper focuses on the epistemic and cognitive characterization of backward reasoning in strategy games resolution. It explores the use of AiC (Abstraction in Context) as a tool for the analysis of the epistemic actions involved in these processes. It is reported a first analysis developed by the research team in order to be used as protocol-guide in the analysis of a study carried out with PhD students in Mathematics Degree in a Spanish and an Italian University, who face problem solving games. The case study shows the process of discovery that a PhD student makes to formulate a general recursive formula. It is a key for understanding the interaction between the AiC model and the characteristics of backward reasoning. The analysis allows to combine the two models -backward reasoning and AiC -in a unified framework that allows to focus both short-term and long-term processes in students' activities.

INTRODUCTION

Backward reasoning has great potential in the study of mathematics since it can support students when engaged in tasks, where they are asked to pass from argumentations and inquiry to mathematical proofs. For deepening this issue we specifically developed some studies at the university level focussed on mathematical thinking, where learning the method of analysis is a critical issue [START_REF] Antonini | Generating examples: focus on processes[END_REF][START_REF] Peckhaus | Regressive Analysis[END_REF].

In such studies, which analysed mathematics and engineering students involved in problem solving activities [START_REF] Barbero | Analyzing Regressive reasoning at university level[END_REF][START_REF] Gómez-Chacón | Situation Specific-Skills Working Backward Reasoning: The Student's Perceptions and Affect Dimension[END_REF], it was noted that so-called regressive reasoningas an emerging key process in the dialectics between inference processesdevelops mainly in interrogative movements and is responsible for the generation of new ideas and elements in the solution process. This reasoning is used in its character of "ordering device": through it, the students manage to find elements necessary for the construction/definition of the objective. The backward reasoning, which is based on the return of reasoning to an informal context, helps to connect more intuitive aspects with the mathematical and computational context.

In standard mathematical problems, it is more difficult working backwards than forwards. So it is necessary to offer students a large class of problems to which the method of working backwards is appropriate, such as strategy games presented here. We also identified some factors in the cognitive and affect interplay, which would inevitably cause difficulties for students to construct and work backwards. These studies [START_REF] Gómez-Chacón | Emotions and heuristics: the state of perplexity in mathematics[END_REF] showed how the epistemic emotions continually exert numerous so-called operator effects, both linear and nonlinear, on attentional activity and on the ability to perceive goal-path obstacles and to overcome them. Understanding is linked with the appraisal of their ability to influence (control dimension), with their ability to predict, and with mental flexibility [START_REF] Gómez-Chacón | Emotions and heuristics: the state of perplexity in mathematics[END_REF][START_REF] Gómez-Chacón | Situation Specific-Skills Working Backward Reasoning: The Student's Perceptions and Affect Dimension[END_REF]. The dectected taxonomy of obstacles suggests that the lecturer, as a mediator of knowledge, explicitly takes into account the nature of backward reasoning underlying the interplay between epistemological and cognitive models. This paper focuses on the epistemic and cognitive characterization of backward reasoning in strategy games resolution. Strategy games allow for the natural development of backward reasoning. Players must make strategic choices to make their moves. These choices are triggered by typical implicit questions that players ask before making a new move: "What can I do in this situation? What is better to do?" To answer these typically strategic questions, they reflect both on the moves already made and on the possible moves to do and they activate the backward reasoning [START_REF] Wickelgren | How to solve problems. Elements of a theory of problems and problem solving[END_REF].

We explore the use of AiC (Abstraction in Context) as a tool for the analysis of the epistemic actions involved in these processes of resolution. We try to understand how the process of abstraction evolves, analyzing the relationship established between the epistemic actions (categories) of the RBC model of Dreyfus and Kidron (2014), and it is based on the perspective of abstraction in AiC context [START_REF] Hershkowitz | Abstraction in context: Epistemic actions[END_REF], as well as by the subcategories of analysis introduced in this investigation based on the specific characteristics of the regressive reasoning. Epistemic actions are understood as mental actions that develop during the abstraction process and explain the emergence of a new, more elaborate and complex construction. We report a first analysis developed by the research team in order to be used as protocol-guide in the analysis of a study carried out with 185 undergraduate students in Mathematics Degree. Further analysis can be found in [START_REF] Barbero | Backward Reasoning and Epistemic Actions in Discovering Processes of Strategic Games Problems[END_REF].

The structured as follows: first the theoretical frame underlying the analytical methodology of the study; second, the context of the study description and its particular goals; third, first results presentation, drawn from a case study micro-analysis, where the theoretical background is applied; finally, a discussion and some conclusions.

BACKWARD REASONING

In mathematics, progressive reasoning alone is not exhaustive to fulfil the tasks of solving problems. Great mathematicians like Pappus, Descartes, Leibniz, in their discussions about analysis and synthesis, emphasize this fact [START_REF] Peckhaus | Regressive Analysis[END_REF]. Backward reasoning is known by different denominations, each underlying some of its main features: regressive analysis, backward solution, method of analysis, etc. It is the practice that involves the making of a number of arguments from the bottom of the problem and proceeds through logical correspondences which allow to obtain something known or to be reached through other paths. This process includes different ways of proceeding in problem solving: Backward heuristics, Reductio ad Absurdum, Starting with the end of the problem, Assuming the problem solved [START_REF] Beaney | Analysis[END_REF].

Pappus was the mathematician who has contributed substantially to the clarification and exemplification of the method. In the seventh book of his Collection he deals with the topic of Heuristics (methods to solve the problems). There he exemplifies the method of analysis as the method of synthesis, therefore making the development of this reasoning clearer. Pappus defines the method of analysis as follows: "In analysis, we start from what is required, we take it for granted; and we draw correspondence (ακολουθον) from it and correspondence from the correspondence, till we reach a point that we can use as a starting point in synthesis. That is to say, in analysis we assume what is sought as already found (what we have to prove as true)." (elaboration by Polya, 1965 and by [START_REF] Hintikka | The Method of Analysis: Its Geometrical Origin and Its General Significance[END_REF]. Subsequently he points out: "This procedure we call analysis, or solution backward, or regressive reasoning." [START_REF] Hintikka | The Method of Analysis: Its Geometrical Origin and Its General Significance[END_REF]. And on the Method of Synthesis: "In synthesis, on the other hand, we suppose that which was reached last in analysis to be already done, and arranging in their natural order as consequents the former antecedents and linking them one with another, we in the end arrive at the construction of the thing sought. This procedure we call synthesis, or constructive solution, or progressive reasoning." [START_REF] Hintikka | The Method of Analysis: Its Geometrical Origin and Its General Significance[END_REF] The two processes are closely related and there is no analysis method without the synthesis one. Solving a problem is therefore a combination of the two procedures. [START_REF] Peckhaus | Regressive Analysis[END_REF] studies this analysis-synthesis scheme and affirms that "The analytical [is] […] the procedure which starts with the formulation of the problem and ends with the determination of the conditions for its solution. The synthetical represents the way from the conditions to the actual solution of the problem. […] This branch of the scheme is deeply connected with the complementary [one]." Not only analysis can't exist without synthesis but also "synthesis can't be isolated and presupposes analysis."

The concept of Backward Reasoning involves characteristics that allow us to identify its development throughout the resolution of a task. Philosophers and mathematicians from the ancient Greeks, through the authors from the 17th and 18th centuries to the 20 th one have studied its characteristics. The main features are the following:

-Direction vs cause-effect. In Pappus' definition, the backward direction of reasoning is highlighted. This entails going from the end of the problem to its beginning. By applying the method, the premises of a certain idea are sought. In the 17th and 18th centuries, authors such as Arnauld and Nicole interpreted the method as a search for cause-effect relationships between ideas. By these, the connection between the notions in background and the problem are identified. The knowledge of the development of the resolution of the task and the effects and causes of each notion involved in the process arise [START_REF] Beaney | Analysis[END_REF]Peckhaus, 2002).

-Decomposition. According to Plato and Pappus, this kind of reasoning allows for the reduction of the problem to its simplest components. The properties that define the assignment and the relationships between the most complex and the simplest objects involved in it are identified by extracting and investigating the principles that are at the base of the task. Aristotles, for example, underlines the fact that "sometimes, to solve a geometrical problem, you can only analyse a figure", breaking it down into its basic components and understanding the different parts of it [START_REF] Beaney | Analysis[END_REF].

-Introduction of auxiliary elements. Kant, Polya and Hintikka, focus their attention on a fundamental process part: the introduction of new elements (a known Geometry practice: the auxiliary constructions). In the progressive and deductive processes all the bases are given and from these, consequences are elaborated. Unlike the backward reasoning, new notions appear and develop throughout the resolution at specific moments, according the solver needs [START_REF] Beaney | Analysis[END_REF][START_REF] Hintikka | The Method of Analysis: Its Geometrical Origin and Its General Significance[END_REF].

EPISTEMIC ACTIONS

The concept of epistemic action was introduced into cognitive sciences by [START_REF] Kirsh | On distinguishing epistemic from pragmatic action[END_REF] to indicate those physical actions that facilitate cognition and allow problems to be solved more quickly. These actions help to acquire useful information for the resolution that are hidden or difficult to compute mentally, have the purpose to simplify the mental processes. In mathematics education the term was first used by Hershkowitz, Schwarz y Dreyfus, ( 2001), who derived it from [START_REF] Pontecorvo | Arguing and reasoning in understanding historical topics[END_REF] in their research on abstraction. The mental processes that occur in the student when solving a problem are not directly observable but can be identified through the analysis of the students' verbalisation or their physical actions. Epistemic actions are those actions that allow to identify the mental progresses in which knowledge is used or built and to operationally describe the procedures. They develop within the argumentative processes and are the basis of the interpretative activities. The actions involve procedures of a high methodological and metacognitive level and include the explanation of those procedures used for the interpretation of particular events.

The research of the last twenty years has resulted in the development of the theory of Abstraction in Context (AiC) (Dreyfus and Kidron, 2014) which aims to provide a theoretical and methodological approach, at the micro level, on the processes of learning mathematical knowledge. From a theoretical point of view, AiC attempts to create a bridge between cognitive knowledge and theories of abstraction, constructivist theory and the theory of activity. From a methodological point of view, AiC is a tool that allows the analysis of thought processes. The central theoretical construct of AiC is a theoretical-methodological model, according to which the emergence of a new construct is described and analyzed by means of three observable epistemic actions: recognizing (R), building-with (B), and constructing (C).

-

Recognizing. It consists in recognizing some previously learned knowledge as relevant for the resolution of the problem.

-Building-with. It consists of combining a set of knowledge with the aim of achieving a specific objective. Objectives can be: to implement a strategy, to meet a justification to a conjecture, to find the solution to the problem.

-Constructing. It consists in assembling and integrating the previous knowledge with the aim of producing a new construct.

RESEARCH AIM AND METHODOLOGY

Aim

The aim of this paper is to show the use of AiC combined with the characterization of backward reasoning as a tool for the analysis of the epistemic actions involved in discovery processes. Both epistemic and cognitive elements are highlighted to examine how university students develop backward reasoning.

Participants and instrument

Data were collected in 2018 from 185 Spanish and Italian mathematics students, aged between 19 and 30. The participants students are spread all over all the years of academic studies from the first year of Bachelor to the last year of PhD (Table 1 To study the epistemic and cognitive characterization of backward reasoning in strategy games resolution we choose the 3D Tic-Tac-Toe [START_REF] Golomb | Hypercube Tic-Tac-Toe, in: More Games of No Chance[END_REF]. This is a finite 2 players game with perfect information. Generally, it is played with paper and pencil. The board of the k-dimensional Tic-Tac-Toe (k>1) is a k-dimensional cube of side n, i.e. a (n, k)-board. The two players choose to adopt "X" or "O" to indicate the position of their pawns on the board. The game version used for the this research project experiments consists of a (4,3)-board. The board was presented in its two-dimensional representation (Fig. 1). The objective is to place 4 marks in a row horizontally, diagonally or vertically while trying to block the opponent from doing so.

The given task (Fig. 1) consists in solving the game and finding a relationship between the number of winning lines and the board dimensions. Some mathematical notions acquired in university degree are necessary to solve it.

The methods for obtaining the data are direct observations during the working session, the recordings from the cameras, and the documents where students describe their approaches to the problem solution on protocols. The students worked in pairs or alone; we gave each pair of students paper and pencil and some "empty board", using which they could elaborate a game strategy. Students were also asked to describe their approaches to solving the problem specifically describing: their thought processes in the resolution, the difficulties they encountered, and the strategies they would use in order to solve with paper and pencil. Students had two hours to do that.

3D Tic-Tac-Toe is the three dimensional version of the classic Three in a Skate game. The game board is a 4x4x4 cube.

The game is for two players. One player uses "crosses" and the other uses "zeros".

The objective is to place 4 marks in a row horizontally, diagonally or vertically while trying to block the opponent from doing so.

1. By helping yourself with the two-dimensional version of the game board, solve the game by developing your thinking process with a detailed solution protocol. A qualitative analysis was chosen to examine the resolution protocols of the students through the combination of the Backward Reasoning Epistemic Model and the AiC Model. We will illustrate it through a significant example in next section.

Mathematically express (formula, pattern, routine, ...) the relationships that can happen between the dimensions of the game board and the winning lines

RESULTS: CASE STUDY

In this section we analyse a single student's resolution protocol of the 3D Tic-Tac-Toe. This allows us to get a deep understanding of the tendencies of the behaviour related to the sequences of actions during the discovery phase of resolution. The chosen student, whom we name A, is key informant of the PhD students group. A is an expert student, who solved the problem by investigating the mathematical relationships that are at the basis of this game using backward reasoning.

The student begins the game resolution by solving the 2D version of the game (3x3 board). First, he plays trying to remember the winning strategy, then he starts calculating mathematically the number of winning lines. Then he moves on to the 3D version of the game where he continues to reason about the number of winning lines until he obtains a general formula. Then it shows that the formula that he has found is valid for any cube of dimension (n, d) and finally he reasons again about the winning strategy, this time for the 3D case. The extract refers to the discovery process that the student makes to formulate the general recursive formula that allows to identify the number of winning lines knowing the size of the game board. Backward reasoning is predominant in this excerpt (Fig. 2).

12. I decide to move on to the 3D case. The previous strategy suggests me to count lines. I make a few drawings to test. There are 10 lines in each plan parallel to the axes and there are 12 planes parallel to the axes. I lack the "diagonal lines" as in the example. They seem more complicated. 13. I'm starting to do numerology: 10 = 4 * 2 + 2 which is broken down as the number of pawns per dimension of the plane plus two diagonals. Will it be general? 14. I realize that 12 = 4 * 3 that seems to follow the previous pattern. Hope. It looks like a nice combinatorial problem. 15. It reminds me of geometry calculations on finite fields. I think about shooting over there, but I realize that there are cyclic lines that come out on one side and appear on the opposite side. These movements are not allowed. I could rule them out but it seems too complicated. I abandon this strategy. 16. I think of a recursive pattern. I guess n pieces in d dimensions (the usual case is (𝑛, 𝑑) = (3,2) and this is (𝑛, 𝑑) = (4,3)). Maybe the number of straight lines follows a pattern. 𝐿(𝑛, 𝑑) = 𝑐𝑛𝑡(𝑛, 𝑑) * 𝐿(𝑛, 𝑑 -1) + 𝐷𝑖𝑎𝑔𝑜𝑛𝑎𝑙𝑠 17. The constant must be the number of planes parallel to the axes. As in the previous case, these have to be 𝑛𝑑, then I refine my formula to 𝐿(𝑛, 𝑑) = 𝑛𝑑 * 𝐿(𝑛, 𝑑 -1) + 𝐷𝑖𝑎𝑔𝑜𝑛𝑎𝑙𝑠 18. Diagonals don't seem that simple. I start to play with the example of the cube and the plane.

They seem to join opposite vertices of opposite faces. Will it be general? 19. I calculate that a hypercube has 2 𝑑 vertices, which gives me two faces with 2 𝑑-1 vertices.

Thus, if my previous observation is correct, the formula is 𝐿(𝑛, 𝑑) = 𝑛𝑑 * 𝐿(𝑛, 𝑑 -1) + 2 𝑑-1

Fig. 2: Extract of student protocol

The student begins the resolution of the case in 3 dimensions thinking in analogy with the resolution of the case in 2 dimensions that he has previously carried out. The first objective is to count the winning lines on the board. To do so, he divides the game board into planes and counts the winning lines present on each plan. He then begins to think about the number of lines in each floor and breaks it down trying to identify the parts of the number with elements of the game (number of checkers for each winning line, size, number of diagonals). He then analyse and decompose each floor in the same way. At this point he introduces a recursive "auxiliary pattern" and conjectures the existence of a general recursive formula that relates the number of winning lines with the size of the table. He then analyses the formula and looks for a mathematical expression for each part of it. He then obtains the general recursive formula.

Analysing the extract, it is possible to identify different epistemic actions performed by the student. Using as definition of epistemic action: "that action in which knowledge is used or constructed". Each epistemic action can be characterized as an expression of the different characteristics of backward reasoning: in this extract we can see elements of decomposition (D) and insertion of auxiliary elements (E) and solution formulation (FS). In the same way, the same action can be classified according to the AiC model.

In the table below the second column identify the actions, the third identify the characteristics of backward reasoning and the last identify the AiC classification. Analysing the epistemic actions from the point of view of backward reasoning, one can observe how the student breaks down the problem and inserts auxiliary elements in an alternating way in order: first to conjecture the existence of a general formula and then to represent it mathematically. From the point of view of the analysis with AiC-model one can notice a certain regularity in the alternation of the AE (Table 2): Two sequences B-R-C-B-R-C characterize the formulation of the conjecture, while two sequences C-B-C-B characterize the formulation of the general formula. The actions that characterize the "decomposition" are actions that do not develop instantaneously in the resolution process but that suppose a longer time of realization. If you look at the introduction of auxiliary elements, these actions are instead instantaneous. Some actions, such as the introduction of a recursive pattern, can be a recognition of concepts belonging to the student's background, it happens after a structural analogy. During this analogy (line 15) the student remembers geometrical concepts that help him to identify patterns. In other actions, such as the identification of each element of the decomposition of the number 10 with an element of the game, the student creates a new construct from the processing of knowledge already encountered in the resolution.

CONCLUSION

In this investigation, we chose to use the AiC -model to understand how the process of abstraction develops in the construction of new mathematical knowledge using backward reasoning. The development of the different epistemic actions was analysed, with the help of the subcategories built in this research and the relationships they established among themselves. If we look at the whole process of the protocol (Fig. 3), we can see how the student passes through different contexts in order to achieve the general mathematical formulation. He begins working within the game context, then he moves to a mathematical context to interpret the example through this new lens, then he goes forward and explains the game in a more general mathematical context.

The transition between the three contexts happens with a complex back and forth process, where the different contexts are repeatedly activated, as illustrated in Fig. 3. Following the introduction of subcategories of analysis, built in a narrow link with the nature of backward reasoning it is possible to analyse, in detail, characteristics associated with the development of students' thinking processes. This helps in better understanding the connections between the different epistemic actions that can influence Building with and Construction.

We notice that the incorporation of Backward Reasoning-based categories allows to identify breaking elements and which they trigger the construction process of the formula. These actions occur and they cannot be determined only with specific actions defined according to the AiC-model. In this case it has been necessary to identify elements of the constructive epistemic action processes produced in the long term. The back and forth movement above is identified as a cognitive travel between the concrete and the abstract: in it the analogy processesboth contextual and structural analogyhave been crucial. In the process of conjecturing and justifying, complex chains of plausible reasoning are often elaborated, which may contain new nuances that enrich already known patterns. An exhaustive analysis of these processes requires an exploration not only of the punctual but in the long term.

Figure 1 :

 1 Figure 1: Strategy game statement

Fig. 3

 3 Fig. 3 Pattern in epistemic actions and context

Table 1 .

 1 ). They have different mathematical notions with regard to solving problems, but they had not received any special training about backtracking heuristics. These data are summarised in Table1. Participants

	Mathematics	Mathematics	Future High School	Mathematics	Total
	Bachelor Italy	Bachelor Spain	teachers	(Master-	PhD
			students)
	99	50	28		8	185

Table 2 : Analysis of Epistemic action

 2

	Protocols	Epistemic action	BR	AiC
	12	Splitting the game board into planes	D	B
		Counting the winning lines in each plan	D	B
		Grouping winning Lines into a Scheme	E	R
	13	Mathematically break down a number	D	C
		Identify each element of the decomposition	E	C
	14	Mathematically break down a number	D	B
	15	Analogy/ break motion
	16	Introduce a recursive pattern	E	R
		Conjecture: general recursive formula	FS	C
	17	Break down the formula into its elements	D	C
		Analyse the constant element
	18	Analyse the diagonal element	D	B
	19	Representation of the diagonal in relation to the vertices of the	D	C
		hypercube
		Formulation of the general formula	FS	B

Acknowledgment:

This study was funded by Interdisciplinary Mathematics Institute (IMI) special action grant, Programme INVEDUMAT_uni (Research in Mathematical Education at University Level), Spain and Science Doctoral School of Università and Politecnico of Torino.