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

Статья в сборнике "Математические вопросы кибернетики" №13, Москва, 2004
Авторы: Сафин Р.Ф.
О соотношении между глубиной и сложностью формул для предполных классов k-значной логики
Аннотация:
В работе рассматривается задача о соотношении глубины и сложности формул, реализующих функции из предполных классов k-значной логики. Для всех предполных классов типов E, B, L, P, а также некоторых предполных классов типов O и C в Pk, k ≥ 3, показано, что любая конечная система функций A, порождающая один из этих классов, удовлетворяет следующему условию: найдутся такие константы c и d, что для любой функции f из [A] глубина D(f) и сложность L(f) функции f в классе формул над A связаны соотношением D(f) ≤ c log2 L(f) + d. Также доказано существование конечных порождающих систем, удовлетворяющих этому условию, для всех предполных классов в Pk, 2 ≤ k ≤ 7, и для всех предполных классов типа C в Pk, k ≥ 2.
Ключевые слова:
предполные классы k-значной логики, глубина и сложность формул
Язык публикации: русский, страниц: 56 (с. 223-278)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст: Сведения об авторах:
  • Сафин Ринат Фатехович,  ,  механико-математический ф-т МГУ им. М.В.Ломоносова