Control of complex networks such as gene regulatory networks is one of the fundamental problems in control theory. A Boolean network (BN) is one of the mathematical models in complex networks, and represents the dynamic behavior by Boolean functions. In this paper, a solution method for the finite-time control problem of BNs is proposed using a BDD (binary decision diagram). In this problem, we find all combinations of the initial state and the control input sequence such that a certain control specification is satisfied. The use of BDDs enables us to solve this problem for BNs such that the conventional method cannot be applied. First, after the outline of BNs and BDDs is explained, the problem studied in this paper is given. Next, a solution method using BDDs is proposed. Finally, a numerical example on a 67-node BN is presented.

Binary Decision Diagrams (BDDs) are an important data structure for the design of digital circuits using VLSI CAD tools. The ordering of variables affects the total number of nodes and path length in the BDDs. Finding a good variable ordering is an optimization problem and previously many optimization approaches have been implemented for BDDs in a number of research works. In this paper, an optimization approach based on Spider Monkey Optimization (SMO) algorithm is proposed for the BDD variable ordering problem targeting number of nodes and longest path length. SMO is a well-known swarm intelligence-based optimization approach based on spider monkeys foraging behavior. The proposed work has been compared with other latest BDD reordering approaches using Particle Swarm Optimization (PSO) algorithm. The results obtained show significant improvement over the Particle Swarm Optimization method. The proposed SMO-based method is applied to different benchmark digital circuits having different levels of complexities. The node count and longest path length for the maximum number of tested circuits are found to be better in SMO than PSO.

Optical logic circuits based on integrated nanophotonics attract significant interest due to their ultra-high-speed operation. However, the power dissipation of conventional optical logic circuits is exponential to the number of inputs of target logic functions. This paper proposes a synthesis method reducing power dissipation to a polynomial order of the number of inputs while exploiting the high-speed nature. Our method divides the target logic function into multiple sub-functions with Optical-to-Electrical (OE) converters. Each sub-function has a smaller number of inputs than that of the original function, which enables to exponentially reduce the power dissipated by an optical logic circuit representing the sub-function. The proposed synthesis method can mitigate the OE converter delay overhead by parallelizing sub-functions. We apply the proposed synthesis method to the ISCAS'85 benchmark circuits. The power consumption of the conventional circuits based on the Binary Decision Diagram (BDD) is at least three orders of magnitude larger than that of the optical logic circuits synthesized by the proposed method. The proposed method reduces the power consumption to about 100mW. The delay of almost all the circuits synthesized by the proposed method is kept less than four times the delay of the conventional BDD-based circuit.

Boolean networks (BNs) are considered as popular formal models for the dynamics of gene regulatory networks. There are many different types of BNs, depending on their updating scheme (synchronous, asynchronous, deterministic, or non-deterministic), such as Classical Random Boolean Networks (CRBNs), Asynchronous Random Boolean Networks (ARBNs), Generalized Asynchronous Random Boolean Networks (GARBNs), Deterministic Asynchronous Random Boolean Networks (DARBNs), and Deterministic Generalized Asynchronous Random Boolean Networks (DGARBNs). An important long-term behavior of BNs, so-called attractor, can provide valuable insights into systems biology (e.g., the origins of cancer). In the previous paper [1], we have studied properties of attractors of GARBNs, their relations with attractors of CRBNs, also proposed different algorithms for attractor detection. In this paper, we propose a new algorithm based on SAT-based bounded model checking to overcome inherent problems in these algorithms. Experimental results prove the effectiveness of the new algorithm. We also show that studying attractors of GARBNs can pave potential ways to study attractors of ARBNs.

Recent years have witnessed a rapid increase in cyber-attacks through unauthorized accesses and DDoS attacks. Since packet classification is a fundamental technique to prevent such illegal communications, it has gained considerable attention. Packet classification is achieved with a linear search on a classification rule list that represents the packet classification policy. As such, a large number of rules can result in serious communication latency. To decrease this latency, the problem is formalized as optimal rule ordering (ORO). In most cases, this problem aims to find the order of rules that minimizes latency while satisfying the dependency relation of the rules, where rules ri and rj are dependent if there is a packet that matches both ri and rj and their actions applied to packets are different. However, there is a case in which although the ordering violates the dependency relation, the ordering satisfies the packet classification policy. Since such an ordering can decrease the latency compared to an ordering under the constraint of the dependency relation, we have introduced a new model, called relaxed optimal rule ordering (RORO). In general, it is difficult to determine whether an ordering satisfies the classification policy, even when it violates the dependency relation, because this problem contains unsatisfiability. However, using a zero-suppressed binary decision diagram (ZDD), we can determine it in a reasonable amount of time. In this paper, we present a simulated annealing method for RORO which interchanges rules by determining whether rules ri and rj can be interchanged in terms of policy violation using the ZDD. The experimental results show that our method decreases latency more than other heuristics.

Optical circuits using nanophotonic devices attract significant interest due to its ultra-high speed operation. As a consequence, the synthesis methods for the optical circuits also attract increasing attention. However, existing methods for synthesizing optical circuits mostly rely on straight-forward mappings from established data structures such as Binary Decision Diagram (BDD). The strategy of simply mapping a BDD to an optical circuit sometimes results in an explosion of size and involves significant power losses in branches and optical devices. To address these issues, this paper proposes a method for reducing the size of BDD-based optical logic circuits exploiting wavelength division multiplexing (WDM). The paper also proposes a method for reducing the number of branches in a BDD-based circuit, which reduces the power dissipation in laser sources. Experimental results obtained using a partial product accumulation circuit used in a 4-bit parallel multiplier demonstrates significant advantages of our method over existing approaches in terms of area and power consumption.

This paper deals with the constrained DAG shortest path problem (CDSP), which finds the shortest path on a given directed acyclic graph (DAG) under any logical constraints posed on taken edges. There exists a previous work that uses binary decision diagrams (BDDs) to represent the logical constraints, and traverses the input DAG and the BDD simultaneously. The time and space complexity of this BDD-based method is derived from BDD size, and tends to be fast only when BDDs are small. However, since it does not prioritize the search order, there is considerable room for improvement, particularly for large BDDs. We combine the well-known A* search with the BDD-based method synergistically, and implement several novel heuristic functions. The key insight here is that the ‘shortest path’ in the BDD is a solution of a relaxed problem, just as the shortest path in the DAG is. Experiments, particularly practical machine learning applications, show that the proposed method decreases search time by up to 2 orders of magnitude, with the specific result that it is 2,000 times faster than a commercial solver. Moreover, the proposed method can reduce the peak memory usage up to 40 times less than the conventional method.

For subgraph enumeration problems, very efficient algorithms have been proposed whose time complexities are far smaller than the number of subgraphs. Although the number of subgraphs can exponentially increase with the input graph size, these algorithms exploit compressed representations to output and maintain enumerated subgraphs compactly so as to reduce the time and space complexities. However, they are designed for enumerating only some specific types of subgraphs, e.g., paths or trees. In this paper, we propose an algorithm framework, called the frontier-based search, which generalizes these specific algorithms without losing their efficiency. Our frontier-based search will be used to resolve various practical problems that include constrained subgraph enumeration.

Graphical User Interfaces (GUIs) are critical for the security, safety and reliability of software systems. Injection attacks, for instance via SQL, succeed due to insufficient input validation and can be avoided if contract-based approaches, such as Design by Contract, are followed in the software development lifecycle of GUIs. This paper proposes a model-based testing approach for detecting GUI data contract violations, which may result in serious failures such as system crash. A contract-based model of GUI data specifications is used to develop test scenarios and to serve as test oracle. The technique introduced uses multi terminal binary decision diagrams, which are designed as an integral part of decision table-augmented event sequence graphs, to implement a GUI testing process. A case study, which validates the presented approach on a port scanner written in Java programming language, is presented.

Ordered Binary Decision Diagrams (OBDDs for short) are popular dynamic data structures for Boolean functions. In some modern applications, we have to handle such huge graphs that the usual explicit representations by adjacency lists or adjacency matrices are infeasible. To deal with such huge graphs, OBDD-based graph representations and algorithms have been investigated. Although the size of OBDD representations may be large in general, it is known to be small for some special classes of graphs. In this paper, we show upper bounds and lower bounds of the size of OBDDs representing some intersection graphs such as bipartite permutation graphs, biconvex graphs, convex graphs, (2-directional) orthogonal ray graphs, and permutation graphs.

This paper describes a method for the efficient computation of the total autocorrelation for large multiple-output Boolean functions over a Shared Binary Decision Diagram (SBDD). The existing methods for computing the total autocorrelation over decision diagrams are restricted to single output functions and in the case of multiple-output functions require repeating the procedure k times where k is the number of outputs. The proposed method permits to perform the computation in a single traversal of SBDD. In that order, compared to standard BDD packages, we modified the way of traversing sub-diagrams in SBDD and introduced an additional memory function kept in the hash table for storing results of the computation of the autocorrelation between two subdiagrams in the SBDD. Due to that, the total amount of computations is reduced which makes the method feasible in practical applications. Experimental results over standard benchmarks confirm the efficiency of the method.

This letter describes a design methodology for an arithmetic logic unit (ALU) incorporating reconfigurability based on double-gate carbon nanotube field-effect transistors (DG-CNTFETs). The design of a DG-CNTFET with an ambipolar-property-based reconfigurable static logic circuit is simple and straightforward using an ambipolar binary decision diagram (Am-BDD), which represents the cornerstone for the automatic pass transistor logic (PTL) synthesis flows of ambipolar devices. In this work, an ALU with 16 functions is synthesized by the design methodology of a DG-CNTFET-based reconfigurable static logic circuit. Furthermore, it is shown that the proposed ALU is much more flexible and practical than a conventional DG-CNTFET-based reconfigurable ALU.

This letter describes the design methodology for reduced reconfigurable logic circuits based on double gate carbon nanotube field effect transistors (DG-CNTFETs) with ambipolar propoerty. Ambipolar Binary Decision Diagram (Am-BDD) which represents the cornerstone for automatic pass transistor logic (PTL) synthesis flows of ambipolar devices was utilized to build DG-CNTFET based n-input reconfigurable cells in the conventional approach. The proposed method can reduce the number of ambipolar devices for 2-inputs reconfigurable cells, incorporating the simple Boolean algebra in the Am-BDD compared with the conventional approach. As a result, the static 2-inputs reconfigurable circuit with 16 logic functions can be synthesized by using 8 DG-CNTFETs although the previous design method needed 12 DG-CNTFETs for the same purpose.

This paper proposes a high-speed architecture to realize two-variable numeric functions. It represents the given function as an edge-valued multiple-valued decision diagram (EVMDD), and shows a systematic design method based on the EVMDD. To achieve a design, we characterize a numeric function f by the values of l and p for which f is an l-restricted Mp-monotone increasing function. Here, l is a measure of subfunctions of f and p is a measure of the rate at which f increases with an increase in the dependent variable. For the special case of an EVMDD, the EVBDD, we show an upper bound on the number of nodes needed to realize an l-restricted Mp-monotone increasing function. Experimental results show that all of the two-variable numeric functions considered in this paper can be converted into an l-restricted Mp-monotone increasing function with p=1 or 3. Thus, they can be compactly realized by EVBDDs. Since EVMDDs have shorter paths and smaller memory size than EVBDDs, EVMDDs can produce fast and compact NFGs.

Decision diagrams (DDs) are data structures commonly used for representation of discrete functions with large number of variables. Binary DDs (BDDs) are used for representation and manipulation with Boolean functions. Complexity of a BDD is usually measured by its size, that is defined as the number of non-terminal nodes in the BDD. Minimization of the sizes of DDs is a problem greatly considered in literature and many related algorithms (exact and heuristic) have been proposed. However, there are many functions for which BDDs when minimized are still large and can have even an exponential size in the number of variables. An approach to derive compact decision diagram representations for such functions is transformation of BDDs into Multi-valued DDs (MDDs) and Heterogeneous MDDs (HMDDs). Complexity of MDDs and HMDDs is measured by the cost which is a generalization of the notion of the size by taking into account complexity of nodes in MDDs and HMDDs. This paper presents a method for transformation of BDD into HMDD with minimal cost. The proposed method reduces the time for determination of the type of nodes in HMDDs by introducing a matrix expressing dependency (interconnections) among nodes at different levels. Comparing to other methods for conversion of BDDs into HMDDs, the method reduces the number of traverses of a BDD necessary for collecting enough information to construct an equivalent HMDD. For an experimental verification of its efficiency, the method is applied to construction of HMDDs for some benchmark functions and their arithmetic and Walsh spectra.

A multiple-output function can be represented by a binary decision diagram for characteristic function (BDD_for_CF). This paper presents a method to represent multiple-output incompletely specified functions using BDD_for_CFs. An algorithm to reduce the widths of BDD_for_CFs is presented. This method is useful for decomposition of incompletely specified multiple-output functions. Experimental results for radix converters, adders, a multiplier, and lists of English words show that this method is useful for the synthesis of LUT cascades. An implementation of English words list by LUT cascades and an auxiliary memory is also shown.

Numerical function generators (NFGs) realize arithmetic functions, such as ex,sin(πx), and , in hardware. They are used in applications where high-speed is essential, such as in digital signal or graphics applications. We introduce the edge-valued binary decision diagram (EVBDD) as a means of reducing the delay and memory requirements in NFGs. We also introduce a recursive segmentation algorithm, which divides the domain of the function to be realized into segments, where the given function is realized as a polynomial. This design reduces the size of the multiplier needed and thus reduces delay. It is also shown that an adder can be replaced by a set of 2-input AND gates, further reducing delay. We compare our results to NFGs designed with multi-terminal BDDs (MTBDDs). We show that EVBDDs yield a design that has, on the average, only 39% of the memory and 58% of the delay of NFGs designed using MTBDDs.

We propose a new method of logic synthesis for dual-rail RSFQ (rapid single-flux-quantum) digital circuits. RSFQ circuit technology is one of the strongest candidates for the next generation technology of digital circuits. For representing logic functions, we use a root-shared binary decision diagram (RSBDD) which is a directed acyclic graph constructed from binary decision diagrams. In the method, first we construct an RSBDD from given logic functions, and then reduce the number of nodes in the constructed RSBDD by variable re-ordering. Finally, we synthesize a dual-rail RSFQ circuit from the reduced RSBDD. We have implemented the method and have synthesized benchmark circuits. We have synthesized dual-rail circuits that consist of about 27% fewer logic elements than those synthesized by a Transduction-based method on average.

This paper outlines the method of constructing single-electron logic circuits based on the binary decision diagram (BDD), a graphical representation of digital functions. The circuit consists of many unit devices, BDD devices, cascaded to build the tree of a BDD graph. Each BDD device corresponds to a node of the BDD graph and operates as a two-way switch for the transport of a single electron. Any combinatorial logic can be implemented using BDD circuits. Several subsystems for a single-electron processor have been constructed using semiconductor nano-process technology.

A new moment computation technique for general lumped R(L)C interconnect circuits with multiple resistor loops is proposed. Using the concept of tearing, a lumped R(L)C network can be partitioned into a spanning tree and several resistor links. The contributions of network moments from each tree and the corresponding links can be determined independently. By combining the conventional moment computation algorithms and the reduced ordered binary decision diagram (ROBDD), the proposed method can compute system moments efficiently. Experimental results have demonstrate that the proposed method can indeed obtain accurate moments and is more efficient than the conventional approach.