Research output: Chapter in Book/Report/Conference proceeding › Chapter › Research › peer-review
Online and Feasible Presentability: From Trees to Modal Algebras. / Bazhenov, Nikolay; Kalociński, Dariusz; Wrocławski, Michał.
Leibniz International Proceedings in Informatics, LIPIcs. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2025. 142 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 334).Research output: Chapter in Book/Report/Conference proceeding › Chapter › Research › peer-review
}
TY - CHAP
T1 - Online and Feasible Presentability: From Trees to Modal Algebras
AU - Bazhenov, Nikolay
AU - Kalociński, Dariusz
AU - Wrocławski, Michał
N1 - Conference code: 52
PY - 2025/6/30
Y1 - 2025/6/30
N2 - 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.
AB - 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.
KW - Algebraic structure
KW - Boolean algebra
KW - computable structure
KW - fully primitive recursive structure
KW - lattice
KW - modal algebra
KW - polynomial-time computable structure
KW - punctual robustness
KW - punctual structure
KW - semilattice
KW - tree
UR - https://www.mendeley.com/catalogue/a2b381fb-e5e8-32bb-be52-55df4377f2ec/
UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=105009881187&origin=inward
U2 - 10.4230/LIPIcs.ICALP.2025.142
DO - 10.4230/LIPIcs.ICALP.2025.142
M3 - Chapter
SN - 9783959773720
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Leibniz International Proceedings in Informatics, LIPIcs
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 52nd International Colloquium on Automata, Languages, and Programming
Y2 - 1 January 2025
ER -
ID: 68403867