Standard

Complexity Issues for the Iterated h-Preorders. / Alaev, Pavel; Selivanov, Victor.

Descriptional Complexity of Formal Systems. 2021. p. 1-12 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13037).

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

Harvard

Alaev, P & Selivanov, V 2021, Complexity Issues for the Iterated h-Preorders. in Descriptional Complexity of Formal Systems. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13037, pp. 1-12, 22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020, Vienna, Austria, 24/08/20. https://doi.org/10.1007/978-3-030-93489-7_1

APA

Alaev, P., & Selivanov, V. (2021). Complexity Issues for the Iterated h-Preorders. In Descriptional Complexity of Formal Systems (pp. 1-12). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13037). https://doi.org/10.1007/978-3-030-93489-7_1

Vancouver

Alaev P, Selivanov V. Complexity Issues for the Iterated h-Preorders. In Descriptional Complexity of Formal Systems. 2021. p. 1-12. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-93489-7_1

Author

Alaev, Pavel ; Selivanov, Victor. / Complexity Issues for the Iterated h-Preorders. Descriptional Complexity of Formal Systems. 2021. pp. 1-12 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{905967d000b34807b19f2b6d86803082,
title = "Complexity Issues for the Iterated h-Preorders",
abstract = "We show that many natural structures related to the so called homomorphic preorder (or h-preorder) on the iterated labeled forests have isomorphic copies computable in polynomial time. Moreover, the polynomials in the upper bounds are of low degree which makes the computational content of the whole theory feasible. We apply these results to relevant questions of automata and computability theory.",
keywords = "Iterated h-preorder, Labeled forest, Polynomial-time presentation, Preorder, Structure",
author = "Pavel Alaev and Victor Selivanov",
year = "2021",
month = jan,
day = "1",
doi = "10.1007/978-3-030-93489-7_1",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "1--12",
booktitle = "Descriptional Complexity of Formal Systems",
note = "22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020 ; Conference date: 24-08-2020 Through 26-08-2020",

}

RIS

TY - GEN

T1 - Complexity Issues for the Iterated h-Preorders

AU - Alaev, Pavel

AU - Selivanov, Victor

PY - 2021/1/1

Y1 - 2021/1/1

N2 - We show that many natural structures related to the so called homomorphic preorder (or h-preorder) on the iterated labeled forests have isomorphic copies computable in polynomial time. Moreover, the polynomials in the upper bounds are of low degree which makes the computational content of the whole theory feasible. We apply these results to relevant questions of automata and computability theory.

AB - We show that many natural structures related to the so called homomorphic preorder (or h-preorder) on the iterated labeled forests have isomorphic copies computable in polynomial time. Moreover, the polynomials in the upper bounds are of low degree which makes the computational content of the whole theory feasible. We apply these results to relevant questions of automata and computability theory.

KW - Iterated h-preorder

KW - Labeled forest

KW - Polynomial-time presentation

KW - Preorder

KW - Structure

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

U2 - 10.1007/978-3-030-93489-7_1

DO - 10.1007/978-3-030-93489-7_1

M3 - Conference contribution

AN - SCOPUS:85122575122

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

SP - 1

EP - 12

BT - Descriptional Complexity of Formal Systems

T2 - 22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020

Y2 - 24 August 2020 through 26 August 2020

ER -

ID: 126985055