Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Checking Tests for Read-Once Functions over Arbitrary Bases
verfasst von : Dmitry V. Chistikov
Erschienen in: Computer Science – Theory and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A Boolean function is called read-once over a basis
B
if it can be expressed by a formula over
B
where no variable appears more than once. A checking test for a read-once function
f
over
B
depending on all its variables is a set of input vectors distinguishing
f
from all other read-once functions of the same variables. We show that every read-once function
f
over
B
has a checking test containing
O
(
n
l
) vectors, where
n
is the number of relevant variables of
f
and
l
is the largest arity of functions in
B
. For some functions, this bound cannot be improved by more than a constant factor. The employed technique involves reconstructing
f
from its
l
-variable projections and provides a stronger form of Kuznetsov’s classic theorem on read-once representations.