EUVIMEDEUVIMED entdecken
Crossref

Complexity issues for the iterated h-preorders

Pavel Alaev, Victor Selivanov

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →