Justin Lloyd's Thinkering

Today I read a paper titled “Look-Back and Look-Ahead in the Conversion of Hidden Markov Models into Finite State Transducers”

The abstract is:
This paper describes the conversion of a Hidden Markov Model into a finite state transducer that closely approximates the behavior of the stochastic model.

In some cases the transducer is equivalent to the HMM.

This conversion is especially advantageous for part-of-speech tagging because the resulting transducer can be composed with other transducers that encode correction rules for the most frequent tagging errors.

The speed of tagging is also improved.

The described methods have been implemented and successfully tested..

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.