Standard

A reducibility for the dot-depth hierarchy. / Selivanov, Victor L.; Wagner, Klaus W.

Mathematical Foundations of Computer Science 2004 (MFCS 2004). 2004. стр. 783-793 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 3153).

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

Harvard

Selivanov, VL & Wagner, KW 2004, A reducibility for the dot-depth hierarchy. в Mathematical Foundations of Computer Science 2004 (MFCS 2004). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 3153, стр. 783-793, Mathematical foundations of computer science-2024, 22/08/04. https://doi.org/10.1007/978-3-540-28629-5_61

APA

Selivanov, V. L., & Wagner, K. W. (2004). A reducibility for the dot-depth hierarchy. в Mathematical Foundations of Computer Science 2004 (MFCS 2004) (стр. 783-793). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 3153). https://doi.org/10.1007/978-3-540-28629-5_61

Vancouver

Selivanov VL, Wagner KW. A reducibility for the dot-depth hierarchy. в Mathematical Foundations of Computer Science 2004 (MFCS 2004). 2004. стр. 783-793. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-540-28629-5_61

Author

Selivanov, Victor L. ; Wagner, Klaus W. / A reducibility for the dot-depth hierarchy. Mathematical Foundations of Computer Science 2004 (MFCS 2004). 2004. стр. 783-793 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{3e3a0b04053e4b5884c797ec1bdbdedd,
title = "A reducibility for the dot-depth hierarchy",
abstract = "Hierarchies considered in computability theory and in complexity theory are related to some reducibilities in the sense that levels of the hierarchies are downward closed and have complete sets. In this paper we propose a reducibility having similar relationship to the Brzozowski's dot-depth hierarchy and some its refinements. We prove some basic facts on the corresponding degree structure and discuss relationships of the reducibility to complexity theory (via the leaf-language approach). {\textcopyright} Springer-Verlag 2004.",
author = "Selivanov, {Victor L.} and Wagner, {Klaus W.}",
year = "2004",
month = jan,
day = "1",
doi = "10.1007/978-3-540-28629-5_61",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "783--793",
booktitle = "Mathematical Foundations of Computer Science 2004 (MFCS 2004)",
note = "Mathematical foundations of computer science-2024 ; Conference date: 22-08-2004",

}

RIS

TY - GEN

T1 - A reducibility for the dot-depth hierarchy

AU - Selivanov, Victor L.

AU - Wagner, Klaus W.

PY - 2004/1/1

Y1 - 2004/1/1

N2 - Hierarchies considered in computability theory and in complexity theory are related to some reducibilities in the sense that levels of the hierarchies are downward closed and have complete sets. In this paper we propose a reducibility having similar relationship to the Brzozowski's dot-depth hierarchy and some its refinements. We prove some basic facts on the corresponding degree structure and discuss relationships of the reducibility to complexity theory (via the leaf-language approach). © Springer-Verlag 2004.

AB - Hierarchies considered in computability theory and in complexity theory are related to some reducibilities in the sense that levels of the hierarchies are downward closed and have complete sets. In this paper we propose a reducibility having similar relationship to the Brzozowski's dot-depth hierarchy and some its refinements. We prove some basic facts on the corresponding degree structure and discuss relationships of the reducibility to complexity theory (via the leaf-language approach). © Springer-Verlag 2004.

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

U2 - 10.1007/978-3-540-28629-5_61

DO - 10.1007/978-3-540-28629-5_61

M3 - Conference contribution

AN - SCOPUS:35048858043

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

SP - 783

EP - 793

BT - Mathematical Foundations of Computer Science 2004 (MFCS 2004)

T2 - Mathematical foundations of computer science-2024

Y2 - 22 August 2004

ER -

ID: 127140604