Definable subsets of polynomial-time algebraic structures

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование


A structure S in a finite signature σ is polynomial-time if the domain of S, and the basic operations and relations of S are polynomial-time computable. Following the approach of semantic programming, for a given polynomial-time structure S, we consider the family B(S) containing all subsets of dom(S), which are definable by a ∆0 formula with parameters. It is known that each of these sets is polynomial-time computable; hence, B(S), endowed with the standard set-theoretic operations, forms a natural Boolean algebra of polynomial-time languages, associated with S. We prove that up to isomorphism, the algebras B(S), where S is a polynomial-time structure, are precisely computable atomic Boolean algebras.

Язык оригиналаанглийский
Название основной публикацииComputer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings
РедакторыHenning Fernau
ИздательSpringer Gabler
Число страниц13
ISBN (печатное издание)9783030500252
СостояниеОпубликовано - 1 янв. 2020
Событие15th International Computer Science Symposium in Russia, CSR 2020 - Yekaterinburg, Российская Федерация
Продолжительность: 29 июн. 20203 июл. 2020

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том12159 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349


Конференция15th International Computer Science Symposium in Russia, CSR 2020
Страна/TерриторияРоссийская Федерация


Подробные сведения о темах исследования «Definable subsets of polynomial-time algebraic structures». Вместе они формируют уникальный семантический отпечаток (fingerprint).