Archives for 1999

Today I read a paper titled “An Optimal Tabular Parsing Algorithm”

The abstract is:
In this paper we relate a number of parsing algorithms which have been developed in very different areas of parsing theory, and which include deterministic algorithms, tabular algorithms, and a parallel algorithm.

We show that these algorithms are based on the same underlying ideas.

By relating existing ideas, we hope to provide an opportunity to improve some algorithms based on features of others.

A second purpose of this paper is to answer a question which has come up in the area of tabular parsing, namely how to obtain a parsing algorithm with the property that the table will contain as little entries as possible, but without the possibility that two entries represent the same subderivation..

Today I read a paper titled “Exploring the Decision Forest: An Empirical Investigation of Occam’s Razor in Decision Tree Induction”

The abstract is:
We report on a series of experiments in which all decision trees consistent with the training data are constructed.

These experiments were run to gain an understanding of the properties of the set of consistent decision trees and the factors that affect the accuracy of individual trees.

In particular, we investigated the relationship between the size of a decision tree consistent with some training data and the accuracy of the tree on test data.

The experiments were performed on a massively parallel Maspar computer.

The results of the experiments on several artificial and two real world problems indicate that, for many of the problems investigated, smaller consistent decision trees are on average less accurate than the average accuracy of slightly larger trees..

Today I read a paper titled “Separation-Sensitive Collision Detection for Convex Objects”

The abstract is:
We develop a class of new kinetic data structures for collision detection between moving convex polytopes; the performance of these structures is sensitive to the separation of the polytopes during their motion.

For two convex polygons in the plane, let D be the maximum diameter of the polygons, and let s be the minimum distance between them during their motion.

Our separation certificate changes O(log(D/s)) times when the relative motion of the two polygons is a translation along a straight line or convex curve, O(D/s‾‾‾√)for translation along an algebraic trajectory, and O(D/s) for algebraic rigid motion (translation and rotation).

Each certificate update is performed in O(log(D/s)) time.

Variants of these data structures are also shown that exhibit \emph{hysteresis}—after a separation certificate fails, the new certificate cannot fail again until the objects have moved by some constant fraction of their current separation.

We can then bound the number of events by the combinatorial size of a certain cover of the motion path by balls..

Today I read a paper titled “Analogue Quantum Computers for Data Analysis”

The abstract is:
Analogue computers use continuous properties of physical system for modeling.

In the paper is described possibility of modeling by analogue quantum computers for some model of data analysis.

It is analogue associative memory and a formal neural network.

A particularity of the models is combination of continuous internal processes with discrete set of output states.

The modeling of the system by classical analogue computers was offered long times ago, but now it is not very effectively in comparison with modern digital computers.

The application of quantum analogue modelling looks quite possible for modern level of technology and it may be more effective than digital one, because number of element may be about Avogadro number (N=6.0E23)..

Today I read a paper titled “Symmetries and transitions of bounded Turing machines”

The abstract is:
We consider the structures given by repeatedly generalising the definition of finite state automata by symmetry considerations, and constructing analogues of transition monoids at each step.

This approach first gives us non-deterministic automata, then (non-deterministic) two-way automata and bounded Turing machines — that is, Turing machines where the read / write head is unable to move past the end of the input word.

In the case of two-way automata, the transition monoids generalise to endomorphism monoids in compact closed categories.

These use Girard’s resolution formula (from the Geometry of Interaction representation of linear logic) to construct the images of singleton words.

In the case of bounded Turing machines, the transition homomorphism generalises to a monoid homomorphism from the natural numbers to a monoid constructed from the union of endomorphism monoids of a compact closed category, together with an appropriate composition.

These use Girard’s execution formula (also from the Geometry of Interaction representation of linear logic) to construct images of singletons.

Today I read a paper titled “1-way quantum finite automata: strengths, weaknesses and generalizations”

The abstract is:
We study 1-way quantum finite automata (QFAs).

First, we compare them with their classical counterparts.

We show that, if an automaton is required to give the correct answer with a large probability (over 0.98), then the power of 1-way QFAs is equal to the power of 1-way reversible automata.

However, quantum automata giving the correct answer with smaller probabilities are more powerful than reversible automata.

Second, we show that 1-way QFAs can be very space-efficient.

Namely, we construct a 1-way QFA which is exponentially smaller than any equivalent classical (even randomized) finite automaton.

This construction may be useful for design of other space-efficient quantum algorithms.

Third, we consider several generalizations of 1-way QFAs.

Here, our goal is to find a model which is more powerful than 1-way QFAs keeping the quantum part as simple as possible..

Today I read a paper titled “Reversibility and Adiabatic Computation: Trading Time and Space for Energy”

The abstract is:
Future miniaturization and mobilization of computing devices requires energy parsimonious `adiabatic’ computation.

This is contingent on logical reversibility of computation.

An example is the idea of quantum computations which are reversible except for the irreversible observation steps.

We propose to study quantitatively the exchange of computational resources like time and space for irreversibility in computations.

Reversible simulations of irreversible computations are memory intensive.

Such (polynomial time) simulations are analysed here in terms of `reversible’ pebble games.

We show that Bennett’s pebbling strategy uses least additional space for the greatest number of simulated steps.

We derive a trade-off for storage space versus irreversible erasure.

Next we consider reversible computation itself.

An alternative proof is provided for the precise expression of the ultimate irreversibility cost of an otherwise reversible computation without restrictions on time and space use.

A time-irreversibility trade-off hierarchy in the exponential time region is exhibited.

Finally, extreme time-irreversibility trade-offs for reversible computations in the thoroughly unrealistic range of computable versus noncomputable time-bounds are given.

Today I read a paper titled “Adaptive Load Balancing: A Study in Multi-Agent Learning”

The abstract is:
We study the process of multi-agent reinforcement learning in the context of load balancing in a distributed system, without use of either central coordination or explicit communication.

We first define a precise framework in which to study adaptive load balancing, important features of which are its stochastic nature and the purely local information available to individual agents.

Given this framework, we show illuminating results on the interplay between basic adaptive behavior parameters and their effect on system efficiency.

We then investigate the properties of adaptive load balancing in heterogeneous populations, and address the issue of exploration vs.

exploitation in that context.

Finally, we show that naive use of communication may not improve, and might even harm system efficiency.