Search Results

Documents authored by Bazhenov, Nikolay

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.142
Online and Feasible Presentability: From Trees to Modal Algebras

Authors: Nikolay Bazhenov, Dariusz Kalociński, and Michał Wrocławski

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

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.
Cite as

Nikolay Bazhenov, Dariusz Kalociński, and Michał Wrocławski. Online and Feasible Presentability: From Trees to Modal Algebras. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 142:1-142:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bazhenov_et_al:LIPIcs.ICALP.2025.142,
  author =	{Bazhenov, Nikolay and Kaloci\'{n}ski, Dariusz and Wroc{\l}awski, Micha{\l}},
  title =	{{Online and Feasible Presentability: From Trees to Modal Algebras}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{142:1--142:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.142},
  URN =		{urn:nbn:de:0030-drops-235190},
  doi =		{10.4230/LIPIcs.ICALP.2025.142},
  annote =	{Keywords: Algebraic structure, computable structure, fully primitive recursive structure, punctual structure, polynomial-time computable structure, punctual robustness, tree, semilattice, lattice, Boolean algebra, modal algebra}
}
Document
DOI: 10.4230/LIPIcs.CSL.2023.11
Degree Spectra, and Relative Acceptability of Notations

Authors: Nikolay Bazhenov and Dariusz Kalociński

Published in: LIPIcs, Volume 252, 31st EACSL Annual Conference on Computer Science Logic (CSL 2023)

Abstract
We investigate the interplay between the degree spectrum of a computable relation R on the computable structure (ω, <), i.e., natural numbers with the standard order, and the computability of the successor, relativized to that relation, in all computable copies of the structure - the property we dub successor’s recoverability. In computable structure theory, this property is used to show that of all possible Turing degrees that could belong to the spectrum of R (namely, of all Δ₂ degrees), in fact only the computably enumerable degrees are contained in the spectrum. Interestingly, successor’s recoverability (in the unrelativized form) appears also in philosophy of computing where it is used to distinguish between acceptable and deviant encodings (notations) of natural numbers. Since Shapiro’s notations are rarely seen through the lens of computable structure theory, we first lay the elementary conceptual groundwork to understand notations in terms of computable structures and show how results pertinent to the former can fundamentally inform our understanding of the latter. Secondly, we prove a new result which shows that for a large class of computable relations (satisfying a certain effectiveness condition), having all c.e. degrees as a spectrum implies that the successor is recoverable from the relation. The recoverability of successor may be otherwise seen as relativized acceptability of every notation for the structure. We end with remarks about connections of our result to relative computable categoricity and to a similar direction pursued by Matthew Harrison-Trainor in [Harrison-Trainor, 2018], and with an open question.
Cite as

Nikolay Bazhenov and Dariusz Kalociński. Degree Spectra, and Relative Acceptability of Notations. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 252, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bazhenov_et_al:LIPIcs.CSL.2023.11,
  author =	{Bazhenov, Nikolay and Kaloci\'{n}ski, Dariusz},
  title =	{{Degree Spectra, and Relative Acceptability of Notations}},
  booktitle =	{31st EACSL Annual Conference on Computer Science Logic (CSL 2023)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-264-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{252},
  editor =	{Klin, Bartek and Pimentel, Elaine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2023.11},
  URN =		{urn:nbn:de:0030-drops-174725},
  doi =		{10.4230/LIPIcs.CSL.2023.11},
  annote =	{Keywords: Computable structure theory, Degree spectra, \omega-type order, C.e. degrees, \Delta₂ degrees, Acceptable notation, Successor, Learnability}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.8
Intrinsic Complexity of Recursive Functions on Natural Numbers with Standard Order

Authors: Nikolay Bazhenov, Dariusz Kalociński, and Michał Wrocławski

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
The intrinsic complexity of a relation on a given computable structure is captured by the notion of its degree spectrum - the set of Turing degrees of images of the relation in all computable isomorphic copies of that structure. We investigate the intrinsic complexity of unary total recursive functions on nonnegative integers with standard order. According to existing results, the possible spectra of such functions include three sets consisting of precisely: the computable degree, all c.e. degrees and all Δ₂ degrees. These results, however, fall far short of the full classification. In this paper, we obtain a more complete picture by giving a few criteria for a function to have intrinsic complexity equal to one of the three candidate sets of degrees. Our investigations are based on the notion of block functions and a broader class of quasi-block functions beyond which all functions of interest have intrinsic complexity equal to the c.e. degrees. We also answer the questions raised by Wright [Wright, 2018] and Harrison-Trainor [Harrison-Trainor, 2018] by showing that the division between computable, c.e. and Δ₂ degrees is insufficient in this context as there is a unary total recursive function whose spectrum contains all c.e. degrees but is strictly contained in the Δ₂ degrees.
Cite as

Nikolay Bazhenov, Dariusz Kalociński, and Michał Wrocławski. Intrinsic Complexity of Recursive Functions on Natural Numbers with Standard Order. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bazhenov_et_al:LIPIcs.STACS.2022.8,
  author =	{Bazhenov, Nikolay and Kaloci\'{n}ski, Dariusz and Wroc{\l}awski, Micha{\l}},
  title =	{{Intrinsic Complexity of Recursive Functions on Natural Numbers with Standard Order}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.8},
  URN =		{urn:nbn:de:0030-drops-158185},
  doi =		{10.4230/LIPIcs.STACS.2022.8},
  annote =	{Keywords: Computable Structure Theory, Degree Spectra, \omega-Type Order, c.e. Degrees, d.c.e. Degrees, \Delta₂ Degrees, Learnability}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact