RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive
Diskr. Mat., 2005 Volume 17, Issue 4, Pages 111–115 (Mi dm134)
The representability of a Boolean function by a repetition-free formula can be verified by a circuit of linear complexity

A. A. Voronenko


Abstract: We prove that the representability of a Boolean function by a repetition-free formula can be verified by a circuit of linear complexity.
This research was supported by the Russian Foundation for Basic Research, grant 04–01–00359.

UDC: 519.7

Received: 13.06.2005

DOI: 10.4213/dm134


 English version: Discrete Mathematics and Applications, 2005, 15:5, 507–511

Bibliographic databases:

© Steklov Math. Inst. of RAS, 2024