No Detail Found!

On the limitations of ROBDDs in deciding the evasiveness of Boolean functions

Author(s)
Jes u´s Aransay Departamento de Matem a ́ticas y Computacio ́n, Universidad de La Rioja,Logro n ̃o,Spain
Laureano Lamb a´n Departamento de Matem a ́ticas y Computacio ́n, Universidad de La Rioja,Logro n ̃o,Spain
Julio Rubio Departamento de Matem a ́ticas y Computacio ́n, Universidad de La Rioja,Logro n ̃o,Spain
Abstract
In this paper, we prove that examining all the Reduced Ordered Binary Decision Diagrams (ROBDDs) of a Boolean monotone function is not enough to determine the evasiveness of the function. Working in the framework of simplicial topology, we introduce the notion of ordered non evasive simplicial complex, corresponding to our ROBDDs quest, and we prove that there exist non evasive simplicial complexes which are not ordered non evasive.
Publication Details
Page(s) 43-50
Published Journal: Discrete Mathematics Letters, Volume: 16, Issue: 0, Year: 2025

Request the full text from PASTIC

Keywords
simplicial complex, binary decision diagram, evasiveness
References
Adiprasito K. A.,Benedetti B.,Lutz F. H. .2017 .Extremal examples of collapsible complexes and random discrete morse theory, Discrete Comput. Geom, 57(4) : 824-853.
Aransay J.,Dubois J. .2023 .Evasiveness through binary decision diagrams. Intelligent Computer Mathematics. CICM 2023, : 37-52.
Barmak J. A.,Minian E. G. .2012 .Strong homotopy types, nerves and collapses. Discrete Comput. Geom, 47(2) : 301-328.
Bryant R. E. .1986 .Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput, 35 : 677-691.
Jefs R. A.,I. Novik R. A. .2021 .9) (. Int. Math. Res. Notices, : 7132-7158.
Knuth D. E.,Addison-Wesley D. E. .2009 .. The Art of Computer Programming, 4 : .
Nipkow T.,Assistant for Higher-Order Logic .2002 .. , : .
Scoville N. A. .2019 .. Amer. Math. Soc., : .
0

Citations

0

Downloads

24

Views