While this submission is a draft, it cannot be used by other submissions.

Traversal times

Lax330177.Durations · concepts/Lax330177/Durations.lean · lax-330177

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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
    4 concepts
    100%
    DefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.

    In the paper

    • page 2 of this submission's paper

    Lean source view on GitHub

    1import Mathlib
    2import Lax330177.Representations
    3import Lax330177.Paths
    4
    5/-!
    6---
    7title: Traversal times
    8type: definition
    9---
    10Each 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-/
    16namespace Lax330177.Durations
    17open Lax330177.Representations
    18open Lax330177.Paths
    19noncomputable section
    20attribute [local instance] Classical.propDecidable
    21
    22def Feasible {k : ℕ} (time duration : Fin k → ℕ) : Prop :=
    23 ∀ i j, i < j → time i + duration i ≤ time j
    24
    25def 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
    31def 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
    38end
    39end Lax330177.Durations
    40

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…