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
Страницы142-154
Число страниц13
ISBN (печатное издание)9783030500252
DOI
СостояниеОпубликовано - 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
СтранаРоссийская Федерация
ГородYekaterinburg
Период29.06.202003.07.2020

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

  • Цитировать

    Bazhenov, N. (2020). Definable subsets of polynomial-time algebraic structures. В H. Fernau (Ред.), Computer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings (стр. 142-154). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 12159 LNCS). Springer Gabler. https://doi.org/10.1007/978-3-030-50026-9_10