Complexity issues for the iterated h-preorders
Computability · 2025
DOI: 10.1177/22113568251335491 ↗Kurz gefasst
Fachartikel in der Zeitschrift Computability, 2025. Verfasst von Pavel Alaev und 1 weiteren Autor:innen. Die Arbeit nennt 15 Literaturangaben.
Abstract (Originalsprache)
We show that natural structures related to the so called homomorphism 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 discuss possible applications of these results to relevant questions of automata and computability theory.
Zitieren
APA
Alaev, P., & Selivanov, V. (2025). Complexity issues for the iterated h-preorders. Computability. https://doi.org/10.1177/22113568251335491
Vancouver
Alaev P, Selivanov V. Complexity issues for the iterated h-preorders. Computability. 2025. doi:10.1177/22113568251335491
BibTeX
@article{Alaev2025,
author = {Alaev, Pavel and Selivanov, Victor},
title = {Complexity issues for the iterated h-preorders},
journal = {Computability},
year = {2025},
doi = {10.1177/22113568251335491}
}
EUVIMED