Minimal Lifting in Regular Triadic Coalgebras
Fuente:
Zenodo
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Recurso digital |
| Publié: |
Zenodo
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866901993465839616 |
|---|---|
| author | PAQUET, Maxime |
| author_facet | PAQUET, Maxime |
| contents | <div> <div>Representing dynamical systems in structured formats often incurs overhead. We characterize exactly when this overhead vanishes for <em>regular triadic coalgebras</em> (RTCs)---ternary coalgebras equipped with a cyclic symmetry of order three and a regularity constraint ensuring that each state unfolds into three pairwise distinct successors.</div> <br> <div>Every finite dynamical system $(C,f)$ admits a <em>canonical lifting</em> to an RTC of size $3|C|$. Our main result characterizes when a lifting of minimal size exists: a system with $n$ configurations admits a lifting of size $n$ if and only if $n \equiv 0 \pmod{3}$ and the maximal in-degree of $f$ is at most $n/3$. This criterion is decidable in linear time.</div> <br> <div>The key tool is a <em>dispersion lemma</em>: cyclic equivariance forces elements within any orbit to have pairwise distinct successors, yielding a global capacity bound. Sufficiency reduces to equitable coloring of a union of cliques.</div> <br> <div>The canonical lifting preserves computational complexity with constant overhead. Turing-complete RTCs exist via lifting of universal counter machines, demonstrating encodability rather than intrinsic triadic expressivity.</div> </div> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_18133173 |
| institution | Zenodo |
| language | |
| publishDate | 2026 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | Minimal Lifting in Regular Triadic Coalgebras PAQUET, Maxime Coalgebra Discrete dynamical systems Cyclic symmetry Lifting Cyclic equivariance Ternary structures Minimal encoding Collision graph Computational complexity Turing-completeness Minsky machines <div> <div>Representing dynamical systems in structured formats often incurs overhead. We characterize exactly when this overhead vanishes for <em>regular triadic coalgebras</em> (RTCs)---ternary coalgebras equipped with a cyclic symmetry of order three and a regularity constraint ensuring that each state unfolds into three pairwise distinct successors.</div> <br> <div>Every finite dynamical system $(C,f)$ admits a <em>canonical lifting</em> to an RTC of size $3|C|$. Our main result characterizes when a lifting of minimal size exists: a system with $n$ configurations admits a lifting of size $n$ if and only if $n \equiv 0 \pmod{3}$ and the maximal in-degree of $f$ is at most $n/3$. This criterion is decidable in linear time.</div> <br> <div>The key tool is a <em>dispersion lemma</em>: cyclic equivariance forces elements within any orbit to have pairwise distinct successors, yielding a global capacity bound. Sufficiency reduces to equitable coloring of a union of cliques.</div> <br> <div>The canonical lifting preserves computational complexity with constant overhead. Turing-complete RTCs exist via lifting of universal counter machines, demonstrating encodability rather than intrinsic triadic expressivity.</div> </div> |
| title | Minimal Lifting in Regular Triadic Coalgebras |
| topic | Coalgebra Discrete dynamical systems Cyclic symmetry Lifting Cyclic equivariance Ternary structures Minimal encoding Collision graph Computational complexity Turing-completeness Minsky machines |
| url | https://doi.org/10.5281/zenodo.18133173 |