Complexity issues for the iterated h-preorders Full article
| Journal |
Computability
ISSN: 2211-3568 , E-ISSN: 2211-3576 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2025, Volume: 14, Number: 3-4, Pages: 139-156 Pages count : 18 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. V.14. N3-4. P.139-156. DOI: 10.1177/22113568251335491 WOS
Complexity issues for the iterated h-preorders
Computability. 2025. V.14. N3-4. P.139-156. DOI: 10.1177/22113568251335491 WOS
Dates:
| Submitted: | Nov 8, 2023 |
| Accepted: | Jan 29, 2025 |
| Published print: | Nov 30, 2025 |
| Published online: | Nov 30, 2025 |
Identifiers:
| ≡ Web of science: | WOS:001645773100001 |