AFTD Auto-Formalizing Theoretical Domains

Online.OnlineAlgorithm

structureimported Lean

A deterministic online algorithm as a state machine. The state State summarises the relevant past; step consumes the current state and the current input to produce the next state together with an *optional* output — without ever seeing any future input. The input is Option Input: some r is a genuine request, none signals *end of input*, the algorithm's chance to act when the stream is exhausted. A step that emits some o halts the run with result o; a step that emits none defers, recording what it learned into the next state.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
structure Online.OnlineAlgorithm (Input State Output : Type*)
Defined in
EconCSLib, `Online.OnlineAlgorithm`
Lean proof
By Claude (from the file's git history), from github.com/gametheoryinlean/EconCSLib at 1a88f809b538 (Copyright (c) 2026 EconCSLib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.30.0.
Verified
08 Oct 2026
Axioms
none listed
Used by 7

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
/-- A deterministic online algorithm as a state machine. The state `State` summarises the relevant past; `step` consumes the current state and the current input to produce the next state together with an *optional* output — without ever seeing any future input. The input is `Option Input`: `some r` is a genuine request, `none` signals *end of input*, the algorithm's chance to act when the stream is exhausted. A step that emits `some o` halts the run with result `o`; a step that emits `none` defers, recording what it learned into the next state. -/
structure Online.OnlineAlgorithm (Input State Output : Type*) where
  /-- Initial state, before any input is processed. -/
  init : State
  /-- One-step transition. Depends only on the current state and the
  current input — by construction, the future is invisible. The input is
  `some r` for a request and `none` for end of input. Emitting `some o`
  halts the run; `none` defers. -/
  step : State → Option Input → State × Option Output
See it in the graphDiscuss this resultChallenge it