Standard

Definable subsets of polynomial-time algebraic structures. / Bazhenov, Nikolay.

Computer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings. ред. / Henning Fernau. Springer Gabler, 2020. стр. 142-154 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 12159 LNCS).

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

Harvard

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 12159 LNCS, Springer Gabler, стр. 142-154, 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Российская Федерация, 29.06.2020. https://doi.org/10.1007/978-3-030-50026-9_10

APA

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

Vancouver

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

Author

Bazhenov, Nikolay. / Definable subsets of polynomial-time algebraic structures. Computer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings. Редактор / Henning Fernau. Springer Gabler, 2020. стр. 142-154 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{26d30ca6c69144ed92ab51d62b4a421b,
title = "Definable subsets of polynomial-time algebraic structures",
abstract = "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.",
keywords = "Boolean algebra, Computable structure theory, Hereditarily finite superstructure, List structure, Polynomial-time structure, ∆-definability",
author = "Nikolay Bazhenov",
year = "2020",
month = jan,
day = "1",
doi = "10.1007/978-3-030-50026-9_10",
language = "English",
isbn = "9783030500252",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Gabler",
pages = "142--154",
editor = "Henning Fernau",
booktitle = "Computer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings",
address = "Germany",
note = "15th International Computer Science Symposium in Russia, CSR 2020 ; Conference date: 29-06-2020 Through 03-07-2020",

}

RIS

TY - GEN

T1 - Definable subsets of polynomial-time algebraic structures

AU - Bazhenov, Nikolay

PY - 2020/1/1

Y1 - 2020/1/1

N2 - 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.

AB - 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.

KW - Boolean algebra

KW - Computable structure theory

KW - Hereditarily finite superstructure

KW - List structure

KW - Polynomial-time structure

KW - ∆-definability

UR - http://www.scopus.com/inward/record.url?scp=85087275997&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-50026-9_10

DO - 10.1007/978-3-030-50026-9_10

M3 - Conference contribution

AN - SCOPUS:85087275997

SN - 9783030500252

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 142

EP - 154

BT - Computer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings

A2 - Fernau, Henning

PB - Springer Gabler

T2 - 15th International Computer Science Symposium in Russia, CSR 2020

Y2 - 29 June 2020 through 3 July 2020

ER -

ID: 24722320