Complexity issues for the iterated h-preorders | Sciact - Система учета научной деятельности ИМ СО РАН

Complexity issues for the iterated h-preorders Научная публикация

Журнал

Computability
ISSN: 2211-3568 , E-ISSN: 2211-3576

Вых. Данные

Год: 2025, DOI: 10.1177/22113568251335491

Ключевые слова

preorder, labeled forest, iterated h-preorder, structure, polynomial-time presentation

Авторы

Alaev P. ¹ , Selivanov V. ²

Организации

1	S.L. Sobolev Institute of Mathematics
2	St. Petersburg State University

Информация о финансировании (1)

Институт математики им. С.Л. Соболева СО РАН

FWNF-2022-0011

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.

Alaev P. , Selivanov V.
Complexity issues for the iterated h-preorders
Computability. 2025. DOI: 10.1177/22113568251335491 WOS

Поступила в редакцию:	8 нояб. 2023 г.
Принята к публикации:	29 янв. 2025 г.

Web of science:

WOS:001645773100001

Пока нет цитирований