Coding-Logic Correspondence: Turning Information and Communication Networks into Logical Formulae via Hypergraph Heyting Algebra
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914218866900992 |
|---|---|
| author | Li, Cheuk Ting |
| author_facet | Li, Cheuk Ting |
| contents | We propose using confusion hypergraphs (hyperconfusions) as a model of information. In contrast to the conventional approach using random variables, we can now perform conjunction, disjunction and implication of information, forming a Heyting algebra. Using the connection between Heyting algebra and intuitionistic logic, we can express the requirements of a communication network (e.g., network coding, index coding, Slepian-Wolf coding) as a logical formula, allowing us to use the hypergraph Heyting algebra to directly compute the optimal coding scheme. The optimal communication cost is simply given by the entropy of the hypergraph (within a logarithmic gap). This gives a surprising correspondence between coding settings and logical formulae, similar to the Curry-Howard correspondence between proofs and computer programs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_21112 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Coding-Logic Correspondence: Turning Information and Communication Networks into Logical Formulae via Hypergraph Heyting Algebra Li, Cheuk Ting Information Theory Logic We propose using confusion hypergraphs (hyperconfusions) as a model of information. In contrast to the conventional approach using random variables, we can now perform conjunction, disjunction and implication of information, forming a Heyting algebra. Using the connection between Heyting algebra and intuitionistic logic, we can express the requirements of a communication network (e.g., network coding, index coding, Slepian-Wolf coding) as a logical formula, allowing us to use the hypergraph Heyting algebra to directly compute the optimal coding scheme. The optimal communication cost is simply given by the entropy of the hypergraph (within a logarithmic gap). This gives a surprising correspondence between coding settings and logical formulae, similar to the Curry-Howard correspondence between proofs and computer programs. |
| title | Coding-Logic Correspondence: Turning Information and Communication Networks into Logical Formulae via Hypergraph Heyting Algebra |
| topic | Information Theory Logic |
| url | https://arxiv.org/abs/2512.21112 |