|
|
Международная школа-семинар "Синтаксис и семантика логических систем"
15 августа 2019 г. 16:10–16:30, Турбаза на берегу озера Хубсугул
|
|
|
|
|
|
О сложности мультиопераций ранга $k$ в классе стандартных форм
А. С. Казимиров Иркутский государственный университет
|
Количество просмотров: |
Эта страница: | 67 | Материалы: | 14 |
|
Аннотация:
Мультиоперации ранга k определяются как функции на множестве всех подмножеств некоторого k-элементного множества A, при этом значения мультиоперации на наборах из A задаются, а на остальных наборах определяются как объединение всех значений мультиопераций на соотвествующих наборах из A. Таким же образом определяется суперпозиция для мультиопераций.
Мультиоперации являются обобщением различных моделей неопределенности, частичных и гиперопераций.
Для мультиопераций можно определить стандартные формы через мультиоперацию пересечения. Для них можно естественным образом ввести понятие сложности по количеству компонент пересечения.
Ранее была найдена сложность стандартных форм мультиопераций ранга 2 сведением к длине наикратчайшей ДНФ. В данной работе обобщается предыдущий результат на мультиоперации ранга k.
Дополнительные материалы:
Слайды_Казимиров.pdf (270.4 Kb)
,
Казимиров.pdf (1.0 Mb)
|
|