The science papers I've read

Today I read a paper titled “Geometric compression for progressive transmission”

The abstract is:
The compression of geometric structures is a relatively new field of data compression.

Since about 1995, several articles have dealt with the coding of meshes, using for most of them the following approach: the vertices of the mesh are coded in an order such that it contains partially the topology of the mesh.

In the same time, some simple rules attempt to predict the position of the current vertex from the positions of its neighbours that have been previously coded.

In this article, we describe a compression algorithm whose principle is completely different: the order of the vertices is used to compress their coordinates, and then the topology of the mesh is reconstructed from the vertices.

This algorithm, particularly suited for terrain models, achieves compression factors that are slightly greater than those of the currently available algorithms, and moreover, it allows progressive and interactive transmission of the meshes..

Today I read a paper titled “Minimum Cuts in Near-Linear Time”

The abstract is:
We significantly improve known time bounds for solving the minimum cut problem on undirected graphs.

We use a “semi-duality” between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling techniques.

We give a randomized algorithm that finds a minimum cut in an m-edge, n-vertex graph with high probability in O(m log^3 n) time.

We also give a simpler randomized algorithm that finds all minimum cuts with high probability in O(n^2 log n) time.

This variant has an optimal RNC parallelization.

Both variants improve on the previous best time bound of O(n^2 log^3 n).

Other applications of the tree-packing approach are new, nearly tight bounds on the number of near minimum cuts a graph may have and a new data structure for representing them in a space-efficient manner.

Today I read a paper titled “Adaptive Multicast of Multi-Layered Video: Rate-Based and Credit-Based Approaches”

The abstract is:
Network architectures that can efficiently transport high quality, multicast video are rapidly becoming a basic requirement of emerging multimedia applications.

The main problem complicating multicast video transport is variation in network bandwidth constraints.

An attractive solution to this problem is to use an adaptive, multi-layered video encoding mechanism.

In this paper, we consider two such mechanisms for the support of video multicast; one is a rate-based mechanism that relies on explicit rate congestion feedback from the network, and the other is a credit-based mechanism that relies on hop-by-hop congestion feedback.

The responsiveness, bandwidth utilization, scalability and fairness of the two mechanisms are evaluated through simulations.

Results suggest that while the two mechanisms exhibit performance trade-offs, both are capable of providing a high quality video service in the presence of varying bandwidth constraints.

Today I read a paper titled “Events in Property Patterns”

The abstract is:
A pattern-based approach to the presentation, codification and reuse of property specifications for finite-state verification was proposed by Dwyer and his collegues.

The patterns enable non-experts to read and write formal specifications for realistic systems and facilitate easy conversion of specifications between formalisms, such as LTL, CTL, QRE.

In this paper, we extend the pattern system with events – changes of values of variables in the context of LTL.

Today I read a paper titled “Towards History-based Grammars: Using Richer Models for Probabilistic Parsing”

The abstract is:
We describe a generative probabilistic model of natural language, which we call HBG, that takes advantage of detailed linguistic information to resolve ambiguity.

HBG incorporates lexical, syntactic, semantic, and structural information from the parse tree into the disambiguation process in a novel way.

We use a corpus of bracketed sentences, called a Treebank, in combination with decision tree building to tease out the relevant aspects of a parse tree that will determine the correct parse of a sentence.

This stands in contrast to the usual approach of further grammar tailoring via the usual linguistic introspection in the hope of generating the correct parse.

In head-to-head tests against one of the best existing robust probabilistic parsing models, which we call P-CFG, the HBG model significantly outperforms P-CFG, increasing the parsing accuracy rate from 60% to 75%, a 37% reduction in error..

Today I read a paper titled “Temporal Relations: Reference or Discourse Coherence?”

The abstract is:
The temporal relations that hold between events described by successive utterances are often left implicit or underspecified.

We address the role of two phenomena with respect to the recovery of these relations: (1) the referential properties of tense, and (2) the role of temporal constraints imposed by coherence relations.

We account for several facets of the identification of temporal relations through an integration of these..

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.

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.

Today I read a paper titled “Priority Union and Generalization in Discourse Grammars”

The abstract is:
We describe an implementation in Carpenter’s typed feature formalism, ALE, of a discourse grammar of the kind proposed by Scha, Polanyi, et al.

We examine their method for resolving parallelism-dependent anaphora and show that there is a coherent feature-structural rendition of this type of grammar which uses the operations of priority union and generalization.

We describe an augmentation of the ALE system to encompass these operations and we show that an appropriate choice of definition for priority union gives the desired multiple output for examples of VP-ellipsis which exhibit a strict/sloppy ambiguity..

Today I read a paper titled “Lifeworld Analysis”

The abstract is:
We argue that the analysis of agent/environment interactions should be extended to include the conventions and invariants maintained by agents throughout their activity.

We refer to this thicker notion of environment as a lifeworld and present a partial set of formal tools for describing structures of lifeworlds and the ways in which they computationally simplify activity.

As one specific example, we apply the tools to the analysis of the Toast system and show how versions of the system with very different control structures in fact implement a common control structure together with different conventions for encoding task state in the positions or states of objects in the environment.

Today I read a paper titled “A Maximum-Entropy Partial Parser for Unrestricted Text”

The abstract is:
This paper describes a partial parser that assigns syntactic structures to sequences of part-of-speech tags.

The program uses the maximum entropy parameter estimation method, which allows a flexible combination of different knowledge sources: the hierarchical structure, parts of speech and phrasal categories.

In effect, the parser goes beyond simple bracketing and recognises even fairly complex structures.

We give accuracy figures for different applications of the parser.

Today I read a paper titled “Similarity-Based Estimation of Word Cooccurrence Probabilities”

The abstract is:
In many applications of natural language processing it is necessary to determine the likelihood of a given word combination.

For example, a speech recognizer may need to determine which of the two word combinations “eat a peach” and “eat a beach” is more likely.

Statistical NLP methods determine the likelihood of a word combination according to its frequency in a training corpus.

However, the nature of language is such that many word combinations are infrequent and do not occur in a given corpus.

In this work we propose a method for estimating the probability of such previously unseen word combinations using available information on “most similar” words.

We describe a probabilistic word association model based on distributional word similarity, and apply it to improving probability estimates for unseen word bigrams in a variant of Katz’s back-off model.

The similarity-based method yields a 20% perplexity improvement in the prediction of unseen bigrams and statistically significant reductions in speech-recognition error..

Today I read a paper titled “Principles and Implementation of Deductive Parsing”

The abstract is:
We present a system for generating parsers based directly on the metaphor of parsing as deduction.

Parsing algorithms can be represented directly as deduction systems, and a single deduction engine can interpret such deduction systems so as to implement the corresponding parser.

The method generalizes easily to parsers for augmented phrase structure formalisms, such as definite-clause grammars and other logic grammar formalisms, and has been used for rapid prototyping of parsing algorithms for a variety of formalisms including variants of tree-adjoining grammars, categorial grammars, and lexicalized context-free grammars..

Today I read a paper titled “Constraint-Based Categorial Grammar”

The abstract is:
We propose a generalization of Categorial Grammar in which lexical categories are defined by means of recursive constraints.

In particular, the introduction of relational constraints allows one to capture the effects of (recursive) lexical rules in a computationally attractive manner.

We illustrate the linguistic merits of the new approach by showing how it accounts for the syntax of Dutch cross-serial dependencies and the position and scope of adjuncts in such constructions.

Delayed evaluation is used to process grammars containing recursive constraints..

Today I read a paper titled “Lessons from a Restricted Turing Test”

The abstract is:
We report on the recent Loebner prize competition inspired by Turing’s test of intelligent behavior.

The presentation covers the structure of the competition and the outcome of its first instantiation in an actual event, and an analysis of the purpose, design, and appropriateness of such a competition.

We argue that the competition has no clear purpose, that its design prevents any useful outcome, and that such a competition is inappropriate given the current level of technology.

We then speculate as to suitable alternatives to the Loebner prize..

Today I read a paper titled “Structural Tags, Annealing and Automatic Word Classification”

The abstract is:
This paper describes an automatic word classification system which uses a locally optimal annealing algorithm and average class mutual information.

A new word-class representation, the structural tag is introduced and its advantages for use in statistical language modelling are presented.

A summary of some results with the one million word LOB corpus is given; the algorithm is also shown to discover the vowel-consonant distinction and displays an ability to cluster words syntactically in a Latin corpus.

Finally, a comparison is made between the current classification system and several leading alternative systems, which shows that the current system performs respectably well..

Today I read a paper titled “A complete anytime algorithm for balanced number partitioning”

The abstract is:
Given a set of numbers, the balanced partioning problem is to divide them into two subsets, so that the sum of the numbers in each subset are as nearly equal as possible, subject to the constraint that the cardinalities of the subsets be within one of each other.

We combine the balanced largest differencing method (BLDM) and Korf’s complete Karmarkar-Karp algorithm to get a new algorithm that optimally solves the balanced partitioning problem.

For numbers with twelve significant digits or less, the algorithm can optimally solve balanced partioning problems of arbitrary size in practice.

For numbers with greater precision, it first returns the BLDM solution, then continues to find better solutions as time allows.

Today I read a paper titled “Lower Bounds for Quantum Search and Derandomization”

The abstract is:
We prove lower bounds on the error probability of a quantum algorithm for searching through an unordered list of N items, as a function of the number T of queries it makes.

In particular, if T=O(sqrt{N}) then the error is lower bounded by a constant.

If we want error <1/2^N then we need T=Omega(N) queries.

We apply this to show that a quantum computer cannot do much better than a classical computer when amplifying the success probability of an RP-machine.

A classical computer can achieve error <=1/2^k using k applications of the RP-machine, a quantum computer still needs at least ck applications for this (when treating the machine as a black-box), where c>0 is a constant independent of k.

Furthermore, we prove a lower bound of Omega(sqrt{log N}/loglog N) queries for quantum bounded-error search of an ordered list of N items.

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.

Today I read a paper titled “Context-free multilanguages”

The abstract is:
This article is a sketch of ideas that were once intended to appear in the author’s famous series, “The Art of Computer Programming”.

He generalizes the notion of a context-free language from a set to a multiset of words over an alphabet.

The idea is to keep track of the number of ways to parse a string.

For example, “fruit flies like a banana” can famously be parsed in two ways; analogous examples in the setting of programming languages may yet be important in the future.

Today I read a paper titled “On Partially Controlled Multi-Agent Systems”

The abstract is:
Motivated by the control theoretic distinction between controllable and uncontrollable events, we distinguish between two types of agents within a multi-agent system: controllable agents, which are directly controlled by the system’s designer, and uncontrollable agents, which are not under the designer’s direct control.

We refer to such systems as partially controlled multi-agent systems, and we investigate how one might influence the behavior of the uncontrolled agents through appropriate design of the controlled agents.

In particular, we wish to understand which problems are naturally described in these terms, what methods can be applied to influence the uncontrollable agents, the effectiveness of such methods, and whether similar methods work across different domains.

Using a game-theoretic framework, this paper studies the design of partially controlled multi-agent systems in two contexts: in one context, the uncontrollable agents are expected utility maximizers, while in the other they are reinforcement learners.

We suggest different techniques for controlling agents’ behavior in each domain, assess their success, and examine their relationship.

Today I read a paper titled “Automatic processing proper names in texts”

The abstract is:
This paper shows first the problems raised by proper names in natural language processing.

Second, it introduces the knowledge representation structure we use based on conceptual graphs.

Then it explains the techniques which are used to process known and unknown proper names.

At last, it gives the performance of the system and the further works we intend to deal with..

Today I read a paper titled “Approximate Graph Coloring by Semidefinite Programming”

The abstract is:
We consider the problem of coloring k-colorable graphs with the fewest possible colors.

We present a randomized polynomial time algorithm that colors a 3-colorable graph on $n$ vertices with min O(Delta^{1/3} log^{1/2} Delta log n), O(n^{1/4} log^{1/2} n) colors where Delta is the maximum degree of any vertex.

Besides giving the best known approximation ratio in terms of n, this marks the first non-trivial approximation result as a function of the maximum degree Delta.

This result can be generalized to k-colorable graphs to obtain a coloring using min O(Delta^{1-2/k} log^{1/2} Delta log n), O(n^{1-3/(k+1)} log^{1/2} n) colors.

Our results are inspired by the recent work of Goemans and Williamson who used an algorithm for semidefinite optimization problems, which generalize linear programs, to obtain improved approximations for the MAX CUT and MAX 2-SAT problems.

An intriguing outcome of our work is a duality relationship established between the value of the optimum solution to our semidefinite program and the Lovasz theta-function.

We show lower bounds on the gap between the optimum solution of our semidefinite program and the actual chromatic number; by duality this also demonstrates interesting new facts about the theta-function.

Today I read a paper titled “Synthesizing Customized Planners from Specifications”

The abstract is:
Existing plan synthesis approaches in artificial intelligence fall into two categories — domain independent and domain dependent.

The domain independent approaches are applicable across a variety of domains, but may not be very efficient in any one given domain.

The domain dependent approaches need to be (re)designed for each domain separately, but can be very efficient in the domain for which they are designed.

One enticing alternative to these approaches is to automatically synthesize domain independent planners given the knowledge about the domain and the theory of planning.

In this paper, we investigate the feasibility of using existing automated software synthesis tools to support such synthesis.

Specifically, we describe an architecture called CLAY in which the Kestrel Interactive Development System (KIDS) is used to derive a domain-customized planner through a semi-automatic combination of a declarative theory of planning, and the declarative control knowledge specific to a given domain, to semi-automatically combine them to derive domain-customized planners.

We discuss what it means to write a declarative theory of planning and control knowledge for KIDS, and illustrate our approach by generating a class of domain-specific planners using state space refinements.

Our experiments show that the synthesized planners can outperform classical refinement planners (implemented as instantiations of UCP, Kambhampati & Srivastava, 1995), using the same control knowledge.

We will contrast the costs and benefits of the synthesis approach with conventional methods for customizing domain independent planners..

Today I read a paper titled “A Quantum Algorithm for Finding the Minimum”

The abstract is:
We give a quantum algorithm to find the index y in a table T of size N such that in time O(c sqrt N), T[y] is minimum with probability at least 1-1/2^c.

Today I read a paper titled “Learning the Past Tense of English Verbs: The Symbolic Pattern Associator vs. Connectionist Models”

The abstract is:
Learning the past tense of English verbs – a seemingly minor aspect of language acquisition – has generated heated debates since 1986, and has become a landmark task for testing the adequacy of cognitive modeling.

Several artificial neural networks (ANNs) have been implemented, and a challenge for better symbolic models has been posed.

In this paper, we present a general-purpose Symbolic Pattern Associator (SPA) based upon the decision-tree learning algorithm ID3.

We conduct extensive head-to-head comparisons on the generalization ability between ANN models and the SPA under different representations.

We conclude that the SPA generalizes the past tense of unseen verbs better than ANN models by a wide margin, and we offer insights as to why this should be the case.

We also discuss a new default strategy for decision-tree learning algorithms..

Today I read a paper titled “Mini-indexes for literate programs”

The abstract is:
This paper describes how to implement a documentation technique that helps readers to understand large programs or collections of programs, by providing local indexes to all identifiers that are visible on every two-page spread.

A detailed example is given for a program that finds all Hamiltonian circuits in an undirected graph..

Today I read a paper titled “Teleo-Reactive Programs for Agent Control”

The abstract is:
A formalism is presented for computing and organizing actions for autonomous agents in dynamic environments.

We introduce the notion of teleo-reactive (T-R) programs whose execution entails the construction of circuitry for the continuous computation of the parameters and conditions on which agent action is based.

In addition to continuous feedback, T-R programs support parameter binding and recursion.

A primary difference between T-R programs and many other circuit-based systems is that the circuitry of T-R programs is more compact; it is constructed at run time and thus does not have to anticipate all the contingencies that might arise over all possible runs.

In addition, T-R programs are intuitive and easy to write and are written in a form that is compatible with automatic planning and learning methods.

We briefly describe some experimental applications of T-R programs in the control of simulated and actual mobile robots..

Today I read a paper titled “Integrative Windowing”

The abstract is:
In this paper we re-investigate windowing for rule learning algorithms.

We show that, contrary to previous results for decision tree learning, windowing can in fact achieve significant run-time gains in noise-free domains and explain the different behavior of rule learning algorithms by the fact that they learn each rule independently.

The main contribution of this paper is integrative windowing, a new type of algorithm that further exploits this property by integrating good rules into the final theory right after they have been discovered.

Thus it avoids re-learning these rules in subsequent iterations of the windowing process.

Experimental evidence in a variety of noise-free domains shows that integrative windowing can in fact achieve substantial run-time gains.

Furthermore, we discuss the problem of noise in windowing and present an algorithm that is able to achieve run-time gains in a set of experiments in a simple domain with artificial noise..

Today I read a paper titled “Dynamic Non-Bayesian Decision Making”

The abstract is:
The model of a non-Bayesian agent who faces a repeated game with incomplete information against Nature is an appropriate tool for modeling general agent-environment interactions.

In such a model the environment state (controlled by Nature) may change arbitrarily, and the feedback/reward function is initially unknown.

The agent is not Bayesian, that is he does not form a prior probability neither on the state selection strategy of Nature, nor on his reward function.

A policy for the agent is a function which assigns an action to every history of observations and actions.

Two basic feedback structures are considered.

In one of them — the perfect monitoring case — the agent is able to observe the previous environment state as part of his feedback, while in the other — the imperfect monitoring case — all that is available to the agent is the reward obtained.

Both of these settings refer to partially observable processes, where the current environment state is unknown.

Our main result refers to the competitive ratio criterion in the perfect monitoring case.

We prove the existence of an efficient stochastic policy that ensures that the competitive ratio is obtained at almost all stages with an arbitrarily high probability, where efficiency is measured in terms of rate of convergence.

It is further shown that such an optimal policy does not exist in the imperfect monitoring case.

Moreover, it is proved that in the perfect monitoring case there does not exist a deterministic policy that satisfies our long run optimality criterion.

In addition, we discuss the maxmin criterion and prove that a deterministic efficient optimal strategy does exist in the imperfect monitoring case under this criterion.

Finally we show that our approach to long-run optimality can be viewed as qualitative, which distinguishes it from previous work in this area.

Today I read a paper titled “Quantum Computing and Phase Transitions in Combinatorial Search”

The abstract is:
We introduce an algorithm for combinatorial search on quantum computers that is capable of significantly concentrating amplitude into solutions for some NP search problems, on average.

This is done by exploiting the same aspects of problem structure as used by classical backtrack methods to avoid unproductive search choices.

This quantum algorithm is much more likely to find solutions than the simple direct use of quantum parallelism.

Furthermore, empirical evaluation on small problems shows this quantum algorithm displays the same phase transition behavior, and at the same location, as seen in many previously studied classical search methods.

Specifically, difficult problem instances are concentrated near the abrupt change from underconstrained to overconstrained problems.

Today I read a paper titled “Flexibly Instructable Agents”

The abstract is:
This paper presents an approach to learning from situated, interactive tutorial instruction within an ongoing agent.

Tutorial instruction is a flexible (and thus powerful) paradigm for teaching tasks because it allows an instructor to communicate whatever types of knowledge an agent might need in whatever situations might arise.

To support this flexibility, however, the agent must be able to learn multiple kinds of knowledge from a broad range of instructional interactions.

Our approach, called situated explanation, achieves such learning through a combination of analytic and inductive techniques.

It combines a form of explanation-based learning that is situated for each instruction with a full suite of contextually guided responses to incomplete explanations.

The approach is implemented in an agent called Instructo-Soar that learns hierarchies of new tasks and other domain knowledge from interactive natural language instructions.

Instructo-Soar meets three key requirements of flexible instructability that distinguish it from previous systems: (1) it can take known or unknown commands at any instruction point; (2) it can handle instructions that apply to either its current situation or to a hypothetical situation specified in language (as in, for instance, conditional instructions); and (3) it can learn, from instructions, each class of knowledge it uses to perform tasks.

Today I read a paper titled “The problem of compatible representatives”

The abstract is:
The purpose of this note is to attach a name to a natural class of combinatorial problems and to point out that this class includes many important special cases.

We also show that a simple problem of placing nonoverlapping labels on a rectangular map is NP-complete..

Today I read a paper titled “Textbook examples of recursion”

The abstract is:
We discuss properties of recursive schemas related to McCarthy’s “91 function” and to Takeuchi’s triple recursion.

Several theorems are proposed as interesting candidates for machine verification, and some intriguing open questions are raised..

Today I read a paper titled “Designing a Theorem Prover”

The abstract is:
A step-by-step presentation of the code for a small theorem prover introduces theorem-proving techniques.

The programming language used is Standard ML.

The prover operates on a sequent calculus formulation of first-order logic, which is briefly explained.

The implementation of unification and logical inference is shown.

The prover is demonstrated on several small examples, including one that shows its limitations.

The final part of the paper is a survey of contemporary research on interactive theorem proving..

Today I read a paper titled “Rule-based Machine Learning Methods for Functional Prediction”

The abstract is:
We describe a machine learning method for predicting the value of a real-valued function, given the values of multiple input variables.

The method induces solutions from samples in the form of ordered disjunctive normal form (DNF) decision rules.

A central objective of the method and representation is the induction of compact, easily interpretable solutions.

This rule-based decision model can be extended to search efficiently for similar cases prior to approximating function values.

Experimental results on real-world data demonstrate that the new techniques are competitive with existing machine learning and statistical methods and can sometimes yield superior regression performance.

Today I read a paper titled “Wee partons in large nuclei: from virtual dream to hard reality”

The abstract is:
We construct a weak coupling, many body theory to compute parton distributions in large nuclei for $x\ll A^{-1/3}$.

The wee partons are highly coherent, non–Abelian Weizs\”{a}cker–Williams fields.

Radiative corrections to the classical results are discussed.

The parton distributions for a single nucleus provide the initial conditions for the dynamical evolution of matter formed in ultrarelativistic nuclear collisions.