Archives for 2000

Today I read a paper titled “Representation Theory for Default Logic”

The abstract is:
Default logic can be regarded as a mechanism to represent families of belief sets of a reasoning agent.

As such, it is inherently second-order.

In this paper, we study the problem of representability of a family of theories as the set of extensions of a default theory.

We give a complete solution to the representability by means of normal default theories.

We obtain partial results on representability by arbitrary default theories.

We construct examples of denumerable families of non-including theories that are not representable.

We also study the concept of equivalence between default theories.

Today I read a paper titled “Bezier Curves Intersection Using Relief Perspective”

The abstract is:
Presented paper describes the method for finding the intersection of class space rational Bezier curves.

The problem curve/curve intersection belongs among basic geometric problems and the aim of this article is to describe the new technique to solve the problem using relief perspective and Bezier clipping..

Today I read a paper titled “Space-Efficient Routing Tables for Almost All Networks and the Incompressibility Method”

The abstract is:
We use the incompressibility method based on Kolmogorov complexity to determine the total number of bits of routing information for almost all network topologies.

In most models for routing, for almost all labeled graphs $\Theta (n^2)$ bits are necessary and sufficient for shortest path routing.

By `almost all graphs’ we mean the Kolmogorov random graphs which constitute a fraction of $1-1/n^c$ of all graphs on $n$ nodes, where $c > 0$ is an arbitrary fixed constant.

There is a model for which the average case lower bound rises to $\Omega(n^2 \log n)$ and another model where the average case upper bound drops to $O(n \log^2 n)$.

This clearly exposes the sensitivity of such bounds to the model under consideration.

If paths have to be short, but need not be shortest (if the stretch factor may be larger than 1), then much less space is needed on average, even in the more demanding models.

Full-information routing requires $\Theta (n^3)$ bits on average.

For worst-case static networks we prove a $\Omega(n^2 \log n)$ lower bound for shortest path routing and all stretch factors $<2$ in some networks where free relabeling is not allowed.

Today I read a paper titled “Parallelization of a Dynamic Monte Carlo Algorithm: a Partially Rejection-Free Conservative Approach”

The abstract is:
We experiment with a massively parallel implementation of an algorithm for simulating the dynamics of metastable decay in kinetic Ising models.

The parallel scheme is directly applicable to a wide range of stochastic cellular automata where the discrete events (updates) are Poisson arrivals.

For high performance, we utilize a continuous-time, asynchronous parallel version of the n-fold way rejection-free algorithm.

Each processing element carries an lxl block of spins, and we employ the fast SHMEM-library routines on the Cray T3E distributed-memory parallel architecture.

Different processing elements have different local simulated times.

To ensure causality, the algorithm handles the asynchrony in a conservative fashion.

Despite relatively low utilization and an intricate relationship between the average time increment and the size of the spin blocks, we find that for sufficiently large l the algorithm outperforms its corresponding parallel Metropolis (non-rejection-free) counterpart.

As an example application, we present results for metastable decay in a model ferromagnetic or ferroelectric film, observed with a probe of area smaller than the total system.

Today I read a paper titled “Natural Language Parsing as Statistical Pattern Recognition”

The abstract is:
Traditional natural language parsers are based on rewrite rule systems developed in an arduous, time-consuming manner by grammarians.

A majority of the grammarian’s efforts are devoted to the disambiguation process, first hypothesizing rules which dictate constituent categories and relationships among words in ambiguous sentences, and then seeking exceptions and corrections to these rules.

In this work, I propose an automatic method for acquiring a statistical parser from a set of parsed sentences which takes advantage of some initial linguistic input, but avoids the pitfalls of the iterative and seemingly endless grammar development process.

Based on distributionally-derived and linguistically-based features of language, this parser acquires a set of statistical decision trees which assign a probability distribution on the space of parse trees given the input sentence.

These decision trees take advantage of significant amount of contextual information, potentially including all of the lexical information in the sentence, to produce highly accurate statistical models of the disambiguation process.

By basing the disambiguation criteria selection on entropy reduction rather than human intuition, this parser development method is able to consider more sentences than a human grammarian can when making individual disambiguation rules.

In experiments between a parser, acquired using this statistical framework, and a grammarian’s rule-based parser, developed over a ten-year period, both using the same training material and test sentences, the decision tree parser significantly outperformed the grammar-based parser on the accuracy measure which the grammarian was trying to maximize, achieving an accuracy of 78% compared to the grammar-based parser’s 69%..

Today I read a paper titled “Reversible Simulation of Irreversible Computation by Pebble Games”

The abstract is:
Reversible simulation of irreversible algorithms is analyzed in the stylized form of a `reversible’ pebble game.

While such simulations incur little overhead in additional computation time, they use a large amount of additional memory space during the computation.

The reacheable reversible simulation instantaneous descriptions (pebble configurations) are characterized completely.

As a corollary we obtain the reversible simulation by Bennett and that among all simulations that can be modelled by the pebble game, Bennett’s simulation is optimal in that it uses the least auxiliary space for the greatest number of simulated steps.

One can reduce the auxiliary storage overhead incurred by the reversible simulation at the cost of allowing limited erasing leading to an irreversibility-space tradeoff.

We show that in this resource-bounded setting the limited erasing needs to be performed at precise instants during the simulation.

We show that the reversible simulation can be modified so that it is applicable also when the simulated computation time is unknown.

Today I read a paper titled “Differential interactive games: The short-term predictions”

The abstract is:
Procedures of the short-term predictions for processes in general 2-person differential interactive games are proposed.

Their effectiveness is discussed.