OpenRaiser/Intern-Atlas huggingface dataset:
Scheduling Dags under Uncertainty
Venue: arXiv cs.DS 2007
Year: 2007

This paper introduces a parallel scheduling problem where a directed acyclic graph modeling $t$ tasks and their dependencies needs to be executed on $n$ unreliable workers. Worker $i$ executes task $j$ correctly with probability $p_{i,j}$. The goal is to find a regimen $Σ$, that dictates how workers get assigned to tasks (possibly in parallel and redundantly) throughout execution, so as to minimize the expected completion time. This fundamental parallel scheduling problem arises in grid computing and project management fields, and has several applications. We show a polynomial time algorithm for the problem restricted to the case when dag width is at most a constant and the number of workers is also at most a constant. These two restrictions may appear to be too severe. However, they are fundamentally required. Specifically, we demonstrate that the problem is NP-hard with constant number of workers when dag width can grow, and is also NP-hard with constant dag width when the number of workers can grow. When both dag width and the number of workers are unconstrained, then the problem is inapproximable within factor less than 5/4, unless P=NP.
RADAR Imaging in the Open field At 300 MHz-3000 MHz Radio Band
Venue: arXiv cs.NI 2007
Year: 2007

With the technological growth of broadband wireless technology like CDMA and UWB, a lots of development efforts towards wireless communication system and Imaging radar system are well justified. Efforts are also being imparted towards a Convergence Technology.. the convergence between a communication and radar technology which will result in ITS (Intelligent Transport System) and other applications. This encourages present authors for this development. They are trying to utilize or converge the communication technologies towards radar and to achieve the Interference free and clutter free quality remote images of targets using DS-UWB wireless technology.
Improvements to the Psi-SSA representation
Venue: arXiv cs.PL 2007
Year: 2007

Modern compiler implementations use the Static Single Assignment representation as a way to efficiently implement optimizing algorithms. However this representation is not well adapted to architectures with a predicated instruction set. The Psi-SSA representation extends the SSA representation such that standard SSA algorithms can be easily adapted to an architecture with a fully predicated instruction set. A new pseudo operation, the Psi operation, is introduced to merge several conditional definitions into a unique definition.
Best insertion algorithm for resource-constrained project scheduling problem
Venue: arXiv cs.DM 2007
Year: 2007

This paper considers heuristics for well known resource-constrained project scheduling problem (RCPSP). First a feasible schedule is constructed using randomized best insertion algorithm. The construction is followed by a local search where a new solution is generated as follows: first we randomly delete m activities from the list, which are then reinserted in the list in consecutive order. At the end of run, the schedule with the minimum makespan is selected. Experimental work shows very good results on standard test instances found in PSPLIB
Fault Classification using Pseudomodal Energies and Neuro-fuzzy modelling
Venue: arXiv cs.AI 2007
Year: 2007

This paper presents a fault classification method which makes use of a Takagi-Sugeno neuro-fuzzy model and Pseudomodal energies calculated from the vibration signals of cylindrical shells. The calculation of Pseudomodal Energies, for the purposes of condition monitoring, has previously been found to be an accurate method of extracting features from vibration signals. This calculation is therefore used to extract features from vibration signals obtained from a diverse population of cylindrical shells. Some of the cylinders in the population have faults in different substructures. The pseudomodal energies calculated from the vibration signals are then used as inputs to a neuro-fuzzy model. A leave-one-out cross-validation process is used to test the performance of the model. It is found that the neuro-fuzzy model is able to classify faults with an accuracy of 91.62%, which is higher than the previously used multilayer perceptron.
Multi-Access MIMO Systems with Finite Rate Channel State Feedback
Venue: arXiv cs.IT 2007
Year: 2007

This paper characterizes the effect of finite rate channel state feedback on the sum rate of a multi-access multiple-input multiple-output (MIMO) system. We propose to control the users jointly, specifically, we first choose the users jointly and then select the corresponding beamforming vectors jointly. To quantify the sum rate, this paper introduces the composite Grassmann manifold and the composite Grassmann matrix. By characterizing the distortion rate function on the composite Grassmann manifold and calculating the logdet function of a random composite Grassmann matrix, a good sum rate approximation is derived. According to the distortion rate function on the composite Grassmann manifold, the loss due to finite beamforming decreases exponentially as the feedback bits on beamforming increases.
Fuzzy and Multilayer Perceptron for Evaluation of HV Bushings
Venue: arXiv cs.AI 2007
Year: 2007

The work proposes the application of fuzzy set theory (FST) to diagnose the condition of high voltage bushings. The diagnosis uses dissolved gas analysis (DGA) data from bushings based on IEC60599 and IEEE C57-104 criteria for oil impregnated paper (OIP) bushings. FST and neural networks are compared in terms of accuracy and computational efficiency. Both FST and NN simulations were able to diagnose the bushings condition with 10% error. By using fuzzy theory, the maintenance department can classify bushings and know the extent of degradation in the component.
Condition Monitoring of HV Bushings in the Presence of Missing Data Using Evolutionary Computing
Venue: arXiv cs.NE 2007
Year: 2007

The work proposes the application of neural networks with particle swarm optimisation (PSO) and genetic algorithms (GA) to compensate for missing data in classifying high voltage bushings. The classification is done using DGA data from 60966 bushings based on IEEEc57.104, IEC599 and IEEE production rates methods for oil impregnated paper (OIP) bushings. PSO and GA were compared in terms of accuracy and computational efficiency. Both GA and PSO simulations were able to estimate missing data values to an average 95% accuracy when only one variable was missing. However PSO rapidly deteriorated to 66% accuracy with two variables missing simultaneously, compared to 84% for GA. The data estimated using GA was found to classify the conditions of bushings than the PSO.
Informatics Carnot Machine
Venue: arXiv cs.IT 2007
Year: 2007

Based on Planck's blackbody equation it is argued that a single mode light pulse, with a large number of photons, carries one entropy unit. Similarly, an empty radiation mode carries no entropy. In this case, the calculated entropy that a coded sequence of light pulses is carrying is simply the Gibbs mixing entropy, which is identical to the logical Shannon information. This approach is supported by a demonstration that information transmission and amplification, by a sequence of light pulses in an optical fiber, is a classic Carnot machine comprising of two isothermals and two adiabatic. Therefore it is concluded that entropy under certain conditions is information.
Computational Intelligence for Condition Monitoring
Venue: arXiv cs.CE 2007
Year: 2007

Condition monitoring techniques are described in this chapter. Two aspects of condition monitoring process are considered: (1) feature extraction; and (2) condition classification. Feature extraction methods described and implemented are fractals, Kurtosis and Mel-frequency Cepstral Coefficients. Classification methods described and implemented are support vector machines (SVM), hidden Markov models (HMM), Gaussian mixture models (GMM) and extension neural networks (ENN). The effectiveness of these features were tested using SVM, HMM, GMM and ENN on condition monitoring of bearings and are found to give good results.
Scanning and Sequential Decision Making for Multi-Dimensional Data - Part II: the Noisy Case
Venue: arXiv cs.IT 2007
Year: 2007

We consider the problem of sequential decision making on random fields corrupted by noise. In this scenario, the decision maker observes a noisy version of the data, yet judged with respect to the clean data. In particular, we first consider the problem of sequentially scanning and filtering noisy random fields. In this case, the sequential filter is given the freedom to choose the path over which it traverses the random field (e.g., noisy image or video sequence), thus it is natural to ask what is the best achievable performance and how sensitive this performance is to the choice of the scan. We formally define the problem of scanning and filtering, derive a bound on the best achievable performance and quantify the excess loss occurring when non-optimal scanners are used, compared to optimal scanning and filtering. We then discuss the problem of sequential scanning and prediction of noisy random fields. This setting is a natural model for applications such as restoration and coding of noisy images. We formally define the problem of scanning and prediction of a noisy multidimensional array and relate the optimal performance to the clean scandictability defined by Merhav and Weissman. Moreover, bounds on the excess loss due to sub-optimal scans are derived, and a universal prediction algorithm is suggested. This paper is the second part of a two-part paper. The first paper dealt with sequential decision making on noiseless data arrays, namely, when the decision maker is judged with respect to the same data array it observes.
A Logic of Reachable Patterns in Linked Data-Structures
Venue: arXiv cs.LO 2007
Year: 2007

We define a new decidable logic for expressing and checking invariants of programs that manipulate dynamically-allocated objects via pointers and destructive pointer updates. The main feature of this logic is the ability to limit the neighborhood of a node that is reachable via a regular expression from a designated node. The logic is closed under boolean operations (entailment, negation) and has a finite model property. The key technical result is the proof of decidability. We show how to express precondition, postconditions, and loop invariants for some interesting programs. It is also possible to express properties such as disjointness of data-structures, and low-level heap mutations. Moreover, our logic can express properties of arbitrary data-structures and of an arbitrary number of pointer fields. The latter provides a way to naturally specify postconditions that relate the fields on entry to a procedure to the fields on exit. Therefore, it is possible to use the logic to automatically prove partial correctness of programs performing low-level heap mutations.
Structural Health Monitoring Using Neural Network Based Vibrational System Identification
Venue: arXiv cs.NE 2007
Year: 2007

Composite fabrication technologies now provide the means for producing high-strength, low-weight panels, plates, spars and other structural components which use embedded fiber optic sensors and piezoelectric transducers. These materials, often referred to as smart structures, make it possible to sense internal characteristics, such as delaminations or structural degradation. In this effort we use neural network based techniques for modeling and analyzing dynamic structural information for recognizing structural defects. This yields an adaptable system which gives a measure of structural integrity for composite structures.
Symbolic Reachability Analysis of Higher-Order Context-Free Processes
Venue: arXiv cs.LO 2007
Year: 2007

We consider the problem of symbolic reachability analysis of higher-order context-free processes. These models are generalizations of the context-free processes (also called BPA processes) where each process manipulates a data structure which can be seen as a nested stack of stacks. Our main result is that, for any higher-order context-free process, the set of all predecessors of a given regular set of configurations is regular and effectively constructible. This result generalizes the analogous result which is known for level 1 context-free processes. We show that this result holds also in the case of backward reachability analysis under a regular constraint on configurations. As a corollary, we obtain a symbolic model checking algorithm for the temporal logic E(U,X) with regular atomic predicates, i.e., the fragment of CTL restricted to the EU and EX modalities.
Optimizing Scrip Systems: Efficiency, Crashes, Hoarders, and Altruists
Venue: arXiv cs.GT 2007
Year: 2007

We discuss the design of efficient scrip systems and develop tools for empirically analyzing them. For those interested in the empirical study of scrip systems, we demonstrate how characteristics of agents in a system can be inferred from the equilibrium distribution of money. From the perspective of a system designer, we examine the effect of the money supply on social welfare and show that social welfare is maximized by increasing the money supply up to the point that the system experiences a ``monetary crash,'' where money is sufficiently devalued that no agent is willing to perform a service. We also examine the implications of the presence of altruists and hoarders on the performance of the system. While a small number of altruists may improve social welfare, too many can also cause the system to experience a monetary crash, which may be bad for social welfare. Hoarders generally decrease social welfare but, surprisingly, they also promote system stability by helping prevent monetary crashes. In addition, we provide new technical tools for analyzing and computing equilibria by showing that our model exhibits strategic complementarities, which implies that there exist equilibria in pure strategies that can be computed efficiently.
The Asymptotic Normalized Linear Complexity of Multisequences
Venue: arXiv cs.IT 2007
Year: 2007

We show that the asymptotic linear complexity of a multisequence a in F_q^\infty that is I := liminf L_a(n)/n and S := limsup L_a(n)/n satisfy the inequalities M/(M+1) <= S <= 1 and M(1-S) <= I <= 1-S/M, if all M sequences have nonzero discrepancy infinitely often, and all pairs (I,S) satisfying these conditions are met by 2^{\aleph_0} multisequences a. This answers an Open Problem by Dai, Imamura, and Yang. Keywords: Linear complexity, multisequence, Battery Discharge Model, isometry.
Temporal Runtime Verification using Monadic Difference Logic
Venue: arXiv cs.LO 2007
Year: 2007

In this paper we present an algorithm for performing runtime verification of a bounded temporal logic over timed runs. The algorithm consists of three elements. First, the bounded temporal formula to be verified is translated into a monadic first-order logic over difference inequalities, which we call monadic difference logic. Second, at each step of the timed run, the monadic difference formula is modified by computing a quotient with the state and time of that step. Third, the resulting formula is checked for being a tautology or being unsatisfiable by a decision procedure for monadic difference logic. We further provide a simple decision procedure for monadic difference logic based on the data structure Difference Decision Diagrams. The algorithm is complete in a very strong sense on a subclass of temporal formulae characterized as homogeneously monadic and it is approximate on other formulae. The approximation comes from the fact that not all unsatisfiable or tautological formulae are recognised at the earliest possible time of the runtime verification. Contrary to existing approaches, the presented algorithms do not work by syntactic rewriting but employ efficient decision structures which make them applicable in real applications within for instance business software.
Dynamic User-Defined Similarity Searching in Semi-Structured Text Retrieval
Venue: arXiv cs.IR 2007
Year: 2007

Modern text retrieval systems often provide a similarity search utility, that allows the user to find efficiently a fixed number k of documents in the data set that are most similar to a given query (here a query is either a simple sequence of keywords or the identifier of a full document found in previous searches that is considered of interest). We consider the case of a textual database made of semi-structured documents. Each field, in turns, is modelled with a specific vector space. The problem is more complex when we also allow each such vector space to have an associated user-defined dynamic weight that influences its contribution to the overall dynamic aggregated and weighted similarity. This dynamic problem has been tackled in a recent paper by Singitham et al. in in VLDB 2004. Their proposed solution, which we take as baseline, is a variant of the cluster-pruning technique that has the potential for scaling to very large corpora of documents, and is far more efficient than the naive exhaustive search. We devise an alternative way of embedding weights in the data structure, coupled with a non-trivial application of a clustering algorithm based on the furthest point first heuristic for the metric k-center problem. The validity of our approach is demonstrated experimentally by showing significant performance improvements over the scheme proposed in Singitham et al. in VLDB 2004. We improve significantly tradeoffs between query time and output quality with respect to the baseline method in Singitham et al. in in VLDB 2004, and also with respect to a novel method by Chierichetti et al. to appear in ACM PODS 2007. We also speed up the pre-processing time by a factor at least thirty.
Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences
Venue: arXiv cs.IT 2007
Year: 2007

The randomness rate of an infinite binary sequence is characterized by the sequence of ratios between the Kolmogorov complexity and the length of the initial segments of the sequence. It is known that there is no uniform effective procedure that transforms one input sequence into another sequence with higher randomness rate. By contrast, we display such a uniform effective procedure having as input two independent sequences with positive but arbitrarily small constant randomness rate. Moreover the transformation is a truth-table reduction and the output has randomness rate arbitrarily close to 1.
A randomized algorithm for the on-line weighted bipartite matching problem
Venue: arXiv cs.DS 2007
Year: 2007

We study the on-line minimum weighted bipartite matching problem in arbitrary metric spaces. Here, $n$ not necessary disjoint points of a metric space $M$ are given, and are to be matched on-line with $n$ points of $M$ revealed one by one. The cost of a matching is the sum of the distances of the matched points, and the goal is to find or approximate its minimum. The competitive ratio of the deterministic problem is known to be $Θ(n)$. It was conjectured that a randomized algorithm may perform better against an oblivious adversary, namely with an expected competitive ratio $Θ(\log n)$. We prove a slightly weaker result by showing a $o(\log^3 n)$ upper bound on the expected competitive ratio. As an application the same upper bound holds for the notoriously hard fire station problem, where $M$ is the real line.
Symmetry Partition Sort
Venue: arXiv cs.DS 2007
Year: 2007

In this paper, we propose a useful replacement for quicksort-style utility functions. The replacement is called Symmetry Partition Sort, which has essentially the same principle as Proportion Extend Sort. The maximal difference between them is that the new algorithm always places already partially sorted inputs (used as a basis for the proportional extension) on both ends when entering the partition routine. This is advantageous to speeding up the partition routine. The library function based on the new algorithm is more attractive than Psort which is a library function introduced in 2004. Its implementation mechanism is simple. The source code is clearer. The speed is faster, with O(n log n) performance guarantee. Both the robustness and adaptivity are better. As a library function, it is competitive.
Multi-Agent Modeling Using Intelligent Agents in the Game of Lerpa
Venue: arXiv cs.MA 2007
Year: 2007

Game theory has many limitations implicit in its application. By utilizing multiagent modeling, it is possible to solve a number of problems that are unsolvable using traditional game theory. In this paper reinforcement learning is applied to neural networks to create intelligent agents
Automatic Detection of Pulmonary Embolism using Computational Intelligence
Venue: arXiv cs.CV 2007
Year: 2007

This article describes the implementation of a system designed to automatically detect the presence of pulmonary embolism in lung scans. These images are firstly segmented, before alignment and feature extraction using PCA. The neural network was trained using the Hybrid Monte Carlo method, resulting in a committee of 250 neural networks and good results are obtained.
Submission of content to a digital object repository using a configurable workflow system
Venue: arXiv cs.DL 2007
Year: 2007

The prototype of a workflow system for the submission of content to a digital object repository is here presented. It is based entirely on open-source standard components and features a service-oriented architecture. The front-end consists of Java Business Process Management (jBPM), Java Server Faces (JSF), and Java Server Pages (JSP). A Fedora Repository and a mySQL data base management system serve as a back-end. The communication between front-end and back-end uses a SOAP minimal binding stub. We describe the design principles and the construction of the prototype and discuss the possibilities and limitations of work ow creation by administrators. The code of the prototype is open-source and can be retrieved in the project escipub at http://sourceforge.net
Interpolant-Based Transition Relation Approximation
Venue: arXiv cs.LO 2007
Year: 2007

In predicate abstraction, exact image computation is problematic, requiring in the worst case an exponential number of calls to a decision procedure. For this reason, software model checkers typically use a weak approximation of the image. This can result in a failure to prove a property, even given an adequate set of predicates. We present an interpolant-based method for strengthening the abstract transition relation in case of such failures. This approach guarantees convergence given an adequate set of predicates, without requiring an exact image computation. We show empirically that the method converges more rapidly than an earlier method based on counterexample analysis.
Multimedia Content Distribution in Hybrid Wireless Networks using Weighted Clustering
Venue: arXiv cs.MM 2007
Year: 2007

Fixed infrastructured networks naturally support centralized approaches for group management and information provisioning. Contrary to infrastructured networks, in multi-hop ad-hoc networks each node acts as a router as well as sender and receiver. Some applications, however, requires hierarchical arrangements that-for practical reasons-has to be done locally and self-organized. An additional challenge is to deal with mobility that causes permanent network partitioning and re-organizations. Technically, these problems can be tackled by providing additional uplinks to a backbone network, which can be used to access resources in the Internet as well as to inter-link multiple ad-hoc network partitions, creating a hybrid wireless network. In this paper, we present a prototypically implemented hybrid wireless network system optimized for multimedia content distribution. To efficiently manage the ad-hoc communicating devices a weighted clustering algorithm is introduced. The proposed localized algorithm deals with mobility, but does not require geographical information or distances.