.png){kind=icon}
.png){kind=icon}
Return
Complexity issues for the iterated h-preordersa
.png){kind=icon}
PRE
AI
DOI：10.1177/22113568251335491.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
preorder
labeled forest
iterated h-preorder
structure
polynomial-time presentation
Journal
C
IF:
0.7
Papers:
12
Citations:
0