Archives for 1999

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.