OpenRaiser/Intern-Atlas huggingface dataset:
Estimating Genome Reversal Distance by Genetic Algorithm
Venue: arXiv cs.AI 2004
Year: 2004

Sorting by reversals is an important problem in inferring the evolutionary relationship between two genomes. The problem of sorting unsigned permutation has been proven to be NP-hard. The best guaranteed error bounded is the 3/2- approximation algorithm. However, the problem of sorting signed permutation can be solved easily. Fast algorithms have been developed both for finding the sorting sequence and finding the reversal distance of signed permutation. In this paper, we present a way to view the problem of sorting unsigned permutation as signed permutation. And the problem can then be seen as searching an optimal signed permutation in all n2 corresponding signed permutations. We use genetic algorithm to conduct the search. Our experimental result shows that the proposed method outperform the 3/2-approximation algorithm.
A Concurrent Fuzzy-Neural Network Approach for Decision Support Systems
Venue: arXiv cs.AI 2004
Year: 2004

Decision-making is a process of choosing among alternative courses of action for solving complicated problems where multi-criteria objectives are involved. The past few years have witnessed a growing recognition of Soft Computing technologies that underlie the conception, design and utilization of intelligent systems. Several works have been done where engineers and scientists have applied intelligent techniques and heuristics to obtain optimal decisions from imprecise information. In this paper, we present a concurrent fuzzy-neural network approach combining unsupervised and supervised learning techniques to develop the Tactical Air Combat Decision Support System (TACDSS). Experiment results clearly demonstrate the efficiency of the proposed technique.
Evolution of a Subsumption Architecture Neurocontroller
Venue: arXiv cs.AI 2004
Year: 2004

An approach to robotics called layered evolution and merging features from the subsumption architecture into evolutionary robotics is presented, and its advantages are discussed. This approach is used to construct a layered controller for a simulated robot that learns which light source to approach in an environment with obstacles. The evolvability and performance of layered evolution on this task is compared to (standard) monolithic evolution, incremental and modularised evolution. To corroborate the hypothesis that a layered controller performs at least as well as an integrated one, the evolved layers are merged back into a single network. On the grounds of the test results, it is argued that layered evolution provides a superior approach for many tasks, and it is suggested that this approach may be the key to scaling up evolutionary robotics.
EvoNF: A Framework for Optimization of Fuzzy Inference Systems Using Neural Network Learning and Evolutionary Computation
Venue: arXiv cs.AI 2004
Year: 2004

Several adaptation techniques have been investigated to optimize fuzzy inference systems. Neural network learning algorithms have been used to determine the parameters of fuzzy inference system. Such models are often called as integrated neuro-fuzzy models. In an integrated neuro-fuzzy model there is no guarantee that the neural network learning algorithm converges and the tuning of fuzzy inference system will be successful. Success of evolutionary search procedures for optimization of fuzzy inference system is well proven and established in many application areas. In this paper, we will explore how the optimization of fuzzy inference systems could be further improved using a meta-heuristic approach combining neural network learning and evolutionary computation. The proposed technique could be considered as a methodology to integrate neural networks, fuzzy inference systems and evolutionary search procedures. We present the theoretical frameworks and some experimental results to demonstrate the efficiency of the proposed technique.
Single-Strip Triangulation of Manifolds with Arbitrary Topology
Venue: arXiv cs.CG 2004
Year: 2004

Triangle strips have been widely used for efficient rendering. It is NP-complete to test whether a given triangulated model can be represented as a single triangle strip, so many heuristics have been proposed to partition models into few long strips. In this paper, we present a new algorithm for creating a single triangle loop or strip from a triangulated model. Our method applies a dual graph matching algorithm to partition the mesh into cycles, and then merges pairs of cycles by splitting adjacent triangles when necessary. New vertices are introduced at midpoints of edges and the new triangles thus formed are coplanar with their parent triangles, hence the visual fidelity of the geometry is not changed. We prove that the increase in the number of triangles due to this splitting is 50% in the worst case, however for all models we tested the increase was less than 2%. We also prove tight bounds on the number of triangles needed for a single-strip representation of a model with holes on its boundary. Our strips can be used not only for efficient rendering, but also for other applications including the generation of space filling curves on a manifold of any arbitrary topology.
The modulus in the CAD system drawings as a base of developing of the problem-oriented extensions
Venue: arXiv cs.CE 2004
Year: 2004

The concept of the "modulus" in the CAD system drawings is characterized, being a base of developing of the problem-oriented extensions. The modulus consists of visible geometric elements of the drawing and invisible parametric representation of the modelling object. The technological advantages of moduluss in a complex CAD system developing are described.
Interactive visualization of higher dimensional data in a multiview environment
Venue: arXiv cs.GR 2004
Year: 2004

We develop multiple view visualization of higher dimensional data. Our work was chiefly motivated by the need to extract insight from four dimensional Quantum Chromodynamic (QCD) data. We develop visualization where multiple views, generally views of 3D projections or slices of a higher dimensional data, are tightly coupled not only by their specific order but also by a view synchronizing interaction style, and an internally defined interaction language. The tight coupling of the different views allows a fast and well-coordinated exploration of the data. In particular, the visualization allowed us to easily make consistency checks of the 4D QCD data and to infer the correctness of particle properties calculations. The software developed was also successfully applied in material studies, in particular studies of meteorite properties. Our implementation uses the VTK API. To handle a large number of views (slices/projections) and to still maintain good resolution, we use IBM T221 display (3840 X 2400 pixels).
Decision Support Systems Using Intelligent Paradigms
Venue: arXiv cs.AI 2004
Year: 2004

Decision-making is a process of choosing among alternative courses of action for solving complicated problems where multi-criteria objectives are involved. The past few years have witnessed a growing recognition of Soft Computing (SC) technologies that underlie the conception, design and utilization of intelligent systems. In this paper, we present different SC paradigms involving an artificial neural network trained using the scaled conjugate gradient algorithm, two different fuzzy inference methods optimised using neural network learning/evolutionary algorithms and regression trees for developing intelligent decision support systems. We demonstrate the efficiency of the different algorithms by developing a decision support system for a Tactical Air Combat Environment (TACE). Some empirical comparisons between the different algorithms are also provided.
An unexpected application of minimization theory to module decompositions
Venue: arXiv cs.SC 2004
Year: 2004

The aim of this work is to show how we can decompose a module (if decomposable) into an indecomposable module with the help of the minimization process.
Mining Frequent Itemsets from Secondary Memory
Venue: arXiv cs.DB 2004
Year: 2004

Mining frequent itemsets is at the core of mining association rules, and is by now quite well understood algorithmically. However, most algorithms for mining frequent itemsets assume that the main memory is large enough for the data structures used in the mining, and very few efficient algorithms deal with the case when the database is very large or the minimum support is very low. Mining frequent itemsets from a very large database poses new challenges, as astronomical amounts of raw data is ubiquitously being recorded in commerce, science and government. In this paper, we discuss approaches to mining frequent itemsets when data structures are too large to fit in main memory. Several divide-and-conquer algorithms are given for mining from disks. Many novel techniques are introduced. Experimental results show that the techniques reduce the required disk accesses by orders of magnitude, and enable truly scalable data mining.
Advanced exploitation of buffer overflow
Venue: arXiv cs.CR 2004
Year: 2004

This article describes in depth several ways of exploiting buffer overflows in the UNIX operating systems.
Reduction Strategies in Lambda Term Normalization and their Effects on Heap Usage
Venue: arXiv cs.PL 2004
Year: 2004

Higher-order representations of objects such as programs, proofs, formulas and types have become important to many symbolic computation tasks. Systems that support such representations usually depend on the implementation of an intensional view of the terms of some variant of the typed lambda-calculus. Various notations have been proposed for lambda-terms to explicitly treat substitutions as basis for realizing such implementations. There are, however, several choices in the actual reduction strategies. The most common strategy utilizes such notations only implicitly via an incremental use of environments. This approach does not allow the smaller substitution steps to be intermingled with other operations of interest on lambda-terms. However, a naive strategy explicitly using such notations can also be costly: each use of the substitution propagation rules causes the creation of a new structure on the heap that is often discarded in the immediately following step. There is thus a tradeoff between these two approaches. This thesis describes the actual realization of the two approaches, discusses their tradeoffs based on this and, finally, offers an amalgamated approach that utilizes recursion in rewrite rule application but also suspends substitution operations where necessary.
Higher-Order Concurrent Win32 Programming
Venue: arXiv cs.PL 2004
Year: 2004

We present a concurrent framework for Win32 programming based on Concurrent ML, a concurrent language with higher-order functions, static typing, lightweight threads and synchronous communication channels. The key points of the framework are the move from an event loop model to a threaded model for the processing of window messages, and the decoupling of controls notifications from the system messages. This last point allows us to derive a general way of writing controls that leads to easy composition, and can accommodate ActiveX Controls in a transparent way.
A Framework for Interoperability
Venue: arXiv cs.PL 2004
Year: 2004

Practical implementations of high-level languages must provide access to libraries and system services that have APIs specified in a low-level language (usually C). An important characteristic of such mechanisms is the foreign-interface policy that defines how to bridge the semantic gap between the high-level language and C. For example, IDL-based tools generate code to marshal data into and out of the high-level representation according to user annotations. The design space of foreign-interface policies is large and there are pros and cons to each approach. Rather than commit to a particular policy, we choose to focus on the problem of supporting a gamut of interoperability policies. In this paper, we describe a framework for language interoperability that is expressive enough to support very efficient implementations of a wide range of different foreign-interface policies. We describe two tools that implement substantially different policies on top of our framework and present benchmarks that demonstrate their efficiency.
Developing Intellectual Network Management Facilities by Means of Pattern Recognition Theory
Venue: arXiv cs.NI 2004
Year: 2004

In this paper considered question of using pattern recognition methods in network equipment state identification.
Worst-Case Groundness Analysis Using Definite Boolean Functions
Venue: arXiv cs.PL 2004
Year: 2004

This note illustrates theoretical worst-case scenarios for groundness analyses obtained through abstract interpretation over the abstract domains of definite (Def) and positive (Pos) Boolean functions. For Def, an example is given for which any Def-based abstract interpretation for groundness analysis follows a chain which is exponential in the number of argument positions as well as in the number of clauses but sub-exponential in the size of the program. For Pos, we strengthen a previous result by illustrating an example for which any Pos-based abstract interpretation for groundness analysis follows a chain which is exponential in the size of the program. It remains an open problem to determine if the worst case for Def is really as bad as that for Pos.
"User Interfaces" and the Social Negotiation of Availability
Venue: arXiv cs.HC 2004
Year: 2004

In current presence or availability systems, the method of presenting a user's state often supposes an instantaneous notion of that state - for example, a visualization is rendered or an inference is made about the potential actions that might be consistent with a user's state. Drawing on observational research on the use of existing communication technology, we argue (as have others in the past) that determination of availability is often a joint process, and often one that takes the form of a negotiation (whether implicit or explicit). We briefly describe our current research on applying machine learning to infer degrees of conversational engagement from observed conversational behavior. Such inferences can be applied to facilitate the implicit negotiation of conversational engagement - in effect, helping users to weave together the act of contact with the act of determining availability.
Attrition Defenses for a Peer-to-Peer Digital Preservation System
Venue: arXiv cs.CR 2004
Year: 2004

In peer-to-peer systems, attrition attacks include both traditional, network-level denial of service attacks as well as application-level attacks in which malign peers conspire to waste loyal peers' resources. We describe several defenses for LOCKSS, a peer-to-peer digital preservation system, that help ensure that application-level attacks even from powerful adversaries are less effective than simple network-level attacks, and that network-level attacks must be intense, wide-spread, and prolonged to impair the system.
Implementation of Logical Functions in the Game of Life
Venue: arXiv cs.CC 2004
Year: 2004

The Game of Life cellular automaton is a classical example of a massively parallel collision-based computing device. The automaton exhibits mobile patterns, gliders, and generators of the mobile patterns, glider guns, in its evolution. We show how to construct the basic logical operations, AND, OR, NOT in space-time configurations of the cellular automaton. Also decomposition of complicated Boolean functions is discussed. Advantages of our technique are demonstrated on an example of binary adder, realized via collision of glider streams.
Another Proof of an Extension of a Curious Identity
Venue: arXiv cs.DM 2004
Year: 2004

Based on Jensen formulae and the second kind of Chebyshev polynomials, another proof is presented for an extension of a curious binomial identity due to Z. W. Sun and K. J. Wu.
Secure Prolog-Based Mobile Code
Venue: arXiv cs.PL 2004
Year: 2004

LogicWeb mobile code consists of Prolog-like rules embedded in Web pages, thereby adding logic programming behaviour to those pages. Since LogicWeb programs are downloaded from foreign hosts and executed locally, there is a need to protect the client from buggy or malicious code. A security model is crucial for making LogicWeb mobile code safe to execute. This paper presents such a model, which supports programs of varying trust levels by using different resource access policies. The implementation of the model derives from an extended operational semantics for the LogicWeb language, which provides a precise meaning of safety.
Schema-based Scheduling of Event Processors and Buffer Minimization for Queries on Structured Data Streams
Venue: arXiv cs.DB 2004
Year: 2004

We introduce an extension of the XQuery language, FluX, that supports event-based query processing and the conscious handling of main memory buffers. Purely event-based queries of this language can be executed on streaming XML data in a very direct way. We then develop an algorithm that allows to efficiently rewrite XQueries into the event-based FluX language. This algorithm uses order constraints from a DTD to schedule event handlers and to thus minimize the amount of buffering required for evaluating a query. We discuss the various technical aspects of query optimization and query evaluation within our framework. This is complemented with an experimental evaluation of our approach.
Directional Consistency for Continuous Numerical Constraints
Venue: arXiv cs.AI 2004
Year: 2004

Bounds consistency is usually enforced on continuous constraints by first decomposing them into binary and ternary primitives. This decomposition has long been shown to drastically slow down the computation of solutions. To tackle this, Benhamou et al. have introduced an algorithm that avoids formally decomposing constraints. Its better efficiency compared to the former method has already been experimentally demonstrated. It is shown here that their algorithm implements a strategy to enforce on a continuous constraint a consistency akin to Directional Bounds Consistency as introduced by Dechter and Pearl for discrete problems. The algorithm is analyzed in this framework, and compared with algorithms that enforce bounds consistency. These theoretical results are eventually contrasted with new experimental results on standard benchmarks from the interval constraint community.
Alchemistry of the P versus NP question
Venue: arXiv cs.CC 2004
Year: 2004

Are P and NP provably inseparable ? Take a look at some unorthodox, guilty mentioned folklore and related unpublished results.
On Expanders Graphs: Parameters and Applications
Venue: arXiv cs.IT 2004
Year: 2004

We give a new lower bound on the expansion coefficient of an edge-vertex graph of a $d$-regular graph. As a consequence, we obtain an improvement on the lower bound on relative minimum distance of the expander codes constructed by Sipser and Spielman. We also derive some improved results on the vertex expansion of graphs that help us in improving the parameters of the expander codes of Alon, Bruck, Naor, Naor, and Roth.
Stable Outcomes for Two-Sided Contract Choice Problems
Venue: arXiv cs.GT 2004
Year: 2004

We show, that a simple generalization of the Deferred Acceptance Procedure with firms proposing due to Gale and Shapley(1962), yeild outcomes for a two-sided contract choice problem, which necessarily belong to the core and are Weakly Pareto Optimal for firms. Under additional assumptions: (a) given any two distinct workers, the set of yields acheivable by a firm with the first worker is disjoint from the set of yields acheivable by it with the second, and (b) the contract choice problem is pair-wise efficient, we prove that there is no stable outcome at which a firm can get more than what it gets at the unique outcome of our procedure.
Approximation Algorithms for Minimum PCR Primer Set Selection with Amplification Length and Uniqueness Constraints
Venue: arXiv cs.DS 2004
Year: 2004

A critical problem in the emerging high-throughput genotyping protocols is to minimize the number of polymerase chain reaction (PCR) primers required to amplify the single nucleotide polymorphism loci of interest. In this paper we study PCR primer set selection with amplification length and uniqueness constraints from both theoretical and practical perspectives. We give a greedy algorithm that achieves a logarithmic approximation factor for the problem of minimizing the number of primers subject to a given upperbound on the length of PCR amplification products. We also give, using randomized rounding, the first non-trivial approximation algorithm for a version of the problem that requires unique amplification of each amplification target. Empirical results on randomly generated testcases as well as testcases extracted from the from the National Center for Biotechnology Information's genomic databases show that our algorithms are highly scalable and produce better results compared to previous heuristics.
The semijoin algebra and the guarded fragment
Venue: arXiv cs.DB 2004
Year: 2004

The semijoin algebra is the variant of the relational algebra obtained by replacing the join operator by the semijoin operator. We discuss some interesting connections between the semijoin algebra and the guarded fragment of first-order logic. We also provide an Ehrenfeucht-Fraisse game, characterizing the discerning power of the semijoin algebra. This game gives a method for showing that certain queries are not expressible in the semijoin algebra.
Distributed Analysis and Load Balancing System for Grid Enabled Analysis on Hand-held devices using Multi-Agents Systems
Venue: arXiv cs.DC 2004
Year: 2004

Handheld devices, while growing rapidly, are inherently constrained and lack the capability of executing resource hungry applications. This paper presents the design and implementation of distributed analysis and load-balancing system for hand-held devices using multi-agents system. This system enables low resource mobile handheld devices to act as potential clients for Grid enabled applications and analysis environments. We propose a system, in which mobile agents will transport, schedule, execute and return results for heavy computational jobs submitted by handheld devices. Moreover, in this way, our system provides high throughput computing environment for hand-held devices.
Efficient Hashing with Lookups in two Memory Accesses
Venue: arXiv cs.DS 2004
Year: 2004

The study of hashing is closely related to the analysis of balls and bins. It is well-known that instead of using a single hash function if we randomly hash a ball into two bins and place it in the smaller of the two, then this dramatically lowers the maximum load on bins. This leads to the concept of two-way hashing where the largest bucket contains $O(\log\log n)$ balls with high probability. The hash look up will now search in both the buckets an item hashes to. Since an item may be placed in one of two buckets, we could potentially move an item after it has been initially placed to reduce maximum load. with a maximum load of We show that by performing moves during inserts, a maximum load of 2 can be maintained on-line, with high probability, while supporting hash update operations. In fact, with $n$ buckets, even if the space for two items are pre-allocated per bucket, as may be desirable in hardware implementations, more than $n$ items can be stored giving a high memory utilization. We also analyze the trade-off between the number of moves performed during inserts and the maximum load on a bucket. By performing at most $h$ moves, we can maintain a maximum load of $O(\frac{\log \log n}{h \log(\log\log n/h)})$. So, even by performing one move, we achieve a better bound than by performing no moves at all.