Подзоров С. Ю.
Об определении лахлановской полурешетки

Исследуются алгоритмические свойства полурешеток, введенных в 1972 г. Лахланом при изучении рекурсивно перечислимых m-степеней (так называемых лахлановских полурешеток). Показано, что в данном Лахланом определении условие на эффективность операции пересечения в задающей полурешетку последовательности можно опустить.

Podzorov S. Yu.
On the definition of a Lachlan semilattice

We study the algorithmic properties of the semilattices introduced in 1972 by Lachlan in his work on recursively enumerable m-degrees, the so-called Lachlan semilattices. We show that in Lachlan’s definition the effectivity condition on the meet can be omitted in the sequence determining such a semilattice.

Полный текст статьи / Full texts:

• PDF file (460 KB)
• PostScript file (915 KB)