Standard

Complexity issues for preorders on finite labeled forests. / Hertling, Peter; Selivanov, Victor.

Models of Computation in Context (CiE 2011). 2011. p. 112-121 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6735).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Hertling, P & Selivanov, V 2011, Complexity issues for preorders on finite labeled forests. in Models of Computation in Context (CiE 2011). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6735, pp. 112-121, computability in europe-2011, 27/06/11. https://doi.org/10.1007/978-3-642-21875-0_12

APA

Hertling, P., & Selivanov, V. (2011). Complexity issues for preorders on finite labeled forests. In Models of Computation in Context (CiE 2011) (pp. 112-121). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6735). https://doi.org/10.1007/978-3-642-21875-0_12

Vancouver

Hertling P, Selivanov V. Complexity issues for preorders on finite labeled forests. In Models of Computation in Context (CiE 2011). 2011. p. 112-121. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-21875-0_12

Author

Hertling, Peter ; Selivanov, Victor. / Complexity issues for preorders on finite labeled forests. Models of Computation in Context (CiE 2011). 2011. pp. 112-121 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{ebe968c735be40848646d378ae67701e,
title = "Complexity issues for preorders on finite labeled forests",
abstract = "We prove that three preorders on the finite k-labeled forests are polynomial time computable. Together with an earlier result of the first author, this implies polynomial-time computability for an important initial segment of the corresponding degrees of discontinuity of k-partitions on the Baire space. Furthermore, we show that on ω-labeled forests the first of these three preorders is polynomial time computable as well while the other two preorders are NP-complete. {\textcopyright} 2011 Springer-Verlag.",
author = "Peter Hertling and Victor Selivanov",
year = "2011",
month = sep,
day = "26",
doi = "10.1007/978-3-642-21875-0_12",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "112--121",
booktitle = "Models of Computation in Context (CiE 2011)",
note = "computability in europe-2011 ; Conference date: 27-06-2011",

}

RIS

TY - GEN

T1 - Complexity issues for preorders on finite labeled forests

AU - Hertling, Peter

AU - Selivanov, Victor

PY - 2011/9/26

Y1 - 2011/9/26

N2 - We prove that three preorders on the finite k-labeled forests are polynomial time computable. Together with an earlier result of the first author, this implies polynomial-time computability for an important initial segment of the corresponding degrees of discontinuity of k-partitions on the Baire space. Furthermore, we show that on ω-labeled forests the first of these three preorders is polynomial time computable as well while the other two preorders are NP-complete. © 2011 Springer-Verlag.

AB - We prove that three preorders on the finite k-labeled forests are polynomial time computable. Together with an earlier result of the first author, this implies polynomial-time computability for an important initial segment of the corresponding degrees of discontinuity of k-partitions on the Baire space. Furthermore, we show that on ω-labeled forests the first of these three preorders is polynomial time computable as well while the other two preorders are NP-complete. © 2011 Springer-Verlag.

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

U2 - 10.1007/978-3-642-21875-0_12

DO - 10.1007/978-3-642-21875-0_12

M3 - Conference contribution

AN - SCOPUS:80053029158

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

SP - 112

EP - 121

BT - Models of Computation in Context (CiE 2011)

T2 - computability in europe-2011

Y2 - 27 June 2011

ER -

ID: 127085904