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

Complexity Issues for the Iterated h-Preorders Научная публикация

Конференция

23rd IFIP WG 1.02 International Conference on Descriptional Complexity of Format Systems
05-05 сент. 2021 , Сеул

Журнал

Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349

Вых. Данные

Год: 2021, Том: 13037 LNCS, Страницы: 1-12 Страниц : 12 DOI: 10.1007/978-3-030-93489-7_1

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

Iterated h-preorder; Labeled forest; Polynomial-time presentation; Preorder; Structure

Авторы

Alaev P. ¹ , Selivanov V. ^1,2

Организации

1	S.L. Sobolev Institute of Mathematics SB RAS, Novosibirsk, Russian Federation
2	A.P. Ershov Institute of Informatics Systems SB RAS

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.

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

Web of science:	WOS:000884750600001
Scopus:	2-s2.0-85122575122
OpenAlex:	W4205721249

БД	Цитирований
Scopus	3
Web of science	2
OpenAlex	2