Complexity issues for the iterated h-preorders Full article
| Journal |
Computability
ISSN: 2211-3568 , E-ISSN: 2211-3576 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2025, DOI: 10.1177/22113568251335491 | ||||
| Tags | preorder, labeled forest, iterated h-preorder, structure, polynomial-time presentation | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0011 |
Abstract:
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.
Cite:
Alaev P.
, Selivanov V.
Complexity issues for the iterated h-preorders
Computability. 2025. DOI: 10.1177/22113568251335491 WOS
Complexity issues for the iterated h-preorders
Computability. 2025. DOI: 10.1177/22113568251335491 WOS
Dates:
| Submitted: | Nov 8, 2023 |
| Accepted: | Jan 29, 2025 |
Identifiers:
| Web of science: | WOS:001645773100001 |
Citing:
Пока нет цитирований