AFTD Auto-Formalizing Theoretical Domains

is_temporal_walk

def

A temporal walk in a temporal graph (G_t)_t: at every time step t the agent either waits or traverses one edge of the snapshot G_t.

Statement

def is_temporal_walk {n : ℕ} (G : ℕ → SimpleGraph (Fin n)) (w : ℕ → Fin n) : Prop
Defined in
arXiv:2610.06228 (Hiding a Vertex from the Temporal Explorer), Sec. 2 (temporal walks)
Verified
06 Oct 2026
Axioms
none listed
Used by 6
  • temporal_path_many_targets_one_frame_trapFor every k ≥ 2 there is a temporal graph on N = k² + k vertices, all of whose snapshots are spanning paths, together with k designated…
  • temporal_path_twelve_one_frame_target_trapThere is a temporal graph on twelve vertices, every snapshot a spanning path, such that every walk from vertex 0 visits at most one of the…
  • temporal_connected_explore_sqEvery temporal graph on n vertices all of whose snapshots are connected can be explored from any start vertex within (n − 1)² time steps.
  • temporal_target_state_table_soundIf a finite table of endpoint/target-set pairs contains the initial state and is closed under every legal temporal step, then every…
  • temporal_path_four_requires_sixThere is a temporal graph on four vertices with spanning-path snapshots such that every temporal walk starting at vertex 0 needs at least…
  • temporal_path_five_requires_nineThere is a temporal graph on five vertices with spanning-path snapshots such that every walk from vertex 0 needs at least nine steps to…

Lean source view module on GitHub

/-- A walk of an agent in the temporal graph `G` (snapshot `G t` at time step `t`): at each step it waits or moves along one edge of the current snapshot. -/
def is_temporal_walk {n : ℕ} (G : ℕ → SimpleGraph (Fin n)) (w : ℕ → Fin n) : Prop :=
  ∀ t, w (t + 1) = w t ∨ (G t).Adj (w t) (w (t + 1))
See it in the graphDiscuss this resultChallenge it