Local governments usually designed disaster response plan by themselves in order to overcome disasters. In previous research, we developed the effective analysis method for disaster response which is “BFD (Business Flow Diagram)”. In this research, in order to improve effect of BFD analysis, we designed and developed WBS Manager focusing on the process of WBS development which is a part of BFD analysis, because WBS development is fundamental process of BFD method. Especially we developed WBS Manager as web-based application, and implemented it to actual studies at local governments in planning their disaster response operations. In this paper, we introduced the overview of WBS Manager.

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.

A compact composite right/left-handed transmission-line (CRLH TL) stub resonator is presented. The bandpass frequency of the resonator and the adjacent transmission-zeros are determined by the negative order resonance modes of the stub line. We demonstrate that these resonance frequencies can be arbitrarily controlled by using non-identical, unbalanced unit cells, leading to enhanced loaded-Q as well as unloaded-Q. We show that despite the presence of lumped element loss the unloaded-Q is enhanced by a factor of 2 compared to that of microstrip line as a result of nearly-zero group velocity. As a consequence, the loaded-Q can be increased without incurring significant insertion loss as in the case of conventional stub resonators on the same substrate. The physical mechanisms of the distinct features are discussed based on an equivalent dispersion diagram, a concept introduced to model general one-port CRLH TL used as a stub line.

A Decision Diagram Machine (DDM) is a special-purpose processor that has special instructions to evaluate a decision diagram. Since the DDM uses only a limited number of instructions, it is faster than the general-purpose Micro Processor Unit (MPU). Also, the architecture for the DDM is much simpler than that for an MPU. This paper presents a packet classifier using a parallel EVMDD (k) machine. To reduce computation time and code size, first, a set of rules for a packet classifier is partitioned into groups. Then, the parallel EVMDD (k) machine evaluates them. To further speed-up for the standard EVMDD (k) machine, we propose the prefetching EVMDD (k) machine which reads both the index and the jump address at the same time. The prefetching EVMDD (k) machine is 2.4 times faster than the standard one using the same memory size. We implemented a parallel prefetching EVMDD (k) machine consisting of 30 machines on an FPGA, and compared it with the Intel's Core i5 microprocessor running at 1.7GHz. Our parallel machine is 15.1-77.5 times faster than the Core i5, and it requires only 8.1-58.5 percents of the memory for the Core i5.

In the optimization of decision diagrams, variable reordering approaches are often used to minimize the number of nodes. However, such approaches are less effective for analysis of multi-state systems given by monotone structure functions. Thus, in this paper, we propose algorithms to minimize the number of edges in an edge-valued multi-valued decision diagram (EVMDD) for fast analysis of multi-state systems. The proposed algorithms minimize the number of edges by grouping multi-valued variables into larger-valued variables. By grouping multi-valued variables, we can reduce the number of nodes as well. To show the effectiveness of the proposed algorithms, we compare the proposed algorithms with conventional optimization algorithms based on a variable reordering approach. Experimental results show that the proposed algorithms reduce the number of edges by up to 15% and the number of nodes by up to 47%, compared to the conventional ones. This results in a speed-up of the analysis of multi-state systems by about three times.

With the advances in wireless Internet and mobile positioning technology, location-based services (LBSs) have become popular. In LBSs, users must send their exact locations in order to use the services, but they may be subject to several privacy threats. To solve this problem, query processing algorithms based on a cloaking method have been proposed. The algorithms use spatial cloaking methods to blur the user's exact location in a region satisfying the required privacy threshold (k). With the cloaked region, an LBS server can execute a spatial query processing algorithm preserving their privacy. However, the existing algorithms cannot provide good query processing performance. To resolve this problem, we, in this paper, propose a k-NN query processing algorithm based on network Voronoi diagram for spatial networks. Therefore, our algorithm can reduce network expansion overhead and share the information of the expanded road network. In order to demonstrate the efficiency of our algorithms, we have conducted extensive performance evaluations. The results show that our algorithm achieves better performance on retrieval time than the existing algorithms, such as PSNN and kRNN. This is because our k-NN query processing algorithm can greatly reduce a network expansion cost for retrieving k POIs.

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.

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.

Many discrete functions are often compactly represented by Decision Diagrams (DD). The main problem in the construction of decision diagrams is the space and time requirements. While constructing a decision diagram the memory requirement may grow exponentially with the function. Also, large numbers of temporary nodes are created while constructing the decision diagram for a function. Here the problem of reducing the number of temporary nodes is addressed with respect to the PLA specification format of a function, where the function is represented using a set of cubes. Usually a DD is constructed by recursively processing the input cubes in the PLA specification. The DD, representing a sub function, is specified by a single cube. This DD is merged with a master DD, which represents the entire previously processed cubes. Thus the master DD is constructed recursively, until all the cubes in the input cube set are processed. In this paper, an efficient method is proposed, which reorders and also partitions the cube set into unequal number of cubes per subset, in such a way that, the number of temporary nodes created and the number of logical operations done, during the merging of cubes with the master DD are reduced. This results in the reduction of space and time required for the construction of DDs to a remarkable extent.

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.

In wireless sensor networks, energy depletion of bottleneck nodes which have more data packets to relay than others, dominates the network lifetime referred to as the funnel effect problem. To overcome this problem, multiple sink methods have been proposed where sensor nodes send observed data packets toward several sinks to distribute traffic load of bottleneck nodes. If both of the topology and the traffic pattern are symmetric, bottleneck nodes are located near sinks. However, in a general sensor network with an asymmetric topology and/or an asymmetric traffic pattern, bottleneck nodes may exist any place in the network. In this paper, we propose DCAM (DispersiveCast of packets to Avoid bottleneck nodes for Multiple sink sensor network), which is a load balancing method to improve lifetime of a sensor network with an asymmetric topology and an asymmetric traffic pattern. DCAM first finds bottleneck nodes, and then balances the load on the bottleneck nodes. Selected nodes send data packets to several sinks dispersively according to some criteria. The criteria classify DCAM into three variations: DCAM with probability (DCAM-P), DCAM with moving boarder (DCAM-MB), and DCAM with round-robin (DCAM-RR). This paper gives details of the DCAM methods, and thereafter evaluates them with asymmetric topologies and asymmetric traffic patterns. To deal with these dynamic asymmetry, the topology is modeled by a grid network with virtual holes that are defined as vacant places of nodes in the network. Asymmetry of traffic pattern is modeled by defining a hot area where nodes have heavier data traffic than the others. The evaluations are conducted as changing hot-area traffic patterns as well as fixing hot-area patterns. The results show that DCAM improves network lifetime up to 1.87 times longer than the conventional schemes, (i.e., nearest sink transmissions and optimal dispersive cast of packet). We also discuss DCAM on several aspects such as overhead, energy consumption, and applications.

Metamaterials are generally defined as a class of artificial effective media which macroscopically exhibit extraordinary electromagnetic properties that may not be found in nature, and are composed of periodically structured dielectric, or magnetic, or metallic materials. This paper reviews recently developed electromagnetic modeling methods of metamatericals and their inherent basic ideas, with a focus on full wave numerical techniques. Methods described in this paper are the Method of Moments (MoM) and the Finite Difference Time Domain (FDTD) Method for scattering problems excited by an incident plane wave and a single nonperiodic source, and the Finite Element Method (FEM), the Finite Difference Frequency Domain (FDFD) method and the FDTD method for band diagram calculations.

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.

Sequence diagrams are often used in the modular design of softwares. In this paper, we propose a method to verify correctness of sequence diagrams. With this method, using the process algebra CSP, concurrent systems can be synthesized from a number of sequence diagrams. We define new CSP operators for the synthesis of sequence diagrams. We also report on a tool implementing our synthesis method and demonstrate how the tool analyzes sequence diagrams.

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.

During a software development phase where a product is progressively elaborated, it is difficult to guarantee that the refined product retains its original behaviors. In this paper, we propose a method to detect refinement errors in UML sequence diagrams using LTSA (Labeled Transition System Analyzer). The method integrates multiple sequence diagrams using hMSC (high-level Message Sequence Charts) into a sequence diagram. Then, the method translates the diagram into FSP representation, which is the input language of LTSA. The method also supports some combined fragment operators in the UML 2.0 specification. We applied the method to some examples of refined sequence diagrams and checked the correctness of refinement. As a result, we confirmed the method can detect refinement errors in practical time.

Program comprehension using dynamic information is one of key tasks of software maintenance. Software visualization with sequence diagrams is a promising technique to help developer comprehend the behavior of object-oriented systems effectively. There are many tools that can support automatic generation of a sequence diagram from execution traces. However it is still difficult to understand the behavior because the size of automatically generated sequence diagrams from the massive amounts of execution traces tends to be beyond developer's capacity. In this paper, we propose an execution trace slicing and visualization method. Our proposed method is capable of slice calculation based on a behavior model which can treat dependencies based on static and dynamic analysis and supports for various programs including exceptions and multi-threading. We also introduce our tool that perform our proposed slice calculation on the Eclipse platform. We show the applicability of our proposed method by applying the tool to two Java programs as case studies. As a result, we confirm effectiveness of our proposed method for understanding the behavior of object-oriented systems.

Given a collection of k sets consisting of a total of n points in the plane, the distance from any point in the plane to each of the sets is defined to be the minimum among distances to each point in the set. The farthest-color Voronoi diagram is defined as a generalized Voronoi diagram of the k sets with respect to the distance functions for each of the k sets. The combinatorial complexity of the diagram is known to be Θ(kn) in the worst case. This paper initiates a study on farthest-color Voronoi diagrams having O(n) complexity. We introduce a realistic model, which defines a certain class of the diagrams with desirable geometric properties observed. We finally show that the farthest-color Voronoi diagrams under the model have linear complexity.

With exponentially increasing power densities due to technology scaling and ever increasing demand for performance, chip temperature has become an important issue that limits the performance of computer systems. Typically, it is essential to use a set of on-chip thermal sensors to monitor temperatures during the runtime. The runtime thermal measurements are then employed by dynamic thermal management techniques to manage chip performance appropriately. In this paper, we propose an inverse distance weighting method based on a dynamic Voronoi diagram for the reconstruction of full thermal characterization of integrated circuits with non-uniform thermal sensor placements. Firstly we utilize the proposed method to transform the non-uniformly spaced samples to virtual uniformly spaced data. Then we apply three classical interpolation algorithms to reconstruct the full thermal signals in the uniformly spaced samples mode. To evaluate the effectiveness of our method, we develop an experiment for reconstructing full thermal status of a 16-core processor. Experimental results show that the proposed method significantly outperforms spectral analysis techniques, and can obtain full thermal characterization with an average absolute error of 1.72% using 9 thermal sensors per core.