Search

In this paper, several efficient migration and allocation strategies have been compared on the mesh-based multiprocessor systems. The traditional non-preemptive submesh allocation strategies consist of two row boundary (TRB) and two column boundary (TCB). The existing migration mechanisms are online dynamic compaction-four corner (ODC-FC), limited top-down compaction (LTDC), TCB, and the combination of TCB and ODC-FC algorithms. Indeed, the new allocation method is presented in this paper. This mechanism has the benefits of two efficient traditional allocation algorithms. It is the combination of the TCB and TRB allocation methods. Also, in this process the impact of four key metrics on online mapping is considered. The parameters are average task execution time (ATET), average task system utilization (ATSU), average task waiting time (ATWT), and average task response time (ATRT). Using TCB and TRB mechanism with the migration strategies is shown that the new algorithm has better ATET, ATRT, ATWT, and ATSU. It has, respectively, 23.5494, 97.1216, 39.1291, and 4.142% improvements in comparison with the previous mechanisms. [ABSTRACT FROM AUTHOR]

We characterize effect algebras and pseudo effect algebras that can be represented as an interval of the lexicographic product of an antilattice unital po-group ( H, u) with a directed po-group G, both with the Riesz Decomposition Property (RDP). We show that a crucial condition is the existence of a lexicographic normal ideal. Finally, we present a categorical equivalence of the category of ( H, u)-lexicographic pseudo effect algebras having RDP with the category of directed po-groups with RDP. In addition, a weaker form of the ( H, u)-lexicographic pseudo effect algebra is studied. [ABSTRACT FROM AUTHOR]

The efficiency of the k-Nearest Neighbour classifier depends on the size of the training set as well as the level of noise in it. Large datasets with high level of noise lead to less accurate classifiers with high computational cost and storage requirements. The goal of editing is to improve accuracy by improving the quality of the training datasets. To obtain such datasets, editing removes noise and mislabeled data as well as smooths the decision boundaries between the discrete classes. On the other hand, prototype abstraction aims to reduce the computational cost and the storage requirements of classifiers by condensing the training data. This paper proposes an editing algorithm called Editing through Homogeneous Clusters (EHC). Then, it extends the idea by introducing a prototype abstraction algorithm that integrate the EHC mechanism and is capable of creating a small noise-free representative set of the initial training data. This algorithm is called Editing and Reduction through Homogeneous Clusters (ERHC). Both are based on a fast and parameter free iterative execution of k-means clustering that forms homogeneous clusters. Both consider as noise and remove clusters consisting of a single item. In addition, ERHC summarizes the items of the remaining clusters by storing the mean item for each one in the representative set. EHC and ERHC are tested on several datasets. The results show that both run very fast and achieve high accuracy. In addition, ERHC achieves high reduction rates. [ABSTRACT FROM AUTHOR]

We give an account on the authors' experience and results from the software verification competition held at the Formal Methods 2012 conference. Competitions like this are meant to provide a benchmark for verification systems. It consisted of three algorithms which the authors have implemented in Java, specified with the Java Modeling Language, and verified using the KeY system. Building on our solutions, we argue that verification systems which target implementations in real-world programming languages better have powerful abstraction capabilities. Regarding the KeY tool, we explain features which, driven by the competition, have been freshly implemented to accommodate for these demands. [ABSTRACT FROM AUTHOR]

The Dissipative Lozi chaotic map is embedded in the discrete self organising migrating algorithm (DSOMA), as a pseudorandom generator. This novel chaotic based algorithm is applied to the constraint based lot-streaming flowshop scheduling problem. Two new and unique data sets generated using the Lozi and Delayed Logistic maps are used to compare the chaos embedded DSOMA and the generic DSOMA utilising the venerable Mersenne Twister. In total, 100 data sets were tested by these two algorithms, for the idling and the non-idling case. From the obtained results, the chaos variant algorithm is shown to significantly improve the performance of generic DSOMA. [ABSTRACT FROM AUTHOR]

In this paper we investigate the effect of observation quality information (OQI) on the performance of a special class of adaptive networks known as distributed incremental least-mean square (DILMS) algorithm. To this aim we consider two different cases: (1) a homogeneous environment where all the nodes have the same observation noise variance (ONV) and (2) an inhomogeneous environment, where different nodes have different ONVs. In the first case we show that, for the same steady-state error, the DILMS algorithm has faster convergence rate in comparison with a non-cooperative scheme. In the second case, we first show that regardless of what ONVs are, the steady-state curves of mean-square deviation, excess mean-square error and mean square error (MSE) in each node are monotonically increasing functions of step-size parameter. Then, to use the OQI, we reformulate the parameter estimation as a constrained optimization problem with MSE criterion as the cost function and ONVs as the constraints. Using the Robbins-Monro method to solve the resultant problem, a new algorithm (which we call noise-constrained incremental LMS algorithm) is obtained which has faster convergence rate than the existing incremental LMS algorithm. Simulation results are also provided to clarify the performance of proposed algorithm. [ABSTRACT FROM AUTHOR]

A novel method to infer logical relationships between sets is presented. These sets can be any collection of elements, for example astronomical catalogs of celestial objects. The method does not require the contents of the sets to be known explicitly. It combines incomplete knowledge about the relationships between sets to infer a priori unknown relationships. Relationships between sets are represented by sets of Boolean hypercubes. This leads to deductive reasoning by application of logical operators to these sets of hypercubes. A pseudo code for an efficient implementation is described. The method is used in the Astro-WISE information system to infer relationships between catalogs of astronomical objects. These catalogs can be very large and, more importantly, their contents do not have to be available at all times. Science products are stored in Astro-WISE with references to other science products from which they are derived, or their dependencies. This creates a full data lineage that links every science product all the way back to the raw data. Catalogs are created in a way that maximizes knowledge about their relationship with their dependencies. The presented algorithm is used to determine which objects a catalog represents by leveraging this information. [ABSTRACT FROM AUTHOR]

Arrangements of lines and pseudolines are important and appealing objects for research in discrete and computational geometry. We show that there are at most $2^{0.657\> n^{2}}$ simple arrangements of n pseudolines in the plane. This improves on previous work by Knuth who proved an upper bound of $3^{\binom{n}{2}} \cong 2^{0.792\> n^{2}}$ in 1992 and the first author, who obtained $2^{0.697\> n^{2}}$ in 1997. The argument uses surprisingly little geometry. The main ingredient is a lemma that was already central to the argument given by Knuth. [ABSTRACT FROM AUTHOR]

We present a new approach based on anagram hashing to handle globally the lexical variation in large and noisy text collections. Lexical variation addressed by spelling correction systems is primarily typographical variation. This is typically handled in a local fashion: given one particular text string some system of retrieving near-neighbors is applied, where near-neighbors are other text strings that differ from the particular string by a given number of characters. The difference in characters between the original string and one of its retrieved near-neighbors constitutes a particular character confusion. We present a global way of performing this action: for all possible particular character confusions given a particular edit distance, we sequentially identify all the pairs of text strings in the text collection that display a particular confusion. We work on large digitized corpora, which contain lexical variation due to both the OCR process and typographical or typesetting error and show that all these types of variation can be handled equally well in the framework we present. The character confusion-based prototype of Text-Induced Corpus Clean-up ( ticcl) is compared to its focus word-based counterpart and evaluated on 6 years' worth of digitized Dutch Parliamentary documents. The character confusion approach is shown to gain an order of magnitude in speed on its word-based counterpart on large corpora. Insights gained about the useful contribution of global corpus variation statistics are shown to also benefit the more traditional word-based approach to spelling correction. Final tests on a held-out set comprising the 1918 edition of the Dutch daily newspaper 'Het Volk' show that the system is not sensitive to domain variation. [ABSTRACT FROM AUTHOR]

This paper provides development of an RF circuit software tool that automatically generates diagnostic programs for device interface boards. The diagnostic tool utilizes novel techniques to differentiate faulty RF circuits embedded in printed circuit boards. We present RF circuit diagnostic techniques using power sensors and multi-tone dither testing, which we integrated into the diagnostic software tool that we developed. The diagnostic tool provides user-transparent pseudocodes with high fault coverage and significantly decreases time to market. [ABSTRACT FROM AUTHOR]

The cyclic antibandwidth problem is to embed the vertices of a graph G of n vertices on a cycle C such that the minimum distance (measured in the cycle) of adjacent vertices is maximized. Exact results/conjectures for this problem exist in the literature for some standard graphs, such as paths, cycles, two-dimensional meshes, and tori, but no algorithm has been proposed for the general graphs in the literature reviewed by us so far. In this paper, we propose a memetic algorithm for the cyclic antibandwidth problem (MACAB) that can be applied on arbitrary graphs. An important feature of this algorithm is the use of breadth first search generated level structures of a graph to explore a variety of solutions. A novel greedy heuristic is designed which explores these level structures to label the vertices of the graph. The algorithm achieves the exact cyclic antibandwidth of all the standard graphs with known optimal values. Based on our experiments we conjecture the cyclic antibandwidth of three-dimensional meshes, hypercubes, and double stars. Experiments show that results obtained by MACAB are substantially better than those given by genetic algorithm. [ABSTRACT FROM AUTHOR]

The use of highly detailed models is continuously increasing in computer-aided design (CAD) design and computer graphics field as the technology of range scanners advances. Real-time rendering and manipulating applications are also increasing to support applications in various areas such as collaborative design and scientific visualization. Although graphics hardware technology has been improved rapidly, more attributes such as color, material property, texture coordinate, and curvature are added to CAD models, and it becomes a challenge to handle and render such heavy models. Consequently, the models with complex mesh need to be approximated to improve the efficiency of rendering and manipulation and to reduce computation time. A considerable amount of work has been done regarding geometry preservation, but relatively little research has been performed to preserve both geometry and additional attributes. We present a feature sensitive simplification method using curvature color as an additional attribute. We also use curvature color filtering and optimal positioning methods after edge collapse to preserve feature more sensitively. Our method is applied to several models, and the performance is demonstrated by comparing it with other methods. [ABSTRACT FROM AUTHOR]

Abstract  The problem of finding dense structures in a given graph is quite basic in informatics including data mining and data engineering. Clique is a popular model to represent dense structures, and widely used because of its simplicity and ease in handling. Pseudo cliques are natural extension of cliques which are subgraphs obtained by removing small number of edges from cliques. We here define a pseudo clique by a subgraph such that the ratio of the number of its edges compared to that of the clique with the same number of vertices is no less than a given threshold value. In this paper, we address the problem of enumerating all pseudo cliques for a given graph and a threshold value. We first show that it seems to be difficult to obtain polynomial time algorithms using straightforward divide and conquer approaches. Then, we propose a polynomial time, polynomial delay in precise, algorithm based on reverse search. The time complexity for each pseudo clique is O(Δlog |V|+min {Δ 2,|V|+|E|}). Computational experiments show the efficiency of our algorithm for both randomly generated graphs and practical graphs. [ABSTRACT FROM AUTHOR]

Abstract  There has been a long-standing debate concerning how dangerous seismic surveys are with respect to marine life. Marine seismic work today is dominated by airgun technology, where high energy is generated by a release of compressed air into the water. The objective of the “Time coded impulse seismic technique” project is to examine whether a new low energy acoustic source can be used for seismic purposes. If the method turns out to be successful, the low output energy and continuous operation will make the source suitable in environmental sensitive areas. The Low level Acoustic Combustion Source (LACS) is a petrol driven pulsed underwater acoustic source. It operates at a few meters depth, and each shot can be digitally controlled from the surface by a computer located in the mother vessel. A presentation of the recorded LACS signal characteristics, the modulation, the Pseudo Noise coding/decoding principles and field test results, is given. The importance of using an optimized code with fine resolution and of using the near field recording as a correlator sequence is demonstrated. Clear correlation peaks could then be seen from the bottom and sub bottom reflectors. [ABSTRACT FROM AUTHOR]

In an earlier paper, Awerbuch presented an innovative distributed algorithm for solving minimum spanning tree (MST) problems that achieved optimal time and message complexity through the introduction of several advanced features. In this paper, we show that there are some cases where his algorithm can create cycles or fail to achieve optimal time complexity. We then show how to modify the algorithm to avoid these problems, and demonstrate both the correctness and optimality of the revised algorithm. [ABSTRACT FROM AUTHOR]