RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 2010, том 49, номер 2, страницы 181–194 (Mi al435)

Эта публикация цитируется в 1 статье

Определимость операций замыкания в $h$-предпорядке размеченных лесов

А. В. Жуковa, О. В. Кудиновb, В. Л. Селивановc

a Новосибирский гос. пед. ун-т, г. Новосибирск, РОССИЯ
b Ин-т матем. им. С. Л. Соболева СО РАН, г. Новосибирск, РОССИЯ
c Ин-т систем информ. им. А. П. Ершова СО РАН, г. Новосибирск, РОССИЯ

Аннотация: Доказывается определимость естественных операций замыкания на фактор-структурах $h$-предпорядка конечных и (не более чем) счётных $k$-размеченных лесов ($k\ge3$) при условии, что минимальные ненулевые элементы допускаются в качестве параметров. Это усиливает полученный ранее результат об определимости любого элемента $h$-предпорядка конечных $k$-размеченных лесов в языке первого порядка и любого элемента $h$-предпорядка (не более чем) счётных $k$-размеченных лесов в языке $L_{\omega_1\omega}$, в обоих случаях $k\ge3$ и минимальные ненулевые элементы допускаются в качестве параметров. Аналогичные утверждения верны для двух других близких структур: $h$-предпорядка конечных (соответственно счётных) $k$-размеченных деревьев и $k$-размеченных деревьев с фиксированной меткой корневого элемента.

Ключевые слова: размеченный лес, размеченное дерево, $h$-предпорядок, определимость, операция замыкания.

УДК: 510.532

Поступило: 29.10.2008


 Англоязычная версия: Algebra and Logic, 2010, 49:2, 120–129

Реферативные базы данных:


© МИАН, 2024