Online and feasible presentability: from trees to modal algebras
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912343282155520 |
|---|---|
| author | Bazhenov, Nikolay Kalociński, Dariusz Wrocławski, Michał |
| author_facet | Bazhenov, Nikolay Kalociński, Dariusz Wrocławski, Michał |
| contents | We investigate whether every computable member of a given class of structures admits a fully primitive recursive (also known as punctual) or fully P-TIME copy. A class with this property is referred to as punctually robust or P-TIME robust, respectively. We present both positive and negative results for structures corresponding to well-known representations of trees, such as binary trees, ordered trees, sequential (or prefix) trees, and partially ordered (poset) trees. A corollary of one of our results on trees is that semilattices and lattices are not punctually robust. In the main result of the paper, we demonstrate that, unlike Boolean algebras, modal algebras - that is, Boolean algebras with modality - are not punctually robust. The question of whether distributive lattices are punctually robust remains open. The paper contributes to a decades-old program on effective and feasible algebra, which has recently gained momentum due to rapid developments in punctual structure theory and its connections to online presentations of structures. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_16663 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Online and feasible presentability: from trees to modal algebras Bazhenov, Nikolay Kalociński, Dariusz Wrocławski, Michał Logic Computational Complexity 03D45, 03C57, 03D15 We investigate whether every computable member of a given class of structures admits a fully primitive recursive (also known as punctual) or fully P-TIME copy. A class with this property is referred to as punctually robust or P-TIME robust, respectively. We present both positive and negative results for structures corresponding to well-known representations of trees, such as binary trees, ordered trees, sequential (or prefix) trees, and partially ordered (poset) trees. A corollary of one of our results on trees is that semilattices and lattices are not punctually robust. In the main result of the paper, we demonstrate that, unlike Boolean algebras, modal algebras - that is, Boolean algebras with modality - are not punctually robust. The question of whether distributive lattices are punctually robust remains open. The paper contributes to a decades-old program on effective and feasible algebra, which has recently gained momentum due to rapid developments in punctual structure theory and its connections to online presentations of structures. |
| title | Online and feasible presentability: from trees to modal algebras |
| topic | Logic Computational Complexity 03D45, 03C57, 03D15 |
| url | https://arxiv.org/abs/2504.16663 |