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

Binary encodings of numbers and graph pairs

Lax119563.BinaryEncodings · concepts/Lax119563/BinaryEncodings.lean · lax-119563

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

    Inputs of Turing machines are bit strings. We encode a natural number mm by its binary digits d0,d1,…d_0, d_1, \dots, least significant first, writing each digit dd as the two bits 1d1 d and terminating with a single 00; this code is self-delimiting and has length 2⌈log⁡2(m+1)⌉+12 \lceil \log_2 (m + 1) \rceil + 1. A list of natural numbers is encoded by concatenating the codes of its entries.

    A colored graph GG with nn vertices and mm edges is described by the list

    n, χG(0),…,χG(n−1), m, u1,v1,…,um,vm,n,\ \chi_G(0), \dots, \chi_G(n - 1),\ m,\ u_1, v_1, \dots, u_m, v_m,

    where u1v1,…,umvmu_1 v_1, \dots, u_m v_m are its edges with uj<vju_j < v_j, in lexicographic order. A pair (G,H)(G, H) is encoded by the code of the description of GG followed by that of HH. For graphs with NN vertices, EE edges, and colors below NN, the encoding has length O((N+E)log⁡(N+2))O((N + E) \log (N + 2)).

    Concept map
    2 concepts
    100%
    DefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.

    Lean source view on GitHub

    1import Mathlib.Data.Nat.Bits
    2import Mathlib.Data.List.FinRange
    3import Lax119563.ColoredGraphs
    4
    5/-!
    6---
    7title: Binary encodings of numbers and graph pairs
    8type: definition
    9---
    10Inputs of Turing machines are bit strings. We encode a natural number mm by its binary
    11digits d0,d1,…d_0, d_1, \dots, least significant first, writing each digit dd as the two bits
    121d1 d and terminating with a single 00; this code is self-delimiting and has length
    132⌈log⁡2(m+1)⌉+12 \lceil \log_2 (m + 1) \rceil + 1. A list of natural numbers is encoded by concatenating
    14the codes of its entries.
    15
    16A colored graph GG with nn vertices and mm edges is described by the list
    17n, χG(0),…,χG(n−1), m, u1,v1,…,um,vm,n,\ \chi_G(0), \dots, \chi_G(n - 1),\ m,\ u_1, v_1, \dots, u_m, v_m,
    18where u1v1,…,umvmu_1 v_1, \dots, u_m v_m are its edges with uj<vju_j < v_j, in lexicographic order. A pair
    19(G,H)(G, H) is encoded by the code of the description of GG followed by that of HH. For graphs
    20with NN vertices, EE edges, and colors below NN, the encoding has length
    21O((N+E)log⁡(N+2))O((N + E) \log (N + 2)).
    22-/
    23
    24open Lax119563.ColoredGraphs
    25
    26namespace Lax119563.BinaryEncodings
    27
    28/-- The self-delimiting binary code of a natural number: its binary digits `d`, least
    29significant first, each written as `true, d`, followed by `false`. -/
    30def encodeNat (m : ℕ) : List Bool :=
    31 (Nat.bits m).flatMap (fun d => [true, d]) ++ [false]
    32
    33/-- The code of a list of natural numbers: the concatenation of the codes of its entries. -/
    34def encodeNats (l : List ℕ) : List Bool :=
    35 l.flatMap encodeNat
    36
    37open Classical in
    38/-- The edges `(u, v)` with `u < v` of a colored graph, in lexicographic order. -/
    39noncomputable def edgeList (G : ColoredGraph) : List (ℕ × ℕ) :=
    40 (List.finRange G.n).flatMap fun u =>
    41 ((List.finRange G.n).filter fun v => u < v ∧ G.graph.Adj u v).map fun v => ((u : ℕ), (v : ℕ))
    42
    43/-- The description `n, χ(0), …, χ(n-1), m, u₁, v₁, …, u_m, v_m` of a colored graph. -/
    44noncomputable def graphDescription (G : ColoredGraph) : List ℕ :=
    45 G.n :: (List.finRange G.n).map G.color ++
    46 (edgeList G).length :: (edgeList G).flatMap fun e => [e.1, e.2]
    47
    48/-- The binary encoding of a pair of colored graphs. -/
    49noncomputable def encodeGraphPair (G H : ColoredGraph) : List Bool :=
    50 encodeNats (graphDescription G ++ graphDescription H)
    51
    52end Lax119563.BinaryEncodings
    53

    Discussion

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

    Loading discussion…