П. Е. Алаев, Дж. Тёрбер, А. Н. Фролов, “Вычислимость на линейных порядках, обогащённых предикатами”, Алгебра и логика, 2009, том 48, номер 5,страницы 549

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

Вычислимость на линейных порядках, обогащённых предикатами

П. Е. Алаев^ab, Дж. Тёрбер^c, А. Н. Фролов^d

^a Ин-т матем. им. С. Л. Соболева СО РАН, г. Новосибирск, РОССИЯ
^b Новосибирский гос. ун-т, г. Новосибирск, РОССИЯ
^c Math. Program, Eastern Oregon Univ., La Grande, OR, USA
^d НИИ матем. мех. им. Н. Г. Чеботарёва, Казанский гос. ун-т, г. Казань, РОССИЯ

Аннотация: Для квазидискретных линейных порядков $L$ доказываются критерии того, что сам порядок $L$ или структура $(L,\operatorname{adj})$ обладают вычислимым представлением, где $\operatorname{adj}(x,y)$ – предикат, выделяющий соседние элементы.

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

УДК: 510.5+510.6

Поступило: 17.12.2008