title:
Automata with Nested Pebbles Capture First-Order Logic with Transitive
  Closure

abstract:
  String languages recognizable in (deterministic) log-space are characterized
either by two-way (deterministic) multi-head automata, or following Immerman,
by first-order logic with (deterministic) transitive closure. Here we elaborate
this result, and match the number of heads to the arity of the transitive
closure. More precisely, first-order logic with k-ary deterministic transitive
closure has the same power as deterministic automata walking on their input
with k heads, additionally using a finite set of nested pebbles. This result is
valid for strings, ordered trees, and in general for families of graphs having
a fixed automaton that can be used to traverse the nodes of each of the graphs
in the family. Other examples of such families are grids, toruses, and
rectangular mazes. For nondeterministic automata, the logic is restricted to
positive occurrences of transitive closure.
  The special case of k=1 for trees, shows that single-head deterministic
tree-walking automata with nested pebbles are characterized by first-order
logic with unary deterministic transitive closure. This refines our earlier
result that placed these automata between first-order and monadic second-order
logic on trees.


title: A Systematic Approach to Web-Application Development

abstract:
  Designing a web-application from a specification involves a series of
well-planned and well executed steps leading to the final product. This often
involves critical changes in design while testing the application, which itself
is slow and cumbersome. Traditional approaches either fully automate the
web-application development process, or let developers write everything from
scratch. Our approach is based on a middle-ground, with precise control on the
workflow and usage of a set of custom-made software tools to automate a
significant part of code generation.


title: Randomized Computations on Large Data Sets: Tight Lower Bounds

abstract:
  We study the randomized version of a computation model (introduced by Grohe,
Koch, and Schweikardt (ICALP'05); Grohe and Schweikardt (PODS'05)) that
restricts random access to external memory and internal memory space.
Essentially, this model can be viewed as a powerful version of a data stream
model that puts no cost on sequential scans of external memory (as other models
for data streams) and, in addition, (like other external memory models, but
unlike streaming models), admits several large external memory devices that can
be read and written to in parallel.
  We obtain tight lower bounds for the decision problems set equality, multiset
equality, and checksort. More precisely, we show that any randomized
one-sided-error bounded Monte Carlo algorithm for these problems must perform
Omega(log N) random accesses to external memory devices, provided that the
internal memory size is at most O(N^(1/4)/log N), where N denotes the size of
the input data.
  From the lower bound on the set equality problem we can infer lower bounds on
the worst case data complexity of query evaluation for the languages XQuery,
XPath, and relational algebra on streaming data. More precisely, we show that
there exist queries in XQuery, XPath, and relational algebra, such that any
(randomized) Las Vegas algorithm that evaluates these queries must perform
Omega(log N) random accesses to external memory devices, provided that the
internal memory size is at most O(N^(1/4)/log N).


title: Remarks on the O(N) Implementation of the Fast Marching Method

abstract:
  The fast marching algorithm computes an approximate solution to the eikonal
equation in O(N log N) time, where the factor log N is due to the
administration of a priority queue. Recently, Yatziv, Bartesaghi and Sapiro
have suggested to use an untidy priority queue, reducing the overall complexity
to O(N) at the price of a small error in the computed solution. In this paper,
we give an explicit estimate of the error introduced, which is based on a
discrete comparison principle. This estimates implies in particular that the
choice of an accuracy level that is independent of the speed function F results
in the complexity bound O(Fmax /Fmin N). A numerical experiment illustrates
this robustness problem for large ratios Fmax /Fmin .


title: Characterization of Search Engine Caches

abstract:
  Search engines provide cached copies of indexed content so users will have
something to "click on" if the remote resource is temporarily or permanently
unavailable. Depending on their proprietary caching strategies, search engines
will purge their indexes and caches of resources that exceed a threshold of
unavailability. Although search engine caches are provided only as an aid to
the interactive user, we are interested in building reliable preservation
services from the aggregate of these limited caching services. But first, we
must understand the contents of search engine caches. In this paper, we have
examined the cached contents of Ask, Google, MSN and Yahoo to profile such
things as overlap between index and cache, size, MIME type and "staleness" of
the cached resources. We also examined the overlap of the various caches with
the holdings of the Internet Archive.


title: The Octagon Abstract Domain

abstract:
  This article presents a new numerical abstract domain for static analysis by
abstract interpretation. It extends a former numerical abstract domain based on
Difference-Bound Matrices and allows us to represent invariants of the form
(+/-x+/-y<=c), where x and y are program variables and c is a real constant. We
focus on giving an efficient representation based on Difference-Bound Matrices
- O(n2) memory cost, where n is the number of variables - and graph-based
algorithms for all common abstract operators - O(n3) time cost. This includes a
normal form algorithm to test equivalence of representation and a widening
operator to compute least fixpoint approximations.


title: Dimension and Relative Frequencies

abstract:
  We show how to calculate the finite-state dimension (equivalently, the
finite-state compressibility) of a saturated sets $X$ consisting of {\em all}
infinite sequences $S$ over a finite alphabet $\Sigma_m$ satisfying some given
condition $P$ on the asymptotic frequencies with which various symbols from
$\Sigma_m$ appear in $S$. When the condition $P$ completely specifies an
empirical probability distribution $\pi$ over $\Sigma_m$, i.e., a limiting
frequency of occurrence for {\em every} symbol in $\Sigma_m$, it has been known
since 1949 that the Hausdorff dimension of $X$ is precisely $\CH(\pi)$, the
Shannon entropy of $\pi$, and the finite-state dimension was proven to have
this same value in 2001.
  The saturated sets were studied by Volkmann and Cajar decades ago. It got
attention again only with the recent developments in multifractal analysis by
Barreira, Saussol, Schmeling, and separately Olsen. However, the powerful
methods they used -- ergodic theory and multifractal analysis -- do not yield a
value for the finite-state (or even computable) dimension in an obvious manner.
  We give a pointwise characterization of finite-state dimensions of saturated
sets. Simultaneously, we also show that their finite-state dimension and strong
dimension coincide with their Hausdorff and packing dimension respectively,
though the techniques we use are completely elementary. Our results
automatically extend to less restrictive effective settings (e.g.,
constructive, computable, and polynomial-time dimensions).


title: A Technical Report On Grid Benchmarking using SEE V.O

abstract:
  Grids include heterogeneous resources, which are based on different hardware
and software architectures or components. In correspondence with this diversity
of the infrastructure, the execution time of any single job, as well as the
total grid performance can both be affected substantially, which can be
demonstrated by measurements. Running a simple benchmarking suite can show this
heterogeneity and give us results about the differences over the grid sites.


title: Social Information Processing in Social News Aggregation

abstract:
  The rise of the social media sites, such as blogs, wikis, Digg and Flickr
among others, underscores the transformation of the Web to a participatory
medium in which users are collaboratively creating, evaluating and distributing
information. The innovations introduced by social media has lead to a new
paradigm for interacting with information, what we call 'social information
processing'. In this paper, we study how social news aggregator Digg exploits
social information processing to solve the problems of document recommendation
and rating. First, we show, by tracking stories over time, that social networks
play an important role in document recommendation. The second contribution of
this paper consists of two mathematical models. The first model describes how
collaborative rating and promotion of stories emerges from the independent
decisions made by many users. The second model describes how a user's
influence, the number of promoted stories and the user's social network,
changes in time. We find qualitative agreement between predictions of the model
and user data gathered from Digg.


title: Plot 94 in ambiance X-Window

abstract:
  <PLOT > is a collection of routines to draw surfaces, contours and so on. In
this work we are presenting a version, that functions over work stations with
the operative system UNIX, that count with the graphic ambiance X-WINDOW with
the tools XLIB and OSF/MOTIF. This implant was realized for the work stations
DEC 5000-200, DEC IPX, and DEC ALFA of the CINVESTAV (Center of Investigation
and Advanced Studies). Also implanted in SILICON GRAPHICS of the CENAC
(National Center of Calculation of the Polytechnic National Institute


title:
Space Program Language (SPL/SQL) for the Relational Approach of the
  Spatial Databases

abstract:
  In this project we are presenting a grammar which unify the design and
development of spatial databases. In order to make it, we combine nominal and
spatial information, the former is represented by the relational model and
latter by a modification of the same model. The modification lets to represent
spatial data structures (as Quadtrees, Octrees, etc.) in a integrated way. This
grammar is important because with it we can create tools to build systems that
combine spatial-nominal characteristics such as Geographical Information
Systems (GIS), Hypermedia Systems, Computed Aided Design Systems (CAD), and so
on


title: Orthogonal Frequency Division Multiplexing: An Overview

abstract:
  Orthogonal Frequency Division Multiplexing (OFDM) is a multi-carrier
modulation scheme that provides efficient bandwidth utilization and robustness
against time dispersive channels. This paper deals with the basic system model
for OFDM based systems and with self-interference, or the corruption of desired
signal by itself in OFDM systems. A simple transceiver based on OFDM modulation
is presented. Important impairments in OFDM systems are mathematically analyzed


title:
Multimodal Meaning Representation for Generic Dialogue Systems
  Architectures

abstract:
  An unified language for the communicative acts between agents is essential
for the design of multi-agents architectures. Whatever the type of interaction
(linguistic, multimodal, including particular aspects such as force feedback),
whatever the type of application (command dialogue, request dialogue, database
querying), the concepts are common and we need a generic meta-model. In order
to tend towards task-independent systems, we need to clarify the modules
parameterization procedures. In this paper, we focus on the characteristics of
a meta-model designed to represent meaning in linguistic and multimodal
applications. This meta-model is called MMIL for MultiModal Interface Language,
and has first been specified in the framework of the IST MIAMM European
project. What we want to test here is how relevant is MMIL for a completely
different context (a different task, a different interaction type, a different
linguistic domain). We detail the exploitation of MMIL in the framework of the
IST OZONE European project, and we draw the conclusions on the role of MMIL in
the parameterization of task-independent dialogue managers.


title:
Comparing BB84 and Authentication-Aided Kak's Three-Stage Quantum
  Protocol

abstract:
  This paper compares the popular quantum key distribution (QKD) protocol BB84
with the more recent Kak's three-stage protocol and the latter is shown to be
more secure. A theoretical representation of an authentication-aided version of
Kak's three-stage protocol is provided that makes it possible to deal with the
man-in-the-middle attack.


title:
Some problems in asymptotic convex geometry and random matrices
  motivated by numerical algorithms

abstract:
  The simplex method in Linear Programming motivates several problems of
asymptotic convex geometry. We discuss some conjectures and known results in
two related directions -- computing the size of projections of high dimensional
polytopes and estimating the norms of random matrices and their inverses.


title: Geographic Routing Around Obstacles in Wireless Sensor Networks

abstract:
  Geographic routing is becoming the protocol of choice for many sensor network
applications. The current state of the art is unsatisfactory: some algorithms
are very efficient, however they require a preliminary planarization of the
communication graph. Planarization induces overhead and is not realistic in
many scenarios. On the otherhand, georouting algorithms which do not rely on
planarization have fairly low success rates and either fail to route messages
around all but the simplest obstacles or have a high topology control overhead
(e.g. contour detection algorithms). To overcome these limitations, we propose
GRIC, the first lightweight and efficient on demand (i.e. all-to-all)
geographic routing algorithm which does not require planarization and has
almost 100% delivery rates (when no obstacles are added). Furthermore, the
excellent behavior of our algorithm is maintained even in the presence of large
convex obstacles. The case of hard concave obstacles is also studied; such
obstacles are hard instances for which performance diminishes.


title: Copula Component Analysis

abstract:
  A framework named Copula Component Analysis (CCA) for blind source separation
is proposed as a generalization of Independent Component Analysis (ICA). It
differs from ICA which assumes independence of sources that the underlying
components may be dependent with certain structure which is represented by
Copula. By incorporating dependency structure, much accurate estimation can be
made in principle in the case that the assumption of independence is
invalidated. A two phrase inference method is introduced for CCA which is based
on the notion of multidimensional ICA.


title: Asynchronous Event-Driven Particle Algorithms

abstract:
  We present, in a unifying way, the main components of three asynchronous
event-driven algorithms for simulating physical systems of interacting
particles. The first example, hard-particle molecular dynamics, is well-known.
We also present a recently-developed diffusion kinetic Monte Carlo algorithm,
as well as a novel stochastic molecular-dynamics algorithm that builds on the
Direct Simulation Monte Carlo. We explain how to effectively combine
asynchronous event-driven with classical time-driven or with synchronous
event-driven handling. Finally, we discuss some promises and challenges for
event-driven simulation of realistic physical systems.


title:
On Approximating Optimal Weighted Lobbying, and Frequency of Correctness
  versus Average-Case Polynomial Time

abstract:
  We investigate issues related to two hard problems related to voting, the
optimal weighted lobbying problem and the winner problem for Dodgson elections.
Regarding the former, Christian et al. [CFRS06] showed that optimal lobbying is
intractable in the sense of parameterized complexity. We provide an efficient
greedy algorithm that achieves a logarithmic approximation ratio for this
problem and even for a more general variant--optimal weighted lobbying. We
prove that essentially no better approximation ratio than ours can be proven
for this greedy algorithm.
  The problem of determining Dodgson winners is known to be complete for
parallel access to NP [HHR97]. Homan and Hemaspaandra [HH06] proposed an
efficient greedy heuristic for finding Dodgson winners with a guaranteed
frequency of success, and their heuristic is a ``frequently self-knowingly
correct algorithm.'' We prove that every distributional problem solvable in
polynomial time on the average with respect to the uniform distribution has a
frequently self-knowingly correct polynomial-time algorithm. Furthermore, we
study some features of probability weight of correctness with respect to
Procaccia and Rosenschein's junta distributions [PR07].


title: Polynomial time algorithm for 3-SAT. Examples of use

abstract:
  The algorithm checks the propositional formulas for patterns of
unsatisfiability.


title:
Constrained Cost-Coupled Stochastic Games with Independent State
  Processes

abstract:
  We consider a non-cooperative constrained stochastic games with N players
with the following special structure. With each player there is an associated
controlled Markov chain. The transition probabilities of the i-th Markov chain
depend only on the state and actions of controller i. The information structure
that we consider is such that each player knows the state of its own MDP and
its own actions. It does not know the states of, and the actions taken by other
players. Finally, each player wishes to minimize a time-average cost function,
and has constraints over other time-avrage cost functions. Both the cost that
is minimized as well as those defining the constraints depend on the state and
actions of all players. We study in this paper the existence of a Nash
equilirium. Examples in power control in wireless communications are given.


title: Approximation Algorithms for Multiprocessor Scheduling under Uncertainty

abstract:
  Motivated by applications in grid computing and project management, we study
multiprocessor scheduling in scenarios where there is uncertainty in the
successful execution of jobs when assigned to processors. We consider the
problem of multiprocessor scheduling under uncertainty, in which we are given n
unit-time jobs and m machines, a directed acyclic graph C giving the
dependencies among the jobs, and for every job j and machine i, the probability
p_{ij} of the successful completion of job j when scheduled on machine i in any
given particular step. The goal of the problem is to find a schedule that
minimizes the expected makespan, that is, the expected completion time of all
the jobs.
  The problem of multiprocessor scheduling under uncertainty was introduced by
Malewicz and was shown to be NP-hard even when all the jobs are independent. In
this paper, we present polynomial-time approximation algorithms for the
problem, for special cases of the dag C. We obtain an O(log(n))-approximation
for the case of independent jobs, an
O(log(m)log(n)log(n+m)/loglog(n+m))-approximation when C is a collection of
disjoint chains, an O(log(m)log^2(n))-approximation when C is a collection of
directed out- or in-trees, and an
O(log(m)log^2(n)log(n+m)/loglog(n+m))-approximation when C is a directed
forest.


title: A Note on Approximate Nearest Neighbor Methods

abstract:
  A number of authors have described randomized algorithms for solving the
epsilon-approximate nearest neighbor problem. In this note I point out that the
epsilon-approximate nearest neighbor property often fails to be a useful
approximation property, since epsilon-approximate solutions fail to satisfy the
necessary preconditions for using nearest neighbors for classification and
related tasks.


title:
Generation of Efficient Codes for Realizing Boolean Functions in
  Nanotechnologies

abstract:
  We address the challenge of implementing reliable computation of Boolean
functions in future nanocircuit fabrics. Such fabrics are projected to have
very high defect rates. We overcome this limitation by using a combination of
cheap but unreliable nanodevices and reliable but expensive CMOS devices. In
our approach, defect tolerance is achieved through a novel coding of Boolean
functions; specifically, we exploit the dont cares of Boolean functions
encountered in multi-level Boolean logic networks for constructing better
codes. We show that compared to direct application of existing coding
techniques, the coding overhead in terms of extra bits can be reduced, on
average by 23%, and savings can go up to 34%. We demonstrate that by
incorporating efficient coding techniques more than a 40% average yield
improvement is possible in case of 1% and 0.1% defect rates. With 0.1% defect
density, the savings can be up to 90%.


title: Concept of a Value in Multilevel Security Databases

abstract: This paper has been withdrawn.


title:
Encoding via Gr\"obner bases and discrete Fourier transforms for several
  types of algebraic codes

abstract:
  We propose a novel encoding scheme for algebraic codes such as codes on
algebraic curves, multidimensional cyclic codes, and hyperbolic cascaded
Reed-Solomon codes and present numerical examples. We employ the recurrence
from the Gr\"obner basis of the locator ideal for a set of rational points and
the two-dimensional inverse discrete Fourier transform. We generalize the
functioning of the generator polynomial for Reed-Solomon codes and develop
systematic encoding for various algebraic codes.


title: New List Decoding Algorithms for Reed-Solomon and BCH Codes

abstract:
  In this paper we devise a rational curve fitting algorithm and apply it to
the list decoding of Reed-Solomon and BCH codes. The proposed list decoding
algorithms exhibit the following significant properties. 1 The algorithm
corrects up to $n(1-\sqrt{1-D})$ errors for a (generalized) $(n, k, d=n-k+1)$
Reed-Solomon code, which matches the Johnson bound, where $D\eqdef \frac{d}{n}$
denotes the normalized minimum distance. In comparison with the Guruswami-Sudan
algorithm, which exhibits the same list correction capability, the former
requires multiplicity, which dictates the algorithmic complexity,
$O(n(1-\sqrt{1-D}))$, whereas the latter requires multiplicity $O(n^2(1-D))$.
With the up-to-date most efficient implementation, the former has complexity
$O(n^{6}(1-\sqrt{1-D})^{7/2})$, whereas the latter has complexity
$O(n^{10}(1-D)^4)$. 2. With the multiplicity set to one, the derivative list
correction capability precisely sits in between the conventional hard-decision
decoding and the optimal list decoding. Moreover, the number of candidate
codewords is upper bounded by a constant for a fixed code rate and thus, the
derivative algorithm exhibits quadratic complexity $O(n^2)$. 3. By utilizing
the unique properties of the Berlekamp algorithm, the algorithm corrects up to
$\frac{n}{2}(1-\sqrt{1-2D})$ errors for a narrow-sense $(n, k, d)$ binary BCH
code, which matches the Johnson bound for binary codes. The algorithmic
complexity is $O(n^{6}(1-\sqrt{1-2D})^7)$.


title:
Practical Identity-Based Encryption (IBE) in Multiple PKG Environments
  and Its Applications

abstract:
  In this paper, we present a new identity-based encryption (IBE) scheme using
bilinear pairings. Our IBE scheme enjoys the same \textsf{Key Extraction} and
\textsf{Decryption} algorithms with the famous IBE scheme of Boneh and Franklin
(BF-IBE for short), while differs from the latter in that it has modified
\textsf{Setup} and \textsf{Encryption} algorithms.
  Compared with BF-IBE, we show that ours are more practical in a multiple
private key generator (PKG) environment, mainly due to that the session secret
$g_{ID}$ could be pre-computed \emph{before} any interaction, and the sender
could encrypt a message using $g_{ID}$ prior to negotiating with the intended
recipient(s). As an application of our IBE scheme, we also derive an escrowed
ElGamal scheme which possesses certain good properties in practice.


title: Clustering and Sharing Incentives in BitTorrent Systems

abstract:
  Peer-to-peer protocols play an increasingly instrumental role in Internet
content distribution. It is therefore important to gain a complete
understanding of how these protocols behave in practice and how their operating
parameters affect overall system performance. This paper presents the first
detailed experimental investigation of the peer selection strategy in the
popular BitTorrent protocol. By observing more than 40 nodes in instrumented
private torrents, we validate three protocol properties that, though believed
to hold, have not been previously demonstrated experimentally: the clustering
of similar-bandwidth peers, the effectiveness of BitTorrent's sharing
incentives, and the peers' high uplink utilization. In addition, we observe
that BitTorrent's modified choking algorithm in seed state provides uniform
service to all peers, and that an underprovisioned initial seed leads to
absence of peer clustering and less effective sharing incentives. Based on our
results, we provide guidelines for seed provisioning by content providers, and
discuss a tracker protocol extension that addresses an identified limitation of
the protocol.


title:
Wireless Lan to Support Multimedia Communication Using Spread Spectrum
  Technology

abstract:
  Wireless LAN is currently enjoying rapid deployment in University
departments, business offices, hospitals and homes. It becomes an inexpensive
technology and allows multiple numbers of the households to simultaneously
access the internet while roaming about the house. In the present work, the
design and development of a wireless LAN is highlighted which utilizes direct
sequence spread spectrum (DSSS) technology at 900MHz RF carrier frequency in
its physical layer. This provides enormous security in the physical layer and
hence it is very difficult to hack or jam the network. The installation cost is
also less due to the use of 900 MHz RF carrier frequency..


title: Tag-Cloud Drawing: Algorithms for Cloud Visualization

abstract:
  Tag clouds provide an aggregate of tag-usage statistics. They are typically
sent as in-line HTML to browsers. However, display mechanisms suited for
ordinary text are not ideal for tags, because font sizes may vary widely on a
line. As well, the typical layout does not account for relationships that may
be known between tags. This paper presents models and algorithms to improve the
display of tag clouds that consist of in-line HTML, as well as algorithms that
use nested tables to achieve a more general 2-dimensional layout in which tag
relationships are considered. The first algorithms leverage prior work in
typesetting and rectangle packing, whereas the second group of algorithms
leverage prior work in Electronic Design Automation. Experiments show our
algorithms can be efficiently implemented and perform well.


title:
Geometric Complexity Theory IV: nonstandard quantum group for the
  Kronecker problem

abstract:
  The Kronecker coefficient g_{\lambda \mu \nu} is the multiplicity of the
GL(V)\times GL(W)-irreducible V_\lambda \otimes W_\mu in the restriction of the
GL(X)-irreducible X_\nu via the natural map GL(V)\times GL(W) \to GL(V \otimes
W), where V, W are \mathbb{C}-vector spaces and X = V \otimes W. A fundamental
open problem in algebraic combinatorics is to find a positive combinatorial
formula for these coefficients.
  We construct two quantum objects for this problem, which we call the
nonstandard quantum group and nonstandard Hecke algebra. We show that the
nonstandard quantum group has a compact real form and its representations are
completely reducible, that the nonstandard Hecke algebra is semisimple, and
that they satisfy an analog of quantum Schur-Weyl duality.
  Using these nonstandard objects as a guide, we follow the approach of Adsul,
Sohoni, and Subrahmanyam to construct, in the case dim(V) = dim(W) =2, a
representation \check{X}_\nu of the nonstandard quantum group that specializes
to Res_{GL(V) \times GL(W)} X_\nu at q=1. We then define a global crystal basis
+HNSTC(\nu) of \check{X}_\nu that solves the two-row Kronecker problem: the
number of highest weight elements of +HNSTC(\nu) of weight (\lambda,\mu) is the
Kronecker coefficient g_{\lambda \mu \nu}. We go on to develop the beginnings
of a graphical calculus for this basis, along the lines of the U_q(\sl_2)
graphical calculus, and use this to organize the crystal components of
+HNSTC(\nu) into eight families. This yields a fairly simple, explicit and
positive formula for two-row Kronecker coefficients, generalizing a formula of
Brown, van Willigenburg, and Zabrocki. As a byproduct of the approach, we also
obtain a rule for the decomposition of Res_{GL_2 \times GL_2 \rtimes \S_2}
X_\nu into irreducibles.


title: Maximum Weighted Sum Rate of Multi-Antenna Broadcast Channels

abstract:
  Recently, researchers showed that dirty paper coding (DPC) is the optimal
transmission strategy for multiple-input multiple-output broadcast channels
(MIMO-BC). In this paper, we study how to determine the maximum weighted sum of
DPC rates through solving the maximum weighted sum rate problem of the dual
MIMO multiple access channel (MIMO-MAC) with a sum power constraint. We first
simplify the maximum weighted sum rate problem such that enumerating all
possible decoding orders in the dual MIMO-MAC is unnecessary. We then design an
efficient algorithm based on conjugate gradient projection (CGP) to solve the
maximum weighted sum rate problem. Our proposed CGP method utilizes the
powerful concept of Hessian conjugacy. We also develop a rigorous algorithm to
solve the projection problem. We show that CGP enjoys provable convergence,
nice scalability, and great efficiency for large MIMO-BC systems.


title:
User-level DSM System for Modern High-Performance Interconnection
  Networks

abstract:
  In this paper, we introduce a new user-level DSM system which has the ability
to directly interact with underlying interconnection networks. The DSM system
provides the application programmer a flexible API to program parallel
applications either using shared memory semantics over physically distributed
memory or to use an efficient remote memory demand paging technique. We also
introduce a new time slice based memory consistency protocol which is used by
the DSM system. We present preliminary results from our implementation on a
small Opteron Linux cluster interconnected over Myrinet.


title: Automatic Selection of Bitmap Join Indexes in Data Warehouses

abstract:
  The queries defined on data warehouses are complex and use several join
operations that induce an expensive computational cost. This cost becomes even
more prohibitive when queries access very large volumes of data. To improve
response time, data warehouse administrators generally use indexing techniques
such as star join indexes or bitmap join indexes. This task is nevertheless
complex and fastidious. Our solution lies in the field of data warehouse
auto-administration. In this framework, we propose an automatic index selection
strategy. We exploit a data mining technique ; more precisely frequent itemset
mining, in order to determine a set of candidate indexes from a given workload.
Then, we propose several cost models allowing to create an index configuration
composed by the indexes providing the best profit. These models evaluate the
cost of accessing data using bitmap join indexes, and the cost of updating and
storing these indexes.


title: Clustering-Based Materialized View Selection in Data Warehouses

abstract:
  Materialized view selection is a non-trivial task. Hence, its complexity must
be reduced. A judicious choice of views must be cost-driven and influenced by
the workload experienced by the system. In this paper, we propose a framework
for materialized view selection that exploits a data mining technique
(clustering), in order to determine clusters of similar queries. We also
propose a view merging algorithm that builds a set of candidate views, as well
as a greedy process for selecting a set of views to materialize. This selection
is based on cost models that evaluate the cost of accessing data using views
and the cost of storing these views. To validate our strategy, we executed a
workload of decision-support queries on a test data warehouse, with and without
using our strategy. Our experimental results demonstrate its efficiency, even
when storage space is limited.


title:
We cite as we communicate: A communication model for the citation
  process

abstract:
  Building on ideas from linguistics, psychology, and social sciences about the
possible mechanisms of human decision-making, we propose a novel theoretical
framework for the citation analysis. Given the existing trend to investigate
citation statistics in the context of various forms of power and Zipfian laws,
we show that the popular models of citation have poor predictive ability and
can hardly provide for an adequate explanation of the observed behavior of the
empirical data. An alternative model is then derived, using the apparatus of
statistical mechanics. The model is applied to approximate the citation
frequencies of scientific articles from two large collections, and it
demonstrates a predictive potential much superior to the one of any of the
citation models known to the authors from the literature. Some analytical
properties of the developed model are discussed, and conclusions are drawn.
Directions for future work are also given at the paper's end.


title:
On the Design of Generic Static Analyzers for Modern Imperative
  Languages

abstract:
  The design and implementation of precise static analyzers for significant
fragments of modern imperative languages like C, C++, Java and Python is a
challenging problem. In this paper, we consider a core imperative language that
has several features found in mainstream languages such as those including
recursive functions, run-time system and user-defined exceptions, and a
realistic data and memory model. For this language we provide a concrete
semantics --characterizing both finite and infinite computations-- and a
generic abstract semantics that we prove sound with respect to the concrete
one. We say the abstract semantics is generic since it is designed to be
completely parametric on the analysis domains: in particular, it provides
support for \emph{relational} domains (i.e., abstract domains that can capture
the relationships between different data objects). We also sketch how the
proposed methodology can be extended to accommodate a larger language that
includes pointers, compound data objects and non-structured control flow
mechanisms. The approach, which is based on structured, big-step
$\mathrm{G}^\infty\mathrm{SOS}$ operational semantics and on abstract
interpretation, is modular in that the overall static analyzer is naturally
partitioned into components with clearly identified responsibilities and
interfaces, something that greatly simplifies both the proof of correctness and
the implementation.


title:
Self-adaptive Gossip Policies for Distributed Population-based
  Algorithms

abstract:
  Gossipping has demonstrate to be an efficient mechanism for spreading
information among P2P networks. Within the context of P2P computing, we propose
the so-called Evolvable Agent Model for distributed population-based algorithms
which uses gossipping as communication policy, and represents every individual
as a self-scheduled single thread. The model avoids obsolete nodes in the
population by defining a self-adaptive refresh rate which depends on the
latency and bandwidth of the network. Such a mechanism balances the migration
rate to the congestion of the links pursuing global population coherence. We
perform an experimental evaluation of this model on a real parallel system and
observe how solution quality and algorithm speed scale with the number of
processors with this seamless approach.


title: Mathematical model of interest matchmaking in electronic social networks

abstract:
  The problem of matchmaking in electronic social networks is formulated as an
optimization problem. In particular, a function measuring the matching degree
of fields of interest of a search profile with those of an advertising profile
is proposed.


title: Support-Graph Preconditioners for 2-Dimensional Trusses

abstract:
  We use support theory, in particular the fretsaw extensions of Shklarski and
Toledo, to design preconditioners for the stiffness matrices of 2-dimensional
truss structures that are stiffly connected. Provided that all the lengths of
the trusses are within constant factors of each other, that the angles at the
corners of the triangles are bounded away from 0 and $\pi$, and that the
elastic moduli and cross-sectional areas of all the truss elements are within
constant factors of each other, our preconditioners allow us to solve linear
equations in the stiffness matrices to accuracy $\epsilon$ in time $O (n^{5/4}
(\log^{2}n \log \log n)^{3/4} \log (1/\epsilon))$.


title:
Sequential decoding for lossless streaming source coding with side
  information

abstract:
  The problem of lossless fixed-rate streaming coding of discrete memoryless
sources with side information at the decoder is studied. A random time-varying
tree-code is used to sequentially bin strings and a Stack Algorithm with a
variable bias uses the side information to give a delay-universal coding system
for lossless source coding with side information. The scheme is shown to give
exponentially decaying probability of error with delay, with exponent equal to
Gallager's random coding exponent for sources with side information. The mean
of the random variable of computation for the stack decoder is bounded, and
conditions on the bias are given to guarantee a finite $\rho^{th}$ moment for
$0 \leq \rho \leq 1$.
  Further, the problem is also studied in the case where there is a discrete
memoryless channel between encoder and decoder. The same scheme is slightly
modified to give a joint-source channel encoder and Stack Algorithm-based
sequential decoder using side information. Again, by a suitable choice of bias,
the probability of error decays exponentially with delay and the random
variable of computation has a finite mean. Simulation results for several
examples are given.


title: Differential Equations for Algebraic Functions

abstract:
  It is classical that univariate algebraic functions satisfy linear
differential equations with polynomial coefficients. Linear recurrences follow
for the coefficients of their power series expansions. We show that the linear
differential equation of minimal order has coefficients whose degree is cubic
in the degree of the function. We also show that there exists a linear
differential equation of order linear in the degree whose coefficients are only
of quadratic degree. Furthermore, we prove the existence of recurrences of
order and degree close to optimal. We study the complexity of computing these
differential equations and recurrences. We deduce a fast algorithm for the
expansion of algebraic series.


title: Rapid Almost-Complete Broadcasting in Faulty Networks

abstract:
  This paper studies the problem of broadcasting in synchronous point-to-point
networks, where one initiator owns a piece of information that has to be
transmitted to all other vertices as fast as possible. The model of fractional
dynamic faults with threshold is considered: in every step either a fixed
number $T$, or a fraction $\alpha$, of sent messages can be lost depending on
which quantity is larger.
  As the main result we show that in complete graphs and hypercubes it is
possible to inform all but a constant number of vertices, exhibiting only a
logarithmic slowdown, i.e. in time $O(D\log n)$ where $D$ is the diameter of
the network and $n$ is the number of vertices.
  Moreover, for complete graphs under some additional conditions (sense of
direction, or $\alpha<0.55$) the remaining constant number of vertices can be
informed in the same time, i.e. $O(\log n)$.


title: Adaptive Methods for Linear Programming Decoding

abstract:
  Detectability of failures of linear programming (LP) decoding and the
potential for improvement by adding new constraints motivate the use of an
adaptive approach in selecting the constraints for the underlying LP problem.
In this paper, we make a first step in studying this method, and show that it
can significantly reduce the complexity of the problem, which was originally
exponential in the maximum check-node degree. We further show that adaptively
adding new constraints, e.g. by combining parity checks, can provide large
gains in the performance.


title: Modelling Complexity in Musical Rhythm

abstract:
  This paper constructs a tree structure for the music rhythm using the
L-system. It models the structure as an automata and derives its complexity. It
also solves the complexity for the L-system. This complexity can resolve the
similarity between trees. This complexity serves as a measure of psychological
complexity for rhythms. It resolves the music complexity of various
compositions including the Mozart effect K488.
  Keyword: music perception, psychological complexity, rhythm, L-system,
automata, temporal associative memory, inverse problem, rewriting rule,
bracketed string, tree similarity


title: Intrinsic dimension of a dataset: what properties does one expect?

abstract:
  We propose an axiomatic approach to the concept of an intrinsic dimension of
a dataset, based on a viewpoint of geometry of high-dimensional structures. Our
first axiom postulates that high values of dimension be indicative of the
presence of the curse of dimensionality (in a certain precise mathematical
sense). The second axiom requires the dimension to depend smoothly on a
distance between datasets (so that the dimension of a dataset and that of an
approximating principal manifold would be close to each other). The third axiom
is a normalization condition: the dimension of the Euclidean $n$-sphere $\s^n$
is $\Theta(n)$. We give an example of a dimension function satisfying our
axioms, even though it is in general computationally unfeasible, and discuss a
computationally cheap function satisfying most but not all of our axioms (the
``intrinsic dimensionality'' of Ch\'avez et al.)


title:
Evolutionary Socioeconomics: Notes on the Computer Simulation according
  to the de Finetti - Simon Principia

abstract:
  The present note includes explanatory comments about the synergic interaction
within the sphere of the socioeconomic analysis between the two following
theoretical frameworks. (I). The Darwinian evolutionary model. (II). The
computer simulation in accordance with the principia established by Bruno de
Finetti and Herbert Simon.


title: Isochronous Data Transmission With Rates Close to Channel Capacity

abstract:
  The existing ARQ schemes (including a hybrid ARQ) have a throughput depending
on packet error probability. In this paper we describe a strategy for delay
tolerant applications which provide a constant throughput until the algorithm
robustness criterion is not failed. The algorithm robustness criterion is
applied to find the optimum size of the retransmission block in the assumption
of the small changes of coding rate within the rate compatible codes family.


title:
Physarum machine: Implementation of Kolmogorov-Uspensky machine in
  biological substrat

abstract:
  We implement Kolmogorov-Uspensky machine on a plasmodium of true slime mold
{\em Physarum polycephalum}. We provide experimental findings on realization of
the machine instructions, illustrate basic operations, and elements of
programming.


title:
A theorem on the quantum evaluation of Weight Enumerators for a certain
  class of Cyclic Codes with a note on Cyclotomic cosets

abstract:
  This note is a stripped down version of a published paper on the Potts
partition function, where we concentrate solely on the linear coding aspect of
our approach. It is meant as a resource for people interested in coding theory
but who do not know much of the mathematics involved and how quantum
computation may provide a speed up in the computation of a very important
quantity in coding theory. We provide a theorem on the quantum computation of
the Weight Enumerator polynomial for a restricted family of cyclic codes. The
complexity of obtaining an exact evaluation is $O(k^{2s}(\log q)^{2})$, where
$s$ is a parameter which determines the class of cyclic codes in question, $q$
is the characteristic of the finite field over which the code is defined, and
$k$ is the dimension of the code. We also provide an overview of cyclotomic
cosets and discuss applications including how they can be used to speed up the
computation of the weight enumerator polynomial (which is related to the Potts
partition function). We also give an algorithm which returns the coset leaders
and the size of each coset from the list $\{0,1,2,...,N-1\}$, whose time
complexity is soft-O(N). This algorithm uses standard techniques but we include
it as a resource for students. Note that cyclotomic cosets do not improve the
asymptotic complexity of the computation of weight enumerators.


title: Space-contained conflict revision, for geographic information

abstract:
  Using qualitative reasoning with geographic information, contrarily, for
instance, with robotics, looks not only fastidious (i.e.: encoding knowledge
Propositional Logics PL), but appears to be computational complex, and not
tractable at all, most of the time. However, knowledge fusion or revision, is a
common operation performed when users merge several different data sets in a
unique decision making process, without much support. Introducing logics would
be a great improvement, and we propose in this paper, means for deciding -a
priori- if one application can benefit from a complete revision, under only the
assumption of a conjecture that we name the "containment conjecture", which
limits the size of the minimal conflicts to revise. We demonstrate that this
conjecture brings us the interesting computational property of performing a
not-provable but global, revision, made of many local revisions, at a tractable
size. We illustrate this approach on an application.


title: Open Access Scientometrics and the UK Research Assessment Exercise

abstract:
  Scientometric predictors of research performance need to be validated by
showing that they have a high correlation with the external criterion they are
trying to predict. The UK Research Assessment Exercise (RAE), together with the
growing movement toward making the full-texts of research articles freely
available on the web -- offer a unique opportunity to test and validate a
wealth of old and new scientometric predictors, through multiple regression
analysis: Publications, journal impact factors, citations, co-citations,
citation chronometrics (age, growth, latency to peak, decay rate),
hub/authority scores, h-index, prior funding, student counts, co-authorship
scores, endogamy/exogamy, textual proximity, download/co-downloads and their
chronometrics, etc. can all be tested and validated jointly, discipline by
discipline, against their RAE panel rankings in the forthcoming parallel
panel-based and metric RAE in 2008. The weights of each predictor can be
calibrated to maximize the joint correlation with the rankings. Open Access
Scientometrics will provide powerful new means of navigating, evaluating,
predicting and analyzing the growing Open Access database, as well as powerful
incentives for making it grow faster. ~


title: Structure induction by lossless graph compression

abstract:
  This work is motivated by the necessity to automate the discovery of
structure in vast and evergrowing collection of relational data commonly
represented as graphs, for example genomic networks. A novel algorithm, dubbed
Graphitour, for structure induction by lossless graph compression is presented
and illustrated by a clear and broadly known case of nested structure in a DNA
molecule. This work extends to graphs some well established approaches to
grammatical inference previously applied only to strings. The bottom-up graph
compression problem is related to the maximum cardinality (non-bipartite)
maximum cardinality matching problem. The algorithm accepts a variety of graph
types including directed graphs and graphs with labeled nodes and arcs. The
resulting structure could be used for representation and classification of
graphs.


title: Computing Good Nash Equilibria in Graphical Games

abstract:
  This paper addresses the problem of fair equilibrium selection in graphical
games. Our approach is based on the data structure called the {\em best
response policy}, which was proposed by Kearns et al. \cite{kls} as a way to
represent all Nash equilibria of a graphical game. In \cite{egg}, it was shown
that the best response policy has polynomial size as long as the underlying
graph is a path. In this paper, we show that if the underlying graph is a
bounded-degree tree and the best response policy has polynomial size then there
is an efficient algorithm which constructs a Nash equilibrium that guarantees
certain payoffs to all participants. Another attractive solution concept is a
Nash equilibrium that maximizes the social welfare. We show that, while exactly
computing the latter is infeasible (we prove that solving this problem may
involve algebraic numbers of an arbitrarily high degree), there exists an FPTAS
for finding such an equilibrium as long as the best response policy has
polynomial size. These two algorithms can be combined to produce Nash
equilibria that satisfy various fairness criteria.


title:
Automatic Generation of Benchmarks for Plagiarism Detection Tools using
  Grammatical Evolution

abstract: This paper has been withdrawn by the authors due to a major rewriting.


title: Dependency Parsing with Dynamic Bayesian Network

abstract:
  Exact parsing with finite state automata is deemed inappropriate because of
the unbounded non-locality languages overwhelmingly exhibit. We propose a way
to structure the parsing task in order to make it amenable to local
classification methods. This allows us to build a Dynamic Bayesian Network
which uncovers the syntactic dependency structure of English sentences.
Experiments with the Wall Street Journal demonstrate that the model
successfully learns from labeled data.


title: Uncovering Plagiarism Networks

abstract:
  Plagiarism detection in educational programming assignments is still a
problematic issue in terms of resource waste, ethical controversy, legal risks,
and technical complexity. This paper presents AC, a modular plagiarism
detection system. The design is portable across platforms and assignment
formats and provides easy extraction into the internal assignment
representation. Multiple similarity measures have been incorporated, both
existing and newly-developed. Statistical analysis and several graphical
visualizations aid in the interpretation of analysis results. The system has
been evaluated with a survey that encompasses several academic semesters of use
at the authors' institution.


title:
ReSHAPE: A Framework for Dynamic Resizing and Scheduling of Homogeneous
  Applications in a Parallel Environment

abstract:
  Applications in science and engineering often require huge computational
resources for solving problems within a reasonable time frame. Parallel
supercomputers provide the computational infrastructure for solving such
problems. A traditional application scheduler running on a parallel cluster
only supports static scheduling where the number of processors allocated to an
application remains fixed throughout the lifetime of execution of the job. Due
to the unpredictability in job arrival times and varying resource requirements,
static scheduling can result in idle system resources thereby decreasing the
overall system throughput. In this paper we present a prototype framework
called ReSHAPE, which supports dynamic resizing of parallel MPI applications
executed on distributed memory platforms. The framework includes a scheduler
that supports resizing of applications, an API to enable applications to
interact with the scheduler, and a library that makes resizing viable.
Applications executed using the ReSHAPE scheduler framework can expand to take
advantage of additional free processors or can shrink to accommodate a high
priority application, without getting suspended. In our research, we have
mainly focused on structured applications that have two-dimensional data arrays
distributed across a two-dimensional processor grid. The resize library
includes algorithms for processor selection and processor mapping. Experimental
results show that the ReSHAPE framework can improve individual job turn-around
time and overall system throughput.


title: Reinforcement Learning for Adaptive Routing

abstract:
  Reinforcement learning means learning a policy--a mapping of observations
into actions--based on feedback from the environment. The learning can be
viewed as browsing a set of policies while evaluating them by trial through
interaction with the environment. We present an application of gradient ascent
algorithm for reinforcement learning to a complex domain of packet routing in
network communication and compare the performance of this algorithm to other
routing methods on a benchmark problem.


title:
TCP throughput guarantee in the DiffServ Assured Forwarding service:
  what about the results?

abstract:
  Since the proposition of Quality of Service architectures by the IETF, the
interaction between TCP and the QoS services has been intensively studied. This
paper proposes to look forward to the results obtained in terms of TCP
throughput guarantee in the DiffServ Assured Forwarding (DiffServ/AF) service
and to present an overview of the different proposals to solve the problem. It
has been demonstrated that the standardized IETF DiffServ conditioners such as
the token bucket color marker and the time sliding window color maker were not
good TCP traffic descriptors. Starting with this point, several propositions
have been made and most of them presents new marking schemes in order to
replace or improve the traditional token bucket color marker. The main problem
is that TCP congestion control is not designed to work with the AF service.
Indeed, both mechanisms are antagonists. TCP has the property to share in a
fair manner the bottleneck bandwidth between flows while DiffServ network
provides a level of service controllable and predictable. In this paper, we
build a classification of all the propositions made during these last years and
compare them. As a result, we will see that these conditioning schemes can be
separated in three sets of action level and that the conditioning at the
network edge level is the most accepted one. We conclude that the problem is
still unsolved and that TCP, conditioned or not conditioned, remains
inappropriate to the DiffServ/AF service.


title: How to Guarantee Secrecy for Cryptographic Protocols

abstract:
  In this paper we propose a general definition of secrecy for cryptographic
protocols in the Dolev-Yao model. We give a sufficient condition ensuring
secrecy for protocols where rules have encryption depth at most two, that is
satisfied by almost all practical protocols. The only allowed primitives in the
class of protocols we consider are pairing and encryption with atomic keys.
Moreover, we describe an algorithm of practical interest which transforms a
cryptographic protocol into a secure one from the point of view of secrecy,
without changing its original goal with respect to secrecy of nonces and keys,
provided the protocol satisfies some conditions. These conditions are not very
restrictive and are satisfied for most practical protocols.


title:
Constructive Conjugate Codes for Quantum Error Correction and
  Cryptography

abstract:
  A conjugate code pair is defined as a pair of linear codes either of which
contains the dual of the other. A conjugate code pair represents the essential
structure of the corresponding Calderbank-Shor-Steane (CSS) quantum
error-correcting code. It is known that conjugate code pairs are applicable to
quantum cryptography. In this work, a polynomial construction of conjugate code
pairs is presented. The constructed pairs achieve the highest known achievable
rate on additive channels, and are decodable with algorithms of polynomial
complexity.


title: Pragmatic Space-Time Trellis Codes for Block Fading Channels

abstract:
  A pragmatic approach for the construction of space-time codes over block
fading channels is investigated. The approach consists in using common
convolutional encoders and Viterbi decoders with suitable generators and rates,
thus greatly simplifying the implementation of space-time codes. For the design
of pragmatic space-time codes a methodology is proposed and applied, based on
the extension of the concept of generalized transfer function for convolutional
codes over block fading channels. Our search algorithm produces the
convolutional encoder generators of pragmatic space-time codes for various
number of states, number of antennas and fading rate. Finally it is shown that,
for the investigated cases, the performance of pragmatic space-time codes is
better than that of previously known space-time codes, confirming that they are
a valuable choice in terms of both implementation complexity and performance.


title: How much feedback is required in MIMO Broadcast Channels?

abstract:
  In this paper, a downlink communication system, in which a Base Station (BS)
equipped with M antennas communicates with N users each equipped with K receive
antennas ($K \leq M$), is considered. It is assumed that the receivers have
perfect Channel State Information (CSI), while the BS only knows the partial
CSI, provided by the receivers via feedback. The minimum amount of feedback
required at the BS, to achieve the maximum sum-rate capacity in the asymptotic
case of $N \to \infty$ and different ranges of SNR is studied. In the fixed and
low SNR regimes, it is demonstrated that to achieve the maximum sum-rate, an
infinite amount of feedback is required. Moreover, in order to reduce the gap
to the optimum sum-rate to zero, in the fixed SNR regime, the minimum amount of
feedback scales as $\theta(\ln \ln \ln N)$, which is achievable by the Random
Beam-Forming scheme proposed in [14]. In the high SNR regime, two cases are
considered; in the case of $K < M$, it is proved that the minimum amount of
feedback bits to reduce the gap between the achievable sum-rate and the maximum
sum-rate to zero grows logaritmically with SNR, which is achievable by the
"Generalized Random Beam-Forming" scheme, proposed in [18]. In the case of $K =
M$, it is shown that by using the Random Beam-Forming scheme and the total
amount of feedback not growing with SNR, the maximum sum-rate capacity is
achieved.


title: On The Capacity Of Time-Varying Channels With Periodic Feedback

abstract:
  The capacity of time-varying channels with periodic feedback at the
transmitter is evaluated. It is assumed that the channel state information is
perfectly known at the receiver and is fed back to the transmitter at the
regular time-intervals. The system capacity is investigated in two cases: i)
finite state Markov channel, and ii) additive white Gaussian noise channel with
time-correlated fading. In the first case, it is shown that the capacity is
achievable by multiplexing multiple codebooks across the channel. In the second
case, the channel capacity and the optimal adaptive coding is obtained. It is
shown that the optimal adaptation can be achieved by a single Gaussian
codebook, while adaptively allocating the total power based on the side
information at the transmitter.


title:
The Simultaneous Triple Product Property and Group-theoretic Results for
  the Exponent of Matrix Multiplication

abstract:
  We describe certain special consequences of certain elementary methods from
group theory for studying the algebraic complexity of matrix multiplication, as
developed by H. Cohn, C. Umans et. al. in 2003 and 2005. The measure of
complexity here is the exponent of matrix multiplication, a real parameter
between 2 and 3, which has been conjectured to be 2. More specifically, a
finite group may simultaneously "realize" several independent matrix
multiplications via its regular algebra if it has a family of triples of
"index" subsets which satisfy the so-called simultaneous triple product
property (STPP), in which case the complexity of these several multiplications
does not exceed the rank (complexity) of the algebra. This leads to bounds for
the exponent in terms of the size of the group and the sizes of its STPP
triples, as well as the dimensions of its distinct irreducible representations.
Wreath products of Abelian with symmetric groups appear especially important,
in this regard, and we give an example of such a group which shows that the
exponent is less than 2.84, and could be possibly be as small as 2.02 depending
on the number of simultaneous matrix multiplications it realizes.


title: A Polynomial Time Algorithm for SAT

abstract:
  Article presents the compatibility matrix method and illustrates it with the
application to P vs NP problem. The method is a generalization of descriptive
geometry: in the method, we draft problems and solve them utilizing the image
creation technique. The method reveals: P = NP = PSPACE


title: The finite tiling problem is undecidable in the hyperbolic plane

abstract:
  In this paper, we consider the finite tiling problem which was proved
undecidable in the Euclidean plane by Jarkko Kari in 1994. Here, we prove that
the same problem for the hyperbolic plane is also undecidable.


title: Computer Science and Game Theory: A Brief Survey

abstract:
  There has been a remarkable increase in work at the interface of computer
science and game theory in the past decade. In this article I survey some of
the main themes of work in the area, with a focus on the work in computer
science. Given the length constraints, I make no attempt at being
comprehensive, especially since other surveys are also available, and a
comprehensive survey book will appear shortly.


title: Exploring Logic Artificial Chemistries: An Illogical Attempt?

abstract:
  Robustness to a wide variety of negative factors and the ability to
self-repair is an inherent and natural characteristic of all life forms on
earth. As opposed to nature, man-made systems are in most cases not inherently
robust and a significant effort has to be made in order to make them resistant
against failures. This can be done in a wide variety of ways and on various
system levels. In the field of digital systems, for example, techniques such as
triple modular redundancy (TMR) are frequently used, which results in a
considerable hardware overhead. Biologically-inspired computing by means of
bio-chemical metaphors offers alternative paradigms, which need to be explored
and evaluated.
  Here, we are interested to evaluate the potential of nature-inspired
artificial chemistries and membrane systems as an alternative information
representing and processing paradigm in order to obtain robust and spatially
extended Boolean computing systems in a distributed environment. We investigate
conceptual approaches inspired by artificial chemistries and membrane systems
and compare proof-of-concepts. First, we show, that elementary logical
functions can be implemented. Second, we illustrate how they can be made more
robust and how they can be assembled to larger-scale systems. Finally, we
discuss the implications for and paths to possible genuine implementations.
Compared to the main body of work in artificial chemistries, we take a very
pragmatic and implementation-oriented approach and are interested in realizing
Boolean computations only. The results emphasize that artificial chemistries
can be used to implement Boolean logic in a spatially extended and distributed
environment and can also be made highly robust, but at a significant price.


title:
Type-II/III DCT/DST algorithms with reduced number of arithmetic
  operations

abstract:
  We present algorithms for the discrete cosine transform (DCT) and discrete
sine transform (DST), of types II and III, that achieve a lower count of real
multiplications and additions than previously published algorithms, without
sacrificing numerical accuracy. Asymptotically, the operation count is reduced
from ~ 2N log_2 N to ~ (17/9) N log_2 N for a power-of-two transform size N.
Furthermore, we show that a further N multiplications may be saved by a certain
rescaling of the inputs or outputs, generalizing a well-known technique for N=8
by Arai et al. These results are derived by considering the DCT to be a special
case of a DFT of length 4N, with certain symmetries, and then pruning redundant
operations from a recent improved fast Fourier transform algorithm (based on a
recursive rescaling of the conjugate-pair split radix algorithm). The improved
algorithms for DCT-III, DST-II, and DST-III follow immediately from the
improved count for the DCT-II.


title:
Asymptotic Analysis of Amplify and Forward Relaying in a Parallel MIMO
  Relay Network

abstract:
  This paper considers the setup of a parallel MIMO relay network in which $K$
relays, each equipped with $N$ antennas, assist the transmitter and the
receiver, each equipped with $M$ antennas, in the half-duplex mode, under the
assumption that $N\geq{M}$. This setup has been studied in the literature like
in \cite{nabar}, \cite{nabar2}, and \cite{qr}. In this paper, a simple scheme,
the so-called Incremental Cooperative Beamforming, is introduced and shown to
achieve the capacity of the network in the asymptotic case of $K\to{\infty}$
with a gap no more than $O(\frac{1}{\log(K)})$. This result is shown to hold,
as long as the power of the relays scales as $\omega(\frac{\log^9(K)}{K})$.
Finally, the asymptotic SNR behavior is studied and it is proved that the
proposed scheme achieves the full multiplexing gain, regardless of the number
of relays.


title:
Quantum Lambda Calculi with Classical Control: Syntax and Expressive
  Power

abstract:
  We study an untyped lambda calculus with quantum data and classical control.
This work stems from previous proposals by Selinger and Valiron and by Van
Tonder. We focus on syntax and expressiveness, rather than (denotational)
semantics. We prove subject reduction, confluence and a standardization
theorem. Moreover, we prove the computational equivalence of the proposed
calculus with a suitable class of quantum circuit families.


title: The periodic domino problem is undecidable in the hyperbolic plane

abstract:
  In this paper, we consider the periodic tiling problem which was proved
undecidable in the Euclidean plane by Yu. Gurevich and I. Koriakov in 1972.
Here, we prove that the same problem for the hyperbolic plane is also
undecidable.


title: A Hot Channel

abstract:
  This paper studies on-chip communication with non-ideal heat sinks. A channel
model is proposed where the variance of the additive noise depends on the
weighted sum of the past channel input powers. It is shown that, depending on
the weights, the capacity can be either bounded or unbounded in the input
power. A necessary condition and a sufficient condition for the capacity to be
bounded are presented.


title: Liveness of Heap Data for Functional Programs

abstract:
  Functional programming languages use garbage collection for heap memory
management. Ideally, garbage collectors should reclaim all objects that are
dead at the time of garbage collection. An object is dead at an execution
instant if it is not used in future. Garbage collectors collect only those dead
objects that are not reachable from any program variable. This is because they
are not able to distinguish between reachable objects that are dead and
reachable objects that are live.
  In this paper, we describe a static analysis to discover reachable dead
objects in programs written in first-order, eager functional programming
languages. The results of this technique can be used to make reachable dead
objects unreachable, thereby allowing garbage collectors to reclaim more dead
objects.


title: Case Base Mining for Adaptation Knowledge Acquisition

abstract:
  In case-based reasoning, the adaptation of a source case in order to solve
the target problem is at the same time crucial and difficult to implement. The
reason for this difficulty is that, in general, adaptation strongly depends on
domain-dependent knowledge. This fact motivates research on adaptation
knowledge acquisition (AKA). This paper presents an approach to AKA based on
the principles and techniques of knowledge discovery from databases and
data-mining. It is implemented in CABAMAKA, a system that explores the
variations within the case base to elicit adaptation knowledge. This system has
been successfully tested in an application of case-based reasoning to decision
support in the domain of breast cancer treatment.


title: Verifying the Unification Algorithm in LCF

abstract:
  Manna and Waldinger's theory of substitutions and unification has been
verified using the Cambridge LCF theorem prover. A proof of the monotonicity of
substitution is presented in detail, as an example of interaction with LCF.
Translating the theory into LCF's domain-theoretic logic is largely
straightforward. Well-founded induction on a complex ordering is translated
into nested structural inductions. Correctness of unification is expressed
using predicates for such properties as idempotence and most-generality. The
verification is presented as a series of lemmas. The LCF proofs are compared
with the original ones, and with other approaches. It appears difficult to find
a logic that is both simple and flexible, especially for proving termination.


title: Constructing Recursion Operators in Intuitionistic Type Theory

abstract:
  Martin-L\"of's Intuitionistic Theory of Types is becoming popular for formal
reasoning about computer programs. To handle recursion schemes other than
primitive recursion, a theory of well-founded relations is presented. Using
primitive recursion over higher types, induction and recursion are formally
derived for a large class of well-founded relations. Included are < on natural
numbers, and relations formed by inverse images, addition, multiplication, and
exponentiation of other relations. The constructions are given in full detail
to allow their use in theorem provers for Type Theory, such as Nuprl. The
theory is compared with work in the field of ordinal recursion over higher
types.


title:
Proving Termination of Normalization Functions for Conditional
  Expressions

abstract:
  Boyer and Moore have discussed a recursive function that puts conditional
expressions into normal form [1]. It is difficult to prove that this function
terminates on all inputs. Three termination proofs are compared: (1) using a
measure function, (2) in domain theory using LCF, (3) showing that its
recursion relation, defined by the pattern of recursive calls, is well-founded.
The last two proofs are essentially the same though conducted in markedly
different logical frameworks. An obviously total variant of the normalize
function is presented as the `computational meaning' of those two proofs. A
related function makes nested recursive calls. The three termination proofs
become more complex: termination and correctness must be proved simultaneously.
The recursion relation approach seems flexible enough to handle subtle
termination proofs where previously domain theory seemed essential.


title: Natural Deduction as Higher-Order Resolution

abstract:
  An interactive theorem prover, Isabelle, is under development. In LCF, each
inference rule is represented by one function for forwards proof and another (a
tactic) for backwards proof. In Isabelle, each inference rule is represented by
a Horn clause. Resolution gives both forwards and backwards proof, supporting a
large class of logics. Isabelle has been used to prove theorems in
Martin-L\"of's Constructive Type Theory. Quantifiers pose several difficulties:
substitution, bound variables, Skolemization. Isabelle's representation of
logical syntax is the typed lambda-calculus, requiring higher- order
unification. It may have potential for logic programming. Depth-first
subgoaling along inference rules constitutes a higher-order Prolog.


title: The Foundation of a Generic Theorem Prover

abstract:
  Isabelle is an interactive theorem prover that supports a variety of logics.
It represents rules as propositions (not as functions) and builds proofs by
combining rules. These operations constitute a meta-logic (or `logical
framework') in which the object-logics are formalized. Isabelle is now based on
higher-order logic -- a precise and well-understood foundation. Examples
illustrate use of this meta-logic to formalize logics and proofs. Axioms for
first-order logic are shown sound and complete. Backwards proof is formalized
by meta-reasoning about object-level entailment. Higher-order logic has several
practical advantages over other meta-logics. Many proof techniques are known,
such as Huet's higher-order unification procedure.


title: Isabelle: The Next 700 Theorem Provers

abstract:
  Isabelle is a generic theorem prover, designed for interactive reasoning in a
variety of formal theories. At present it provides useful proof procedures for
Constructive Type Theory, various first-order logics, Zermelo-Fraenkel set
theory, and higher-order logic. This survey of Isabelle serves as an
introduction to the literature. It explains why generic theorem proving is
beneficial. It gives a thorough history of Isabelle, beginning with its origins
in the LCF system. It presents an account of how logics are represented,
illustrated using classical logic. The approach is compared with the Edinburgh
Logical Framework. Several of the Isabelle object-logics are presented.


title: A Formulation of the Simple Theory of Types (for Isabelle)

abstract:
  Simple type theory is formulated for use with the generic theorem prover
Isabelle. This requires explicit type inference rules. There are function,
product, and subset types, which may be empty. Descriptions (the eta-operator)
introduce the Axiom of Choice. Higher-order logic is obtained through
reflection between formulae and terms of type bool. Recursive types and
functions can be formally constructed. Isabelle proof procedures are described.
The logic appears suitable for general mathematics as well as computational
problems.


title: A Higher-Order Implementation of Rewriting

abstract:
  Many automatic theorem-provers rely on rewriting. Using theorems as rewrite
rules helps to simplify the subgoals that arise during a proof.
  LCF is an interactive theorem-prover intended for reasoning about
computation. Its implementation of rewriting is presented in detail. LCF
provides a family of rewriting functions, and operators to combine them. A
succession of functions is described, from pattern matching primitives to the
rewriting tool that performs most inferences in LCF proofs.
  The design is highly modular. Each function performs a basic, specific task,
such as recognizing a certain form of tautology. Each operator implements one
method of building a rewriting function from simpler ones. These pieces can be
put together in numerous ways, yielding a variety of rewrit- ing strategies.
  The approach involves programming with higher-order functions. Rewriting
functions are data values, produced by computation on other rewriting
functions. The code is in daily use at Cambridge, demonstrating the practical
use of functional programming.


title: Logic Programming, Functional Programming, and Inductive Definitions

abstract:
  An attempt at unifying logic and functional programming is reported. As a
starting point, we take the view that "logic programs" are not about logic but
constitute inductive definitions of sets and relations. A skeletal language
design based on these considerations is sketched and a prototype implementation
discussed.


title: Designing a Theorem Prover

abstract:
  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.


title: Nested satisfiability

abstract:
  A special case of the satisfiability problem, in which the clauses have a
hierarchical structure, is shown to be solvable in linear time, assuming that
the clauses have been represented in a convenient way.


title: A note on digitized angles

abstract:
  We study the configurations of pixels that occur when two digitized straight
lines meet each other.


title: Textbook examples of recursion

abstract:
  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.


title: Theory and practice

abstract:
  The author argues to Silicon Valley that the most important and powerful part
of computer science is work that is simultaneously theoretical and practical.
He particularly considers the intersection of the theory of algorithms and
practical software development. He combines examples from the development of
the TeX typesetting system with clever jokes, criticisms, and encouragements.


title: Context-free multilanguages

abstract:
  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.
  The treatment is informal but essentially rigorous.


title: The problem of compatible representatives

abstract:
  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.


title: Dynamic Backtracking

abstract:
  Because of their occasional need to return to shallow points in a search
tree, existing backtracking methods can sometimes erase meaningful progress
toward solving a search problem. In this paper, we present a method by which
backtrack points can be moved deeper in the search space, thereby avoiding this
difficulty. The technique developed is a variant of dependency-directed
backtracking that uses only polynomial space while still providing useful
control information and retaining the completeness guarantees provided by
earlier approaches.


title:
A Market-Oriented Programming Environment and its Application to
  Distributed Multicommodity Flow Problems

abstract:
  Market price systems constitute a well-understood class of mechanisms that
under certain conditions provide effective decentralization of decision making
with minimal communication overhead. In a market-oriented programming approach
to distributed problem solving, we derive the activities and resource
allocations for a set of computational agents by computing the competitive
equilibrium of an artificial economy. WALRAS provides basic constructs for
defining computational market structures, and protocols for deriving their
corresponding price equilibria. In a particular realization of this approach
for a form of multicommodity flow problem, we see that careful construction of
the decision process according to economic principles can lead to efficient
distributed resource allocation, and that the behavior of the system can be
meaningfully analyzed in economic terms.


title: An Empirical Analysis of Search in GSAT

abstract:
  We describe an extensive study of search in GSAT, an approximation procedure
for propositional satisfiability. GSAT performs greedy hill-climbing on the
number of satisfied clauses in a truth assignment. Our experiments provide a
more complete picture of GSAT's search than previous accounts. We describe in
detail the two phases of search: rapid hill-climbing followed by a long plateau
search. We demonstrate that when applied to randomly generated 3SAT problems,
there is a very simple scaling with problem size for both the mean number of
satisfied clauses and the mean branching rate. Our results allow us to make
detailed numerical conjectures about the length of the hill-climbing phase, the
average gradient of this phase, and to conjecture that both the average score
and average branching rate decay exponentially during plateau search. We end by
showing how these results can be used to direct future theoretical analysis.
This work provides a case study of how computer experiments can be used to
improve understanding of the theoretical properties of algorithms.


title: The Difficulties of Learning Logic Programs with Cut

abstract:
  As real logic programmers normally use cut (!), an effective learning
procedure for logic programs should be able to deal with it. Because the cut
predicate has only a procedural meaning, clauses containing cut cannot be
learned using an extensional evaluation method, as is done in most learning
systems. On the other hand, searching a space of possible programs (instead of
a space of independent clauses) is unfeasible. An alternative solution is to
generate first a candidate base program which covers the positive examples, and
then make it consistent by inserting cut where appropriate. The problem of
learning programs with cut has not been investigated before and this seems to
be a natural and reasonable approach. We generalize this scheme and investigate
the difficulties that arise. Some of the major shortcomings are actually
caused, in general, by the need for intensional evaluation. As a conclusion,
the analysis of this paper suggests, on precise and technical grounds, that
learning cut is difficult, and current induction techniques should probably be
restricted to purely declarative logic languages.


title: Software Agents: Completing Patterns and Constructing User Interfaces

abstract:
  To support the goal of allowing users to record and retrieve information,
this paper describes an interactive note-taking system for pen-based computers
with two distinctive features. First, it actively predicts what the user is
going to write. Second, it automatically constructs a custom, button-box user
interface on request. The system is an example of a learning-apprentice
software- agent. A machine learning component characterizes the syntax and
semantics of the user's information. A performance system uses this learned
information to generate completion strings and construct a user interface.
Description of Online Appendix: People like to record information. Doing this
on paper is initially efficient, but lacks flexibility. Recording information
on a computer is less efficient but more powerful. In our new note taking
softwre, the user records information directly on a computer. Behind the
interface, an agent acts for the user. To help, it provides defaults and
constructs a custom user interface. The demonstration is a QuickTime movie of
the note taking agent in action. The file is a binhexed self-extracting
archive. Macintosh utilities for binhex are available from
mac.archive.umich.edu. QuickTime is available from ftp.apple.com in the
dts/mac/sys.soft/quicktime.


title: Set Theory for Verification: I. From Foundations to Functions

abstract:
  A logic for specification and verification is derived from the axioms of
Zermelo-Fraenkel set theory. The proofs are performed using the proof assistant
Isabelle. Isabelle is generic, supporting several different logics. Isabelle
has the flexibility to adapt to variants of set theory. Its higher-order syntax
supports the definition of new binding operators. Unknowns in subgoals can be
instantiated incrementally. The paper describes the derivation of rules for
descriptions, relations and functions, and discusses interactive proofs of
Cantor's Theorem, the Composition of Homomorphisms challenge [9], and Ramsey's
Theorem [5]. A generic proof assistant can stand up against provers dedicated
to particular logics.


title: Decidable Reasoning in Terminological Knowledge Representation Systems

abstract:
  Terminological knowledge representation systems (TKRSs) are tools for
designing and using knowledge bases that make use of terminological languages
(or concept languages). We analyze from a theoretical point of view a TKRS
whose capabilities go beyond the ones of presently available TKRSs. The new
features studied, often required in practical applications, can be summarized
in three main points. First, we consider a highly expressive terminological
language, called ALCNR, including general complements of concepts, number
restrictions and role conjunction. Second, we allow to express inclusion
statements between general concepts, and terminological cycles as a particular
case. Third, we prove the decidability of a number of desirable TKRS-deduction
services (like satisfiability, subsumption and instance checking) through a
sound, complete and terminating calculus for reasoning in ALCNR-knowledge
bases. Our calculus extends the general technique of constraint systems. As a
byproduct of the proof, we get also the result that inclusion statements in
ALCNR can be simulated by terminological cycles, if descriptive semantics is
adopted.


title: Teleo-Reactive Programs for Agent Control

abstract:
  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.


title: Mini-indexes for literate programs

abstract:
  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.


title:
Learning the Past Tense of English Verbs: The Symbolic Pattern
  Associator vs. Connectionist Models

abstract:
  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.


title:
Substructure Discovery Using Minimum Description Length and Background
  Knowledge

abstract:
  The ability to identify interesting and repetitive substructures is an
essential component to discovering knowledge in structural data. We describe a
new version of our SUBDUE substructure discovery system based on the minimum
description length principle. The SUBDUE system discovers substructures that
compress the original data and represent structural concepts in the data. By
replacing previously-discovered substructures in the data, multiple passes of
SUBDUE produce a hierarchical description of the structural regularities in the
data. SUBDUE uses a computationally-bounded inexact graph match that identifies
similar, but not identical, instances of a substructure and finds an
approximate measure of closeness of two substructures when under computational
constraints. In addition to the minimum description length principle, other
background knowledge can be used by SUBDUE to guide the search towards more
appropriate substructures. Experiments in a variety of domains demonstrate
SUBDUE's ability to find substructures capable of compressing the original data
and to discover structural concepts important to the domain. Description of
Online Appendix: This is a compressed tar file containing the SUBDUE discovery
system, written in C. The program accepts as input databases represented in
graph form, and will output discovered substructures with their corresponding
value.


title: Bias-Driven Revision of Logical Domain Theories

abstract:
  The theory revision problem is the problem of how best to go about revising a
deficient domain theory using information contained in examples that expose
inaccuracies. In this paper we present our approach to the theory revision
problem for propositional domain theories. The approach described here, called
PTR, uses probabilities associated with domain theory elements to numerically
track the ``flow'' of proof through the theory. This allows us to measure the
precise role of a clause or literal in allowing or preventing a (desired or
undesired) derivation for a given example. This information is used to
efficiently locate and repair flawed elements of the theory. PTR is proved to
converge to a theory which correctly classifies all examples, and shown
experimentally to be fast and accurate even for deep theories.


title:
Exploring the Decision Forest: An Empirical Investigation of Occam's
  Razor in Decision Tree Induction

abstract:
  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.


title:
A Semantics and Complete Algorithm for Subsumption in the CLASSIC
  Description Logic

abstract:
  This paper analyzes the correctness of the subsumption algorithm used in
CLASSIC, a description logic-based knowledge representation system that is
being used in practical applications. In order to deal efficiently with
individuals in CLASSIC descriptions, the developers have had to use an
algorithm that is incomplete with respect to the standard, model-theoretic
semantics for description logics. We provide a variant semantics for
descriptions with respect to which the current implementation is complete, and
which can be independently motivated. The soundness and completeness of the
polynomial-time subsumption algorithm is established using description graphs,
which are an abstracted version of the implementation structures used in
CLASSIC, and are of independent interest.


title: Applying GSAT to Non-Clausal Formulas

abstract:
  In this paper we describe how to modify GSAT so that it can be applied to
non-clausal formulas. The idea is to use a particular ``score'' function which
gives the number of clauses of the CNF conversion of a formula which are false
under a given truth assignment. Its value is computed in linear time, without
constructing the CNF conversion itself. The proposed methodology applies to
most of the variants of GSAT proposed so far.


title: Random Worlds and Maximum Entropy

abstract:
  Given a knowledge base KB containing first-order and statistical facts, we
consider a principled method, called the random-worlds method, for computing a
degree of belief that some formula Phi holds given KB. If we are reasoning
about a world or system consisting of N individuals, then we can consider all
possible worlds, or first-order models, with domain {1,...,N} that satisfy KB,
and compute the fraction of them in which Phi is true. We define the degree of
belief to be the asymptotic value of this fraction as N grows large. We show
that when the vocabulary underlying Phi and KB uses constants and unary
predicates only, we can naturally associate an entropy with each world. As N
grows larger, there are many more worlds with higher entropy. Therefore, we can
use a maximum-entropy computation to compute the degree of belief. This result
is in a similar spirit to previous work in physics and artificial intelligence,
but is far more general. Of equal interest to the result itself are the
limitations on its scope. Most importantly, the restriction to unary predicates
seems necessary. Although the random-worlds method makes sense in general, the
connection to maximum entropy seems to disappear in the non-unary case. These
observations suggest unexpected limitations to the applicability of
maximum-entropy methods.


title:
Pattern Matching and Discourse Processing in Information Extraction from
  Japanese Text

abstract:
  Information extraction is the task of automatically picking up information of
interest from an unconstrained text. Information of interest is usually
extracted in two steps. First, sentence level processing locates relevant
pieces of information scattered throughout the text; second, discourse
processing merges coreferential information to generate the output. In the
first step, pieces of information are locally identified without recognizing
any relationships among them. A key word search or simple pattern search can
achieve this purpose. The second step requires deeper knowledge in order to
understand relationships among separately identified pieces of information.
Previous information extraction systems focused on the first step, partly
because they were not required to link up each piece of information with other
pieces. To link the extracted pieces of information and map them onto a
structured output format, complex discourse processing is essential. This paper
reports on a Japanese information extraction system that merges information
using a pattern matcher and discourse processor. Evaluation results show a high
level of system performance which approaches human performance.


title: A System for Induction of Oblique Decision Trees

abstract:
  This article describes a new system for induction of oblique decision trees.
This system, OC1, combines deterministic hill-climbing with two forms of
randomization to find a good oblique split (in the form of a hyperplane) at
each node of a decision tree. Oblique decision tree methods are tuned
especially for domains in which the attributes are numeric, although they can
be adapted to symbolic or mixed symbolic/numeric attributes. We present
extensive empirical studies, using both real and artificial data, that analyze
OC1's ability to construct oblique trees that are smaller and more accurate
than their axis-parallel counterparts. We also examine the benefits of
randomization for the construction of oblique decision trees.


title: On Planning while Learning

abstract:
  This paper introduces a framework for Planning while Learning where an agent
is given a goal to achieve in an environment whose behavior is only partially
known to the agent. We discuss the tractability of various plan-design
processes. We show that for a large natural class of Planning while Learning
systems, a plan can be presented and verified in a reasonable time. However,
coming up algorithmically with a plan, even for simple classes of systems is
apparently intractable. We emphasize the role of off-line plan-design
processes, and show that, in most natural cases, the verification (projection)
part can be carried out in an efficient algorithmic manner.


title: Wrap-Up: a Trainable Discourse Module for Information Extraction

abstract:
  The vast amounts of on-line text now available have led to renewed interest
in information extraction (IE) systems that analyze unrestricted text,
producing a structured representation of selected information from the text.
This paper presents a novel approach that uses machine learning to acquire
knowledge for some of the higher level IE processing. Wrap-Up is a trainable IE
discourse component that makes intersentential inferences and identifies
logical relations among information extracted from the text. Previous
corpus-based approaches were limited to lower level processing such as
part-of-speech tagging, lexical disambiguation, and dictionary construction.
Wrap-Up is fully trainable, and not only automatically decides what classifiers
are needed, but even derives the feature set for each classifier automatically.
Performance equals that of a partially trainable discourse module requiring
manual customization for each domain.