Эта публикация цитируется в
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