Complexity Issues for the Iterated h-Preorders Full article
| Conference |
23rd IFIP WG 1.02 International Conference on Descriptional Complexity of Format Systems 05-05 Sep 2021 , Сеул |
||||
|---|---|---|---|---|---|
| Journal |
Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349 |
||||
| Output data | Year: 2021, Volume: 13037 LNCS, Pages: 1-12 Pages count : 12 DOI: 10.1007/978-3-030-93489-7_1 | ||||
| Tags | Iterated h-preorder; Labeled forest; Polynomial-time presentation; Preorder; Structure | ||||
| Authors |
|
||||
| Affiliations |
|
Abstract:
We show that many natural structures related to the so called homomorphic 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 apply these results to relevant questions of automata and computability theory. © 2021, IFIP International Federation for Information Processing.
Cite:
Alaev P.
, Selivanov V.
Complexity Issues for the Iterated h-Preorders
Lecture Notes in Computer Science. 2021. V.13037 LNCS. P.1-12. DOI: 10.1007/978-3-030-93489-7_1 WOS Scopus OpenAlex
Complexity Issues for the Iterated h-Preorders
Lecture Notes in Computer Science. 2021. V.13037 LNCS. P.1-12. DOI: 10.1007/978-3-030-93489-7_1 WOS Scopus OpenAlex
Identifiers:
| Web of science: | WOS:000884750600001 |
| Scopus: | 2-s2.0-85122575122 |
| OpenAlex: | W4205721249 |