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.

Manipulation of Boolean functions is one of the most important techniques for implementing of VLSI logic design systems. This paper presents a fast method for generating prime-irredundant covers from Binary Decision Diagrams (BDDs), which are efficient representation of Boolean functions. Prime-irredundant covers are forms in which each cube is a prime implicant and no cube can be eliminated. This new method generates compact cube sets from BDDs directly, in contrast to the conventional cube set reduction algorithms, which commonly manipulate redundant cube sets or truth tables. Our method is based on the idea of a recursive operator, proposed by Morreale. Morreale's algorithm is also based on cube set manipulation. We found that the algorithm can be improved and rearranged to fit BDD operations efficiently. The experimental results demonstrate that our method is efficient in terms of time and space. In practical time, we can generate cube sets consisting of more than 1,000,000 literals from multi-level logic circuits which have never previously been flattened into two-level logics. Our method is more than 10 times faster than ESPRESSO in large-scale examples. It gives quasi-minimum numbers of cubes and literals. This method should find many useful applications in logic design systems.

Binary Decision Diagrams (BDDs) and Shared Binary Decision Diagrams (SBDDs), which are improved BDDs, are useful for implementing VLSI logic design systems. Recently, these representations, which are graph representations of Boolean functions, have become popular because of their efficiency in terms of time and space. The forms of the BDD vary with the order of the input variables though they represent the same function. The size of the graphs greatly depends on the order. The variable ordering algorithm is one of the most important issues in the application of BDDs. In this paper, we consider methods which reduce the graph size by reordering input variables on a given BDD with a certain variable order. We propose the Minimum-Width Method which gives a considerably good order in a practicable time and space. In the method, the order is determined by width of BDDs as a cost function. In addition, we show the effect of combining our method with the local search method, and also describe the improvement using the threshold. Experimental results show that our method can reduce the size of BDDs remarkably for most examples. The method needs no additional information, such as the topological information of the circuit. The results can be a measure for evaluation of other ordering methods.

This paper analyzes a blockchain network forming a directed acyclic graph (DAG), called a DAG-type blockchain, from the viewpoint of graph algorithm theory. To use a DAG-type blockchain, NP-hard graph optimization problems on the DAG are required to be solved. Although various problems for undirected and directed graphs can be efficiently solved by using the notions of graph parameters, these currently known parameters are meaningless for DAGs, which implies that it is hopeless to design efficient algorithms based on the parameters for such problems. In this work, we propose a novel graph parameter for directed graphs called a DAG-pathwidth, which represents the closeness to a directed path. This is an extension of the pathwidth, a well-known graph parameter for undirected graphs. We analyze the features of the DAG-pathwidth and prove that computing the DAG-pathwidth of a DAG (directed graph in general) is NP-complete. Finally, we propose an efficient algorithm for a variant of the maximum k-independent set problem for the DAG-type blockchain when the DAG-pathwidth of the input graph is small.

Logic circuits based on a photonic integrated circuit (PIC) have attracted significant interest due to their ultra-high-speed operation. However, they have a fundamental disadvantage that a large amount of the optical signal power is discarded in the path from the optical source to the optical output, which results in significant power consumption. This optical signal power loss is called a garbage output. To address this issue, this paper considers a circuit design without garbage outputs. Although a method for synthesizing an optical logic circuit without garbage outputs is proposed, this synthesis method can not obtain the optimal solution, such as a circuit with the minimum number of gates. This paper proposes a cross-bar gate logic (CBGL) as a new logic structure for optical logic circuits without garbage outputs, moreover enumerates the CBGLs with the minimum number of gates for all three input logic functions by an exhaustive search. Since the search space is vast, our enumeration algorithm incorporates a technique to prune it efficiently. Experimental results for all three-input logic functions demonstrate that the maximum number of gates required to implement the target function is five. In the best case, the number of gates in enumerated CBGLs is one-half compared to the existing method for optical logic circuits without garbage outputs.

Pattern-avoiding permutations are permutations where none of the subsequences matches the relative order of a given pattern. Pattern-avoiding permutations are related to practical and abstract mathematical problems and can provide simple representations for such problems. For example, some floorplans, which are used for optimizing very-large-scale integration (VLSI) circuit design, can be encoded into pattern-avoiding permutations. The generation of pattern-avoiding permutations is an important topic in efficient VLSI design and mathematical analysis of patten-avoiding permutations. In this paper, we present an algorithm for generating pattern-avoiding permutations, and extend this algorithm beyond classical patterns to generalized patterns with more restrictions. Our approach is based on the data structure πDDs, which can represent a permutation set compactly and has useful set operations. We demonstrate the efficiency of our algorithm by computational experiments.

Minato has proposed canonical representation for polynomial functions using zero-suppressed binary decision diagrams (ZBDDs). In this paper, we extend binary moment diagrams (BMDs) proposed by Bryant and Chen to handle variables with degrees higher than l. The experimental results show that this approach is much more efficient than the previous ZBDDs' approach. The proposed approach is expected to be useful for various problems, in particular, for computer algebra.

Finding Pareto-optimal solutions is a basic approach in multi-objective combinatorial optimization. In this paper, we focus on the 0-1 multi-objective knapsack problem, and present an algorithm to enumerate all its Pareto-optimal solutions, which improves upon the method proposed by Bazgan et al. Our algorithm is based on dynamic programming techniques using an efficient data structure called zero-suppressed binary decision diagram (ZDD), which handles a set of combinations compactly. In our algorithm, we utilize ZDDs for storing all the feasible solutions compactly, and pruning inessential partial solutions as quickly as possible. As an output of the algorithm, we can obtain a useful ZDD indexing all the Pareto-optimal solutions. The results of our experiments show that our algorithm is faster than the previous method for various types of three- and four-objective instances, which are difficult problems to solve.

This paper proposes a formal approach of verifying ubiquitous computing application scenarios. Ubiquitous computing application scenarios assume that there are a lot of devices and physical things with computation and communication capabilities, which are called smart objects, and these are interacted with each other. Each of these interactions among smart objects is called “federation”, and these federations form a ubiquitous computing application scenario. Previously, Yuzuru Tanaka proposed “a proximity-based federation model among smart objects”, which is intended for liberating ubiquitous computing from stereotyped application scenarios. However, there are still challenges to establish the verification method of this model. This paper proposes a verification method of this model through model checking. Model checking is one of the most popular formal verification approach and it is often used in various fields of industry. Model checking is conducted using a Kripke structure which is a formal state transition model. We introduce a context catalytic reaction network (CCRN) to handle this federation model as a formal state transition model. We also give an algorithm to transform a CCRN into a Kripke structure and we conduct a case study of ubiquitous computing scenario verification, using this algorithm and the model checking. Finally, we discuss the advantages of our formal approach by showing the difficulties of our target problem experimentally.

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.

Discrete structure manipulation is a fundamental technique for many problems solved by computers. BDDs/ZDDs have attracted a great deal of attention for twenty years, because those data structures are useful to efficiently manipulate basic discrete structures such as logic functions and sets of combinations. Recently, one of the most interesting research topics related to BDDs/ZDDs is Frontier-based search method, a very efficient algorithm for enumerating and indexing the subsets of a graph to satisfy a given constraint. This work is important because many kinds of practical problems can be efficiently solved by some variations of this algorithm. In this article, we present recent research activity related to BDD and ZDD. We first briefly explain the basic techniques for BDD/ZDD manipulation, and then we present several examples of the state-of-the-art algorithms to show the power of enumeration.

Discrete structures are foundational material for computer science and mathematics, which are related to set theory, symbolic logic, inductive proof, graph theory, combinatorics, probability theory, etc. Many problems solved by computers can be decomposed into discrete structures using simple primitive algebraic operations. It is very important to represent discrete structures compactly and to execute efficiently tasks such as equivalency/validity checking, analysis of models, and optimization. Recently, BDDs (Binary Decision Diagrams) and ZDDs (Zero-suppressed BDDs) have attracted a great deal of attention, because they efficiently represent and manipulate large-scale combinational logic data, which are the basic discrete structures in various fields of application. Although a quarter of a century has passed since Bryant's first idea, there are still a lot of interesting and exciting research topics related to BDD and ZDD. BDD/ZDD is based on in-memory data processing techniques, and it enjoys the advantage of using random access memory. Recent commodity PCs are equipped with gigabytes of main memory, and we can now solve large-scale problems which used to be impossible due to memory shortage. Thus, especially since 2000, the scope of BDD/ZDD methods has increased. This survey paper describes the history of, and recent research activity pertaining to, techniques related to BDD and ZDD.

Several web sites providing disaster-related information failed repeatedly after the Great East Japan Earthquake, due to flash crowds caused by Twitter users. Twitter, which was intensively used for information sharing in the aftermath of the earthquake, relies on URL shorteners like bit.ly to offset its strict limit on message length. In order to mitigate the flash crowds, we examine the current Web usage and find that URL shorteners constitute a layer of indirection; a significant part of Web traffic is guided by them. This implies that flash crowds can be controlled by URL shorteners. We developed a new URL shortener, named rcdn.info, just after the earthquake; rcdn.info redirects users to a replica created on a CoralCDN, if the original site is likely to become overloaded. This surprisingly simple solution worked very well in the emergency. We also conduct a thorough analysis of the request log and present several views that capture user behavior in the emergency from various aspects. Interestingly, the traffic significantly grew up at previously unpopular (i.e., small) sites during the disaster; this traffic shift could lead to the failure of several sites. Finally, we show that rcdn.info has great potential in mitigating such failures. We believe that our experience will help the research community tackle future disasters.

Recently much attention has been paid to quantum circuit design to prepare for the future "quantum computation era." Like the conventional logic synthesis, it should be important to verify and analyze the functionalities of generated quantum circuits. For that purpose, we propose an efficient verification method for quantum circuits under a practical restriction. Thanks to the restriction, we can introduce an efficient verification scheme based on decision diagrams called Decision Diagrams for Matrix Functions (DDMFs). Then, we show analytically the advantages of our approach based on DDMFs over the previous verification techniques. In order to introduce DDMFs, we also introduce new concepts, quantum functions and matrix functions, which may also be interesting and useful on their own for designing quantum circuits.

Recently, there has been a lot of research on solving combinatorial problems using Binary Decision Diagrams (BDDs), which are very efficient representations of Boolean functions. We have already developed a Boolean Expression Manipulator, which calculates and reduces Boolean expressions quickly based on BDD techniques. This greatly aids our works on developing VLSI CAD systems and solving combinatorial problems. Any combinatorial problem can be described in Boolean expressions; however, arithmetic operations, such as addition, subraction, multiplication, equality and inequality, are also used for describing many practical problems. Arithmetic operations provide simple descriptions of problems in many cases. In this paper, we present an arithmetic Boolean expression manipulator (BEM-), based on BDD techniques. BEM- calculates Boolean expressions containing arithmetic operations and then displays the results in various formats. It can solve problems represented by a set of equalities and inequalities, which are dealt with using 0-1 linear programming. We show the efficient data structure based on BDD representation, algorihms for manipulating Boolean expressions with arithmetic operations, and good formats for displaying the results. Finally we present the specification of BEM- and an example of application to the 8-Queens problem. BEM- is customizable to various applicationa. It has good computation performance in terms of the total time for programming and execution. We expect BEM- to be a helpful tool in research and development on digital systems.

In this paper, we propose a novel architecture for large-scale regular expression matching, called dynamically reconfigurable bit-parallel NFA architecture (Dynamic BP-NFA), which allows dynamic loading of regular expressions on-the-fly as well as efficient pattern matching for fast data streams. This is the first dynamically reconfigurable hardware with guaranteed performance for the class of extended patterns, which is a subclass of regular expressions consisting of union of characters and its repeat. This class allows operators such as character classes, gaps, optional characters, and bounded and unbounded repeats of character classes. The key to our architecture is the use of bit-parallel pattern matching approach, in which the information of an input non-deterministic finite automaton (NFA) is first compactly encoded in bit-masks stored in a collection of registers and block RAMs. Then, the NFA is efficiently simulated by a fixed circuitry using bitwise Boolean and arithmetic operations consuming one input character per clock regardless of the actual contents of an input text. Experimental results showed that our hardwares for both string and extended patterns were comparable to previous dynamically reconfigurable hardwares in their performances.