Standard

Fine hierarchies and m-reducibilities in theoretical computer science. / Selivanov, Victor L.

в: Theoretical Computer Science, Том 405, № 1-2, 06.10.2008, стр. 116-163.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Selivanov, VL 2008, 'Fine hierarchies and m-reducibilities in theoretical computer science', Theoretical Computer Science, Том. 405, № 1-2, стр. 116-163. https://doi.org/10.1016/j.tcs.2008.06.031

APA

Selivanov, V. L. (2008). Fine hierarchies and m-reducibilities in theoretical computer science. Theoretical Computer Science, 405(1-2), 116-163. https://doi.org/10.1016/j.tcs.2008.06.031

Vancouver

Selivanov VL. Fine hierarchies and m-reducibilities in theoretical computer science. Theoretical Computer Science. 2008 Окт. 6;405(1-2):116-163. https://doi.org/10.1016/j.tcs.2008.06.031

Author

Selivanov, Victor L. / Fine hierarchies and m-reducibilities in theoretical computer science. в: Theoretical Computer Science. 2008 ; Том 405, № 1-2. стр. 116-163.

BibTeX

@article{86519b11d0414d4cb9d75456ffae7edf,
title = "Fine hierarchies and m-reducibilities in theoretical computer science",
abstract = "This is a survey of results about versions of fine hierarchies and many-one reducibilities that appear in different parts of theoretical computer science. These notions and related techniques play a crucial role in understanding complexity of finite and infinite computations. We try not only to present the corresponding notions and facts from the particular fields but also to identify the unifying notions, techniques and ideas. {\textcopyright} 2008 Elsevier B.V. All rights reserved.",
keywords = "ω-language, Alternating tree, Automaton, Baire domain, Baire space, Boolean term, Complexity, Computability, Difference hierarchy, Fine hierarchy, Hierarchy, k-partition, Language, Logic, m-reducibility, Topology",
author = "Selivanov, {Victor L.}",
year = "2008",
month = oct,
day = "6",
doi = "10.1016/j.tcs.2008.06.031",
language = "English",
volume = "405",
pages = "116--163",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "1-2",

}

RIS

TY - JOUR

T1 - Fine hierarchies and m-reducibilities in theoretical computer science

AU - Selivanov, Victor L.

PY - 2008/10/6

Y1 - 2008/10/6

N2 - This is a survey of results about versions of fine hierarchies and many-one reducibilities that appear in different parts of theoretical computer science. These notions and related techniques play a crucial role in understanding complexity of finite and infinite computations. We try not only to present the corresponding notions and facts from the particular fields but also to identify the unifying notions, techniques and ideas. © 2008 Elsevier B.V. All rights reserved.

AB - This is a survey of results about versions of fine hierarchies and many-one reducibilities that appear in different parts of theoretical computer science. These notions and related techniques play a crucial role in understanding complexity of finite and infinite computations. We try not only to present the corresponding notions and facts from the particular fields but also to identify the unifying notions, techniques and ideas. © 2008 Elsevier B.V. All rights reserved.

KW - ω-language

KW - Alternating tree

KW - Automaton

KW - Baire domain

KW - Baire space

KW - Boolean term

KW - Complexity

KW - Computability

KW - Difference hierarchy

KW - Fine hierarchy

KW - Hierarchy

KW - k-partition

KW - Language

KW - Logic

KW - m-reducibility

KW - Topology

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

U2 - 10.1016/j.tcs.2008.06.031

DO - 10.1016/j.tcs.2008.06.031

M3 - Article

AN - SCOPUS:50549086093

VL - 405

SP - 116

EP - 163

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1-2

ER -

ID: 127087737