Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №7, Москва, 1998
Авторы: Шоломов Л.А.
Представление и исследование порядковых моделей выбора средствами логики первого порядка
Аннотация:
Функция выбора C на Rn сопоставляет каждому X⊆Rn выбранное множество C(X)⊆X. Она называется порядковой, если для любого строго монотонно отображения ψ: Rn→Rn и всякого X⊆Rn) выполнено C(ψ(X))=ψ(C(X)). В статье предложен и изучен метод формализации порядковых функций выбора на Rn средствами логики первого порядка. Исследованы на формализуемость все встречающиеся в научной литературе порядковые модели выбора по бинарному отношению. Для большинства из них (22 из 28) указаны формализации, для остальных корректно доказана неформализуемость. Рассмотрены операции над функциями выбора (параллельная и последовательная композиция, ветвление, обращение, ограниченная обратная связь) и для каждой из них указано соответствующее преобразование формализаций. Это позволяет формализовать сложные иерархические модели порядкового выбора. Исследован на алгоритмическую разрешимость, NP-трудность и полиномиальность ряд задач, связанных с построением, упрощением и минимизацией формализаций, где под сложностью формализации понимается число кванторов в предваренной форме.
Ключевые слова:
функция выбора, порядковый выбор, логика первого порядка, формализация порядкового выбора, преобразования формализаций, сложность формализации
Язык публикации: русский, страниц: 34 (с. 169-202)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст: Сведения об авторах:
  • Шоломов Лев Абрамович,  ,  Федеральный исследовательский центр ''Информатика и управление'' РАН