Аннотация:
Рассмотрены вопросы алгоритмической зависимости различных отношений на линейных порядках. Доказано, что отношения соседства, блока, плотности, предельности справа и предельности слева являются алгоритмически независимыми. Введены новые отношения, определимые в сигнатуре линейного порядка, являющиеся алгоритмически зависимыми, и изучены их свойства.
Ключевые слова:линейный порядок, отношение соседства, отношение блока, отношение плотности, отношение предельности справа, отношение предельности слева, алгоритмическая независимость.
Полный текст:
PDF файл (207 kB)