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. ed. / Henning Fernau. Springer Gabler, 2020. p. 142-154 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12159 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Bazhenov, N 2020,
Definable subsets of polynomial-time algebraic structures. in H Fernau (ed.),
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), vol. 12159 LNCS, Springer Gabler, pp. 142-154, 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russian Federation,
29.06.2020.
https://doi.org/10.1007/978-3-030-50026-9_10
APA
Vancouver
Bazhenov N.
Definable subsets of polynomial-time algebraic structures. In Fernau H, editor, Computer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings. Springer Gabler. 2020. p. 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. editor / Henning Fernau. Springer Gabler, 2020. pp. 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 -
