Traversal times
Lax330177.Durations · concepts/Lax330177/Durations.lean · lax-330177
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
Each occurrence has a natural traversal time. The next departure may occur at arrival. The lifetime bounds departure times and the final arrival may fall outside it.
- Feasible departure times. For integer timestamps, a departure sequence is feasible with traversal time zero exactly when it is weakly increasing. With traversal time one, it is feasible exactly when it is strictly increasing.
- The same timed paths. Fix the vertex sequence and every departure time. They form a path with uniform traversal time zero exactly when they form a nonstrict temporal path, and with uniform time one exactly when they form a strict temporal path.
- The same reachable pairs. For every pair of vertices, reachability with uniform traversal time zero is equivalent to nonstrict reachability, and reachability with uniform time one is equivalent to strict reachability.
Concept map
In the paper
- page 2 of this submission's paper
Lean source view on GitHub
| 1 | import Mathlib |
| 2 | import Lax330177.Representations |
| 3 | import Lax330177.Paths |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Traversal times |
| 8 | type: definition |
| 9 | --- |
| 10 | Each occurrence has a natural traversal time. The next departure may occur at arrival. The lifetime bounds departure times and the final arrival may fall outside it. |
| 11 | |
| 12 | - [Feasible departure times.](Lax330177Proofs.Basic.uniform_modes.html) For integer timestamps, a departure sequence is feasible with traversal time zero exactly when it is weakly increasing. With traversal time one, it is feasible exactly when it is strictly increasing. |
| 13 | - [The same timed paths.](Lax330177Proofs.Basic.uniform_paths.html) Fix the vertex sequence and every departure time. They form a path with uniform traversal time zero exactly when they form a nonstrict temporal path, and with uniform time one exactly when they form a strict temporal path. |
| 14 | - [The same reachable pairs.](Lax330177Proofs.Basic.uniform_reaches.html) For every pair of vertices, reachability with uniform traversal time zero is equivalent to nonstrict reachability, and reachability with uniform time one is equivalent to strict reachability. |
| 15 | -/ |
| 16 | namespace Lax330177.Durations |
| 17 | open Lax330177.Representations |
| 18 | open Lax330177.Paths |
| 19 | noncomputable section |
| 20 | attribute [local instance] Classical.propDecidable |
| 21 | |
| 22 | def Feasible {k : ℕ} (time duration : Fin k → ℕ) : Prop := |
| 23 | ∀ i j, i < j → time i + duration i ≤ time j |
| 24 | |
| 25 | def DurationPath {n k} (G : Graph n) (δ : Fin G.lifetime → Fin n → Fin n → ℕ) |
| 26 | (x : Fin (k+1) → Fin n) (t : Fin k → Fin G.lifetime) : Prop := |
| 27 | Function.Injective x ∧ (∀ i, G.edge (t i) (x i.castSucc) (x i.succ)) ∧ |
| 28 | Feasible (fun i => (t i).val) (fun i => δ (t i) (x i.castSucc) (x i.succ)) |
| 29 | |
| 30 | |
| 31 | def DurationReaches {n} (G : Graph n) (δ : Fin G.lifetime → Fin n → Fin n → ℕ) |
| 32 | (u v : Fin n) : Prop := |
| 33 | ∃ k, ∃ x : Fin (k+1) → Fin n, ∃ t : Fin k → Fin G.lifetime, |
| 34 | DurationPath G δ x t ∧ x 0 = u ∧ x (Fin.last k) = v |
| 35 | |
| 36 | |
| 37 | |
| 38 | end |
| 39 | end Lax330177.Durations |
| 40 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments