[1] Binary Decision Diagrams
This paper describes a method for defining, analyzing, testing, and implementing large digital functions by means of a binary decision diagram. This diagram provides a complete, concise, “implementation-free” description of the digital functions involved. Methods are described for deriving these diagrams and examples are given for a number of basic combinational and sequential devices. Techniques are then outlined for using the diagrams to analyze the functions involved, for test generation, and for obtaining various implementations. It is shown that the diagrams are especially suited for processing by a computer. Finally, methods are described for introducing inversion and for directly “interconnecting” diagrams to define still larger functions. An example of the carry look-ahead adder is included.
[2] Representation of switching circuits by binary-decision programs
A binary-decision program is a program consisting of a string of two-address conditional transfer instructions. The paper shows the relationship between switching circuits and binary-decision programs and gives a set of simple rules by which one can transform binary-decision programs to switching circuits. It then shows that, in regard to the computation of switching functions, binary-decision programming representation is superior to the usual Boolean representation.
[3] Symbolic Boolean manipulation with ordered binary-decision diagrams
Ordered Binary-Decision Diagrams (OBDDs) represent Boolean functions as directed acyclic graphs. They form a canonical representation, making testing of functional properties such as satisfiability and equivalence straightforward. A number of operations on Boolean functions can be implemented as graph algorithms on OBDD data structures. Using OBDDs, a wide variety of problems can be solved through symbolic analysis. First, the possible variations in system parameters and operating conditions are encoded with Boolean variables. Then the system is evaluated for all variations by a sequence of OBDD operations. Researchers have thus solved a number of problems in digital-system design, finite-state system analysis, artificial intelligence, and mathematical logic. This paper describes the OBDD data structure and surveys a number of applications that have been solved by OBDD-based symbolic analysis.
[4] Computation of k-out-of-n System Reliability via Reduced Ordered Binary Decision Diagrams
A prominent reliability model is that of the partially-redundant (k-out-of-n) system. We use algebraic as well as signal-flow-graph methods to explore and expose the AR algorithm for computing k-out-of-n reliability. We demonstrate that the AR algorithm is, in fact, both a recursive and an iterative implementation of the strategy of Reduced Ordered Binary Decision Diagrams (ROBDDs). The underlying ROBDD for the AR recursive algorithm is represented by a compact Signal Flow Graph (SFG) that is used to deduce AR iterative algorithms of quadratic temporal complexity and linear spatial complexity. Extensions of the AR algorithm for (single or scalar) threshold, double-threshold, vector-threshold, and k-to-l-out-of-n systems have similar ROBDD interpretations.
[5] New Approaches for Decision Making in Information Systems via Decision Diagrams
In this paper, new approach for data representation using decision diagrams in information systems are studied. We indicate data using binary decision diagrams and ID3-Decision tree learning algorithm to reduct information systems. Some algorithms are built and developed to refinement the process of decision making in information systems. Illustrative figures and examples are presented and real life application examples are given.
Reference
[1] Akers, S.B., 1978. Binary decision diagrams. IEEE Computer Architecture Letters, 27(06), pp.509-516.
[2] Lee, C.Y., 1959. Representation of switching circuits by binary-decision programs. The Bell System Technical Journal, 38(4), pp.985-999.
[3] Bryant, R.E., 1992. Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Computing Surveys (CSUR), 24(3), pp.293-318.
[4] Rushdi, A.M.A. and Alturki, A.M., 2017. Computation of k-out-of-n system reliability via reduced ordered binary decision diagrams. Journal of Advances in Mathematics and Computer Science, pp.1-9.
[5] Salama, A.S., 2015. New Approaches for Decision Making in Information Systems via Decision Diagrams. Journal of Advances in Mathematics and Computer Science, pp.418-432.
