667096
k one-way heads cannot do string-matching
The string-matching problem is defined as follows [6]: Given a character string x, called the pattern, and a character string y, called the text, determine if x is a subword of y. It is well known that the string-matching problem is of great importance in practice, for example, the ``grep'' function in UNIX. Since the invention of the linear-time algorithms of [2, 3, 8], there have been constant efforts to find linear-time algorithms which use less space. See, e.g. [1]. The best theoretical result is in [6], where it was shown that string-matching can be performed by a six-head two-way deterministic finite automaton in linear time. That is, in linear time, such a machine can accept the language
2607374
Information distance
While Kolmogorov complexity is the accepted absolute measure of information content in an individual finite object, a similarly absolute notion is needed for the information distance between two individual objects, for example, two pictures. We give several natural definitions of a universal information metric, based on length of shortest programs for either ordinary computations or reversible (dissipationless) computations. It turns out that these definitions are equivalent up to an additive logarithmic term. We show that the information distance is a universal cognitive similarity distance. We investigate the maximal correlation of the shortest programs involved, the maximal uncorrelation of programs (a generalization of the Slepian–Wolf theorem of classical information theory), and the density properties of the discrete metric spaces induced by the information distances. A related distance measures the amount of nonreversibility of a computation. Using the physical theory of reversible computation, we give an appropriate (universal, antisymmetric, and transitive) measure of the thermodynamic work required to transform one object in another object by the most efficient process. Information distance between individual objects is needed in pattern recognition where one wants to express effective notions of “pattern similarity” or “cognitive similarity” between individual objects and in thermodynamics of computation where one wants to analyze the energy dissipation of a computation from a particular input to a particular output.
43310555
Twist-Rotation Transformations of Binary Trees and Arithmetic Expressions
The paper studies the computational complexity and efficient algorithms for the twist?rotation transformations of binary trees, which is equivalent to the transformation of arithmetic expressions over an associative and commutative binary operation. The main results are (1) a full binary tree with n labeled leaves can be transformed into any other in at most 3nlogn+2n twist and rotation operations, (2) deciding the twist?rotation distance between two binary trees is NP-complete, and (3) the twist?rotation transformation can be approximated with ratio 6logn+4 in polynomial time for full binary trees with n uniquely labeled leaves.
9397376
Inferring a DNA Sequence from Erroneous Copies
Abstract We suggest a novel approach for efficiently reconstructing an original DNA sequence from erroneous copies.
15731393
Fixed topology alignment with recombination
Abstract In this paper, we study a new version of multiple sequence alignment, fixed topology alignment with recombination. We show that it cannot be approximated within any constant ratio unless P=NP. For a restricted version, we show that the problem is MAX-SNP-hard. This implies that there is no PTAS for this version unless P=NP. We also propose approximation algorithms for a special case, where each internal node has at most one recombination child and any two merge paths for different recombination nodes do not share any common node.
871253
Kolmogorov Complexity Arguments in Combinatorics
Abstract The utility of a Kolmogorov complexity method in combinatorial theory is demonstrated by several examples.
979117
The software architecture of a distributed problem-solving environment
This paper describes the functionality and software architecture of a generic problem-solving environment (PSE) for collaborative computational science and engineering. A PSE is designed to provide transparent access to heterogeneous distributed computing resources, and is intended to enhance research productivity by making it easier to construct, run, and analyze the results of computer simulations. Although implementation details are not discussed in depth, the role of software technologies such as CORBA, Java, and XML is outlined. An XML-based component model is presented. The main features of a Visual Component Composition Environment for software development, and an Intelligent Resource Management System for scheduling components, are described. Some prototype implementations of PSE applications are also presented. Copyright 2000 John Wiley & Sons, Ltd.
368077
Approximation of Walrasian equilibrium in single-minded auctions
We consider a social optimization model of pricing scheme in single-minded auctions, in cases where Walrasian equilibrium does not exist. We are interested in the maximization of the ratio, R, of happy bidders over all agents, in a feasible allocation-pricing scheme. We show NP-hardness of the optimization problem, establish lower and upper bounds of R, as well as develop greedy algorithms to approximate the optimal value of R.
14345064
A Wrapper Generator for Wrapping High Performance Legacy Codes as Java/CORBA Components
This paper describes a Wrapper Generator for wrapping high performance legacy codes as Java/CORBA components for use in a distributed component-based problem- solving environment. Using the Wrapper Generator we ave automatically wrapped an MPI-based legacycode as a single CORBA object, and implemented a problem- solving environment for molecular dynamic simulations. Performance comparisons between runs of the CORBA object and the original legacy code on a cluster of workstations and on a parallel computer are also presented.
15017510
Min-Energy Voltage Allocation for Tree-Structured Tasks
We study job scheduling on processors capable of running at variable voltage/speed to minimize energy consumption. Each job in a problem instance is specified by its arrival time and deadline, together with required number of CPU cycles. It is known that the minimum energy schedule for n jobs can be computed in O(n3) time, assuming a convex energy function. We investigate more efficient algorithms for computing the optimal schedule when the job sets have certain special structures. When the time intervals are structured as trees, the minimum energy schedule is shown to have a succinct characterization and is computable in time O(P) where P is the tree’s total path length. We also study an on-line average-rate heuristics AVR and prove that its energy consumption achieves a small constant competitive ratio for nested job sets and for job sets with limited overlap. Some simulation results are also given.
41006390
Min-energy voltage allocation for tree-structured tasks
We study job scheduling on processors capable of running at variable voltage/speed to minimize energy consumption. Each job in a problem instance is specified by its arrival time and deadline, together with required number of CPU cycles. It is known that the minimum energy schedule for n jobs can be computed in O(n3) time, assuming a convex energy function. We investigate more efficient algorithms for computing the optimal schedule when the job sets have certain special structures. When the time intervals are structured as trees, the minimum energy schedule is shown to have a succinct characterization and is computable in time O(P) where P is the tree’s total path length. We also study an on-line average-rate heuristics AVR and prove that its energy consumption achieves a small constant competitive ratio for nested job sets and for job sets with limited overlap. Some simulation results are also given.