Standard

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 proceedingChapterResearchpeer-review

Harvard

Bazhenov, N, Kalociński, D & Wrocławski, M 2025, Online and Feasible Presentability: From Trees to Modal Algebras. in Leibniz International Proceedings in Informatics, LIPIcs., 142, Leibniz International Proceedings in Informatics, LIPIcs, vol. 334, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 52nd International Colloquium on Automata, Languages, and Programming , 01.01.2025. https://doi.org/10.4230/LIPIcs.ICALP.2025.142

APA

Bazhenov, N., Kalociński, D., & Wrocławski, M. (2025). Online and Feasible Presentability: From Trees to Modal Algebras. In Leibniz International Proceedings in Informatics, LIPIcs [142] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 334). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2025.142

Vancouver

Bazhenov N, Kalociński D, Wrocławski M. Online and Feasible Presentability: From Trees to Modal Algebras. In Leibniz International Proceedings in Informatics, LIPIcs. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2025. 142. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.ICALP.2025.142

Author

Bazhenov, Nikolay ; Kalociński, Dariusz ; Wrocławski, Michał. / Online and Feasible Presentability: From Trees to Modal Algebras. Leibniz International Proceedings in Informatics, LIPIcs. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2025. (Leibniz International Proceedings in Informatics, LIPIcs).

BibTeX

@inbook{d84e3103b80041c2a154cf4077d3f758,
title = "Online and Feasible Presentability: From Trees to Modal Algebras",
abstract = "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.",
keywords = "Algebraic structure, Boolean algebra, computable structure, fully primitive recursive structure, lattice, modal algebra, polynomial-time computable structure, punctual robustness, punctual structure, semilattice, tree",
author = "Nikolay Bazhenov and Dariusz Kaloci{\'n}ski and Micha{\l} Wroc{\l}awski",
year = "2025",
month = jun,
day = "30",
doi = "10.4230/LIPIcs.ICALP.2025.142",
language = "English",
isbn = "9783959773720",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
booktitle = "Leibniz International Proceedings in Informatics, LIPIcs",
address = "Germany",
note = "52nd International Colloquium on Automata, Languages, and Programming , ICALP 2025 ; Conference date: 01-01-2025",

}

RIS

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