We show that natural structures related to the so called homomorphism preorder (or -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.
HertlingP. Topologische Komplexitätsgrade von Funktionen mit endlichem Bild. Informatik-Berichte 152, 34 pages, Fernuniversität Hagen, December 1993.
2.
SelivanovV. A Q-Wadge hierarchy in quasi-polish spaces. J Symb Log2022; 87: 732–757.
3.
SelivanovV. Non-collapse of the effective Wadge hierarchy. Computability2022; 11: 335–358.
4.
SelivanovV. Wadge degrees of classes of omega-regular k-partitions. J Autom Lang Combin2023; 28: 167–199.
5.
SelivanovV. Fine hierarchies via Priestley duality. Ann Pure Appl Log2012; 163: 1075–1107.
6.
HertlingPSelivanovVL. Complexity issues for preorders on finite labeled forests. In: Brattka V, Diener H and Spreen D (eds) Logic, computation, hierarchies. Boston-Berlin: Ontos Publishing, de Gruiter, 2014, pp.165–190.
7.
AhoAHopcroftJVUllmanJE. The design and analysis of computer algorithms. Massachusetts: Addison Wesley, Massachusetts, 1969.
8.
AlaevPE. Polynomially computable structures with finitely many generators. Algebra Log2020; 59: 266–272.
9.
CenzerDRemmelJ. Polynomial time versus recursive models. Ann Pure Appl Log1991; 54: 17–58.
10.
AlaevPE. Structures computable in polynomial time. I. Algebra Log2016; 55: 421–435.
11.
SelivanovV. Classifying -regular aperiodic k-partitions. In: Jiraskova G and Pighizzini G (eds) Proc. of DCFS-2020, LNCS 12442, 2020, pp.193–205.
12.
SelivanovVL. A fine hierarchy of -regular k-partitions. In: Löwe B et al. (eds): CiE 2011, LNCS, vol. 6735. Heidelberg: Springer, 2011, pp.260–269.
13.
WilkeTYooH. Computing the Wadge degree, the Lipschitz degree, and the Rabin index of a regular language of infinite words in polynomial time. In: Mosses PD, Nielsen M and Schwartzbach MI (eds) Lecture Notes in Computer Science, vol. 915. Berlin: Springer, 1995, pp.288–302.
14.
PodolskiiVSelivanovV. Complexity aspects of the extension of Wagner’s hierarchy to k-partitions. In: Giovanni P and Florin M (eds)Electronic proceedings in theoretical computer science, vol. 407. NCMA, 2024, pp.186–197.
15.
AlaevPESelivanovVL. Complexity issues for the iterated -preorders. In: Han Y-S and Ko S-K (eds): DCFS 2021, LNCS 13037, 2021, pp.1–12.
