The Growing Lower Bound for the Shannon Function of the
 Detection Test Set Cardinality with Respect to Single Stuck-at
Faults at the Outputs of Gates in Formulas over Bases Close to the
                          Standard One

Cui Zhenyu; Romanov Dmitrii Sergeevich

The Growing Lower Bound for the Shannon Function of the Detection Test Set Cardinality with Respect to Single Stuck-at Faults at the Outputs of Gates in Formulas over Bases Close to the Standard One

Cui Z., Romanov D. S.

Cui Zhenyu

postgraduate student of CMC Faculty, Lomonosov MSU

Romanov Dmitrii Sergeevich

professor of CMC Faculty, Lomonosov MSU

Received: 25 Mar 2026

Published: 2025, vol. 29, issue 2, pp. 162–172

Download full text (In Russian)

Abstract

Lower bounds asymptotically equal to the number of variables are established for Shannon functions of the cardinality of single fault detection test set with respect to stuck-at faults at outputs of gates in Boolean formulas over bases \(\{x\mathbin{\&}y,\,x\vee y,\,\bar x\}\), \(\{x\mathbin{\&}y,\,\bar x\}\), \(\{x\vee y,\,\bar x\}\), \(\{x\mathbin{\&}{\bar y},\,\bar x\}\), \(\{x\vee {\bar y},\,\bar x\}\).

Keywords: fault detection test set, stuck-at faults, Boolean formula

BibTeX

@article{IS-Cui-Romanov2025,
  author  = {Cui, Zhenyu and Romanov, Dmitrii Sergeevich},
  title   = {{The Growing Lower Bound for the Shannon Function of the
 Detection Test Set Cardinality with Respect to Single Stuck-at
Faults at the Outputs of Gates in Formulas over Bases Close to the
                          Standard One}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2025},
  volume  = {29},
  number  = {2},
  pages   = {162--172},
}

AMSBIB

\Bibitem{IS-Cui-Romanov2025}
\by Z.~Cui, D.\,S.~Romanov
\paper The Growing Lower Bound for the Shannon Function of the
 Detection Test Set Cardinality with Respect to Single Stuck-at
Faults at the Outputs of Gates in Formulas over Bases Close to the
                          Standard One
\jour Intelligent Systems. Theory and Applications
\yr 2025
\vol 29
\issue 2
\pages 162--172
\lang In Russian

Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue