|
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.
Received: 13.06.2005
Citation:
A. A. Voronenko, “The representability of a Boolean function by a repetition-free formula can be verified by a circuit of linear complexity”, Diskr. Mat., 17:4 (2005), 111–115; Discrete Math. Appl., 15:5 (2005), 507–511
Linking options:
https://www.mathnet.ru/eng/dm134https://doi.org/10.4213/dm134 https://www.mathnet.ru/eng/dm/v17/i4/p111
|
Statistics & downloads: |
Abstract page: | 687 | Full-text PDF : | 252 | References: | 70 | First page: | 4 |
|