For a fixed number of nodes, we focus on directed acyclic graphs in which there is not a shortcut. We find the case where the number of paths is maximized and its corresponding count of maximal paths. Considering this case is essential in solving large-scale scheduling problems using a PERT chart.

A cooperating system of finite automata (CS-FA) has more than one finite automata (FA's) and an input tape. These FA's operate independently on the input tape and can communicate with each other on the same cell of the input tape. For each k ≥ 1, let L[CS-1DFA(k)] (L[CS-1UFA(k)]) be the class of sets accepted by CS-FA's with k one-way deterministic finite automata (alternating finite automata with only universal states). We show that L[CS-1DFA(k+1)] - L[CS-1UFA(k)] ≠ ∅ and L[CS-1UFA(2)] - ∪1≤k<∞L[CS-1DFA(k)] ≠ ∅.

Yield enhancements and quality improvements must be considered as factors of the utmost importance in VLSI (Very Large Scale Integration circuits) manufacturing in order to reduce cost and ensure customer satisfaction. This paper will present a study of the yield theory, an analysis of actual manufacturing data, and the challenges of yield enhancement.

In this paper, the diversity multiplexing tradeoff (DMT) analysis of the non-coherent block-fading multiple antenna channel which uses a training-based channel estimation scheme at asymptotically high signal-to-noise ratios (SNRs) is extended to finite SNRs. This extension is performed for a single input multiple output (SIMO) maximal ratio combining (MRC) scheme. This analysis at finite SNRs is more useful because in practice, the training schemes operate at finite SNRs and their impact on DMT is more relevant at such SNRs. We show the non-applicability of the asymptotically high SNR relation, given by Zheng, to finite SNRs. We also show the equivalence of two existing training-based channel estimation schemes for any SIMO system, and using one of these, we compute the achievable finite-SNR DMT of the non-coherent SIMO-MRC scheme for two modes of the training scheme. We analyze the achievable finite-SNR DMT for different durations of training, modes of the training scheme, and SNRs. We show that the impact of the mode of the training scheme on finite-SNR DMT decreases as SNR increases. We also show that at asymptotically high SNRs, the achievable DMT in both modes of the SIMO-MRC scheme is equal to that of the non-coherent SIMO channel, as derived by Zheng.

To better support data-intensive workflows which are typically built out of various independently developed executables, this paper proposes extensions to parallel database systems called User-Defined eXecutables (UDX) and collective queries. UDX facilitates the description of workflows by enabling seamless integrations of external executables into SQL statements without any efforts to write programs confirming to strict specifications of databases. A collective query is an SQL query whose results are distributed to multiple clients and then processed by them in parallel, using arbitrary UDX. It provides efficient parallelization of executables through the data transfer optimization algorithms that distribute query results to multiple clients, taking both communication cost and computational loads into account. We implement this concept in a system called ParaLite, a parallel database system based on a popular lightweight database SQLite. Our experiments show that ParaLite has several times higher performance over Hive for typical SQL tasks and has 10x speedup compared to a commercial DBMS for executables. In addition, this paper studies a real-world text processing workflow and builds it on top of ParaLite, Hadoop, Hive and general files. Our experiences indicate that ParaLite outperforms other systems in both productivity and performance for the workflow.

In this paper, we study a supervisory control problem for plants and specifications modeled by nondeterministic automata. This problem requires to synthesize a nondeterministic supervisor such that the supervised plant is bisimilar to a given specification. We assume that a supervisor can observe not only the event occurrence but also the current state of the plant, and introduce a notion of completeness of a supervisor which guarantees that all nondeterministic transitions caused by events enabled by the supervisor are defined in the supervised plant. We define a notion of partial bisimulation between a given specification and the plant, and prove that it serves as a necessary and sufficient condition for the existence of a bisimilarity enforcing complete supervisor.

Information-Based Access Control (IBAC) has been proposed as an improvement to History-Based Access Control (HBAC) model. In modern component-based systems, these access control models verify that all the code responsible for a security-sensitive operation is sufficiently authorized to execute that operation. The HBAC model, although safe, may incorrectly prevent the execution of operations that should be executed. The IBAC has been shown to be more precise than HBAC maintaining its safety level while allowing sufficiently authorized operations to be executed. However the verification problem of IBAC program has not been discussed. This paper presents a formal model for IBAC programs based on extended weighted pushdown systems (EWPDS). The mapping process between the IBAC original semantics and the EWPDS structure is described. Moreover, the verification problem for IBAC programs is discussed and several typical IBAC program examples using our model are implemented.

With the development of global navigation satellite systems (GNSS), the interference among global navigation satellite systems, known as the radio frequency compatibility problem, has become a matter of great concern to system providers and user communities. The acceptable compatibility threshold should be determined in the radio frequency compatibility assessment process. However, there is no common standard for the acceptable threshold in the radio frequency compatibility assessment. This paper firstly introduces the comprehensive radio frequency compatibility methodology combining the spectral separation coefficient (SSC) and code tracking spectral sensitivity coefficient (CT_SSC). Then, a method for determination of the acceptable compatibility threshold is proposed. The proposed method considers the receiver processing phase including acquisition, code and carrier tracking and data demodulation. Simulations accounting for the interference effects are carried out at each time step and every place on earth. The simulations mainly consider the signals of GPS, Galileo and BeiDou Navigation Satellite System (BDS) in the L1 band. Results show that all of the sole systems are compatible with other GNSS systems with respect to a special receiver configuration used in the simulations.

A novel real-time solar photovoltaic (SPV) emulator system, based on a systolic array network (SAN), is presented. This architecture follows the piecewise polynomial approximation and parallel computing techniques, and shows its capability to generate high-accuracy I-V, P-V curves, instead of traditional DSP and lookup table-based SPV systems.

Computational fluid dynamics (CFD) is an important tool for designing aircraft components. FaSTAR (Fast Aerodynamics Routines) is one of the most recent CFD packages and has various subroutines. However, its irregular and complicated data structure makes it difficult to execute FaSTAR on parallel machines due to memory access problem. The use of a reconfigurable platform based on field programmable gate arrays (FPGAs) is a promising approach to accelerating memory-bottlenecked applications like FaSTAR. However, even with hardware execution, a large number of pipeline stalls can occur due to read-after-write (RAW) data hazards. Moreover, it is difficult to predict when such stalls will occur because of the unstructured mesh used in FaSTAR. To eliminate this problem, we developed an out-of-order mechanism for permuting the data order so as to prevent RAW hazards. It uses an execution monitor and a wait buffer. The former identifies the state of the computation units, and the latter temporarily stores data to be processed in the computation units. This out-of-order mechanism can be applied to various types of computations with data dependency by changing the number of execution monitors and wait buffers in accordance with the equations used in the target computation. An out-of-order system can be reconfigured by automatic changing of the parameters. Application of the proposed mechanism to five subroutines in FaSTAR showed that its use reduces the number of stalls to less than 1% compared to without the mechanism. In-order execution was speeded up 2.6-fold and software execution was speeded up 2.9-fold using an Intel Core 2 Duo processor with a reasonable amount of overhead.

An integral image is the sum of input image pixel values. It is mainly used to speed up the process of a box filter operation, such as Haar-like features. However, large memory for integral image data can be an obstacle in an embedded environment with limited hardware. Therefore, an efficient method to store the integral image is necessary. In this paper, we propose a memory size reduction method for integral image. The method uses four types image information: an integral image, a row integral image, a column integral image, and an input image. Using this method, integral image memory can be reduced by 42.6% on a 640×480 8-bit gray-scale input image. The same idea can be applied for bigger size images.

The large and complicated safety-critical systems today need to keep changing to accommodate ever-changing objectives and environments. Accordingly, runtime analysis for safe reconfiguration or evaluation is currently a hot topic in the field, whereas information acquisition of external environment is crucial for runtime safety analysis. With the rapid development of web services, mobile networks and ubiquitous computing, abundant realtime information of environment is available on the Internet. To integrate these public information into runtime safety analysis of critical systems, this paper brings forward a framework, which could be implemented with open source and cross platform modules and encouragingly, applicable to various safety-critical systems.

In this paper, we present a high frame rate (HFR) vision system that can automatically control its exposure time by executing brightness histogram-based image processing in real time at a high frame rate. Our aim is to obtain high-quality HFR images for robust image processing of high-speed phenomena even under dynamically changing illumination, such as lamps flickering at 100 Hz, corresponding to an AC power supply at 50 / 60 Hz. Our vision system can simultaneously calculate a 256-bin brightness histogram for an 8-bit gray image of 512×512 pixels at 2000 fps by implementing a brightness histogram calculation circuit module as parallel hardware logic on an FPGA-based high-speed vision platform. Based on the HFR brightness histogram calculation, our method realizes automatic exposure (AE) control of 512×512 images at 2000 fps using our proposed AE algorithm. The proposed AE algorithm can maximize the number of pixels in the effective range of the brightness histogram, thus excluding much darker and brighter pixels, to improve the dynamic range of the captured image without over- and under-exposure. The effectiveness of our HFR system with AE control is evaluated according to experimental results for several scenes with illumination flickering at 100 Hz, which is too fast for the human eye to see.

Demand for wireless communication is increasing significantly, but the frequency resources available for wireless communication are quite limited. Currently, various countries are prompting the use of TV white spaces (TVWS). IEEE 802.11 Working Group (WG) has started a Task Group (TG), namely IEEE 802.11af, to develop an international standard for Wireless local Area Networks (WLANs) in TVWS. In order to increase maximum throughput, a channel aggregation mechanism is introduced in the draft standard. In Japan, ISDB-T based area-one-segment broadcasting system (Area-1seg) which is a digital TV broadcast service in limited areas has been permitted to offer actual TVWS services since April 2012. The operation of the IEEE 802.11af system shall not jeopardize the Area-1seg system due to the common operating frequency band. If the Area-1seg partially overlaps with the IEEE 802.11af in some frequency, the IEEE 802.11af cannot use the channel aggregation mechanism due to a lack of channels. As a result, the throughput of the IEEE 802.11af deteriorates. In this paper, the physical layer of IEEE 802.11af D4.0 is introduced briefly, and a partial subcarrier system for IEEE 802.11af is proposed to efficiently use the TVWS spectrum. The IEEE 802.11af co-exist with the Area-1seg by using null subcarriers. Computer simulation shows up to around 70% throughput gain is achieved with the proposed mechanism.

MapReduce is commonly used as a parallel massive data processing model. When deploying it as a service over the open systems, the computational integrity of the participants is becoming an important issue due to the untrustworthy workers. Current duplication-based solutions can effectively solve non-collusive attacks, yet most of them require a centralized worker to re-compute additional sampled tasks to defend collusive attacks, which makes the worker a bottleneck. In this paper, we try to explore a trusted worker scheduling framework, named VAWS, to detect collusive attackers and assure the integrity of data processing without extra re-computation. Based on the historical results of verification, we construct an Integrity Attestation Graph (IAG) in VAWS to identify malicious mappers and remove them from the framework. To further improve the efficiency of identification, a verification-couple selection method with the IAG guidance is introduced to detect the potential accomplices of the confirmed malicious worker. We have proven the effectiveness of our proposed method on the improvement of system performance in theoretical analysis. Intensive experiments show the accuracy of VAWS is over 97% and the overhead of computation is closed to the ideal value of 2 with the increasing of the number of map tasks in our scheme.

This paper describes an ultrasonic system that estimates the cell quantity of an artificial culture bone, which is effective for appropriate treat with a composite of this material and Bone Marrow Stromal Cells. For this system, we examine two approaches for analyzing the ultrasound waves transmitted through the cultured bone, including stem cells to estimate cell quantity: multiple regression and fuzzy inference. We employ two characteristics from the obtained wave for applying each method. These features are the amplitude and the frequency; the amplitude is measured from the obtained wave, and the frequency is calculated by the cross-spectrum method. The results confirmed that the fuzzy inference method yields the accurate estimates of cell quantity in artificial culture bone. Using this ultrasonic estimation system, the orthopaedic surgeons can choose the composites that contain favorable number of cells before the implantation.

A new type of the affine projection (AP) algorithms which incorporates the sparsity condition of a system is presented. To exploit the sparsity of the system, a weighted l1-norm regularization is imposed on the cost function of the AP algorithm. Minimizing the cost function with a subgradient calculus and choosing two distinct weightings for l1-norm, two stochastic gradient based sparsity regularized AP (SR-AP) algorithms are developed. Experimental results show that the SR-AP algorithms outperform the typical AP counterparts for identifying sparse systems.

The auto-correlation function (ACF) of Binary Offset Carrier (BOC) modulated signals has multiple peaks which raise the problem of ambiguity in acquisition and tracking. In this paper, the ACF is split into several sub-correlation functions (SCFs) through dividing the integration period of ACF into several partials. Then a pseudo correlation function (PCF) is constructed from the SCFs through a combination function to eliminate all side-peaks. The unambiguous tracking method based on the PCF achieves better code phase tracking accuracy than the conventional methods in AWGN environment. It only requires half computation cost of Bump-Jumping (BJ) and nearly quarter of Double-Estimator, although offers slightly less accurate tracking than BJ and Double-Estimator in multi-path environment. Moreover, this method suits all kinds of BOC signals without any auxiliary correlators.

This paper proposes a visualization system for supporting the task of monitoring bug update information. Recent growth of the Web has brought us various kinds of text stream data, such as bulletin board systems (BBS), blogs, and social networking services (SNS). Bug update information managed by bug tracking systems (BTS) is also a kind of text stream data. As such text stream data continuously generates new data, it is difficult for users to watch it all the time. Therefore, the task of monitoring text stream data inevitably involves breaks of monitoring, which would cause users to lose the context of monitoring. In order to support such a monitoring task involving breaks, the proposed system employs several visualization techniques. The dynamic relationship between bugs is visualized with animation, and a function of highlighting updated bugs as well as that of replaying a part of the last monitoring time is also proposed in order to help a user grasping the context of monitoring. The result of experiment with test participants shows that highlighting and replay functions can reduce frequency of checking data and monitoring time.

This letter proposes a novel intrusion tolerant system consisting of several virtual machines (VMs) that refresh the target system periodically and by live migration, which monitors the many features of the VMs to identify and replace exhausted VMs. The proposed scheme provides adequate performance and dependability against denial of service (DoS) attacks. To show its efficiency and security, we conduct experiments on the CSIM20 simulator, which showed 22% improvement in a normal situation and approximately 77.83% improvement in heavy traffic in terms of the response time compared to that reported in the literature. We measure and compare the response time. The result show that the proposed scheme has shorter response time and maintains than other systems and supports services during the heavy traffic.