RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические заметки // Архив

Матем. заметки, 1987, том 41, выпуск 4, страницы 564–572 (Mi mzm4880)

Единичный тест замыкания для блочных схем

С. М. Вартанян


Аннотация: Рассматриваются единичные тесты замыкания для последователь ной блочной схемы (ПБС). В качестве блоков берутся схемы с двумя входами и двумя выходами, зависящие только от одной переменной. Выбираются 17 неэквивалентных блоков и рассматриваются схемы из этих блоков. Дается понятие существенного отрезка и доказывается следующая теорема о длине $|T|$ минимального теста:
$$ |T|\asymp\max\biggl(\biggl(n-\sum^t_{j=1}m_j\biggr), \sum^t_{j=1}\log_2m_j\biggr), $$
где $t$ – количество существенных отрезков, а $m_j$ – количество блоков некоторого типа в данном существенном отрезке. Библиогр. 5 назв.

УДК: 519.71

Поступило: 12.07.1983


 Англоязычная версия: Mathematical Notes, 1987, 41:4, 316–319

Реферативные базы данных:


© МИАН, 2024