title: Single-Strip Triangulation of Manifolds with Arbitrary Topology

abstract:
  Triangle strips have been widely used for efficient rendering. It is
NP-complete to test whether a given triangulated model can be represented as a
single triangle strip, so many heuristics have been proposed to partition
models into few long strips. In this paper, we present a new algorithm for
creating a single triangle loop or strip from a triangulated model. Our method
applies a dual graph matching algorithm to partition the mesh into cycles, and
then merges pairs of cycles by splitting adjacent triangles when necessary. New
vertices are introduced at midpoints of edges and the new triangles thus formed
are coplanar with their parent triangles, hence the visual fidelity of the
geometry is not changed. We prove that the increase in the number of triangles
due to this splitting is 50% in the worst case, however for all models we
tested the increase was less than 2%. We also prove tight bounds on the number
of triangles needed for a single-strip representation of a model with holes on
its boundary. Our strips can be used not only for efficient rendering, but also
for other applications including the generation of space filling curves on a
manifold of any arbitrary topology.


title: A Probabilistic Model of Machine Translation

abstract:
  A probabilistic model for computer-based generation of a machine translation
system on the basis of English-Russian parallel text corpora is suggested. The
model is trained using parallel text corpora with pre-aligned source and target
sentences. The training of the model results in a bilingual dictionary of words
and "word blocks" with relevant translation probability.


title: Deductive Algorithmic Knowledge

abstract:
  The framework of algorithmic knowledge assumes that agents use algorithms to
compute the facts they explicitly know. In many cases of interest, a deductive
system, rather than a particular algorithm, captures the formal reasoning used
by the agents to compute what they explicitly know. We introduce a logic for
reasoning about both implicit and explicit knowledge with the latter defined
with respect to a deductive system formalizing a logical theory for agents. The
highly structured nature of deductive systems leads to very natural
axiomatizations of the resulting logic when interpreted over any fixed
deductive system. The decision problem for the logic, in the presence of a
single agent, is NP-complete in general, no harder than propositional logic. It
remains NP-complete when we fix a deductive system that is decidable in
nondeterministic polynomial time. These results extend in a straightforward way
to multiple agents.


title:
Catching the Drift: Probabilistic Content Models, with Applications to
  Generation and Summarization

abstract:
  We consider the problem of modeling the content structure of texts within a
specific domain, in terms of the topics the texts address and the order in
which these topics appear. We first present an effective knowledge-lean method
for learning content models from un-annotated documents, utilizing a novel
adaptation of algorithms for Hidden Markov Models. We then apply our method to
two complementary tasks: information ordering and extractive summarization. Our
experiments show that incorporating content models in these applications yields
substantial improvement over previously-proposed methods.


title: Supervisory Control of Fuzzy Discrete Event Systems

abstract:
  In order to cope with situations in which a plant's dynamics are not
precisely known, we consider the problem of supervisory control for a class of
discrete event systems modelled by fuzzy automata. The behavior of such
discrete event systems is described by fuzzy languages; the supervisors are
event feedback and can disable only controllable events with any degree. The
concept of discrete event system controllability is thus extended by
incorporating fuzziness. In this new sense, we present a necessary and
sufficient condition for a fuzzy language to be controllable. We also study the
supremal controllable fuzzy sublanguage and the infimal controllable fuzzy
superlanguage when a given pre-specified desired fuzzy language is
uncontrollable. Our framework generalizes that of Ramadge-Wonham and reduces to
Ramadge-Wonham framework when membership grades in all fuzzy languages must be
either 0 or 1. The theoretical development is accompanied by illustrative
numerical examples.


title:
The modulus in the CAD system drawings as a base of developing of the
  problem-oriented extensions

abstract:
  The concept of the "modulus" in the CAD system drawings is characterized,
being a base of developing of the problem-oriented extensions. The modulus
consists of visible geometric elements of the drawing and invisible parametric
representation of the modelling object. The technological advantages of
moduluss in a complex CAD system developing are described.


title:
A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor
  Networks

abstract:
  Wireless sensor networks benefit from communication protocols that reduce
power requirements by avoiding frame collision. Time Division Media Access
methods schedule transmission in slots to avoid collision, however these
methods often lack scalability when implemented in \emph{ad hoc} networks
subject to node failures and dynamic topology. This paper reports a distributed
algorithm for TDMA slot assignment that is self-stabilizing to transient faults
and dynamic topology change. The expected local convergence time is O(1) for
any size network satisfying a constant bound on the size of a node
neighborhood.


title:
Prediction with Expert Advice by Following the Perturbed Leader for
  General Weights

abstract:
  When applying aggregating strategies to Prediction with Expert Advice, the
learning rate must be adaptively tuned. The natural choice of
sqrt(complexity/current loss) renders the analysis of Weighted Majority
derivatives quite complicated. In particular, for arbitrary weights there have
been no results proven so far. The analysis of the alternative "Follow the
Perturbed Leader" (FPL) algorithm from Kalai (2003} (based on Hannan's
algorithm) is easier. We derive loss bounds for adaptive learning rate and both
finite expert classes with uniform weights and countable expert classes with
arbitrary weights. For the former setup, our loss bounds match the best known
results so far, while for the latter our results are (to our knowledge) new.


title: Corpus structure, language models, and ad hoc information retrieval

abstract:
  Most previous work on the recently developed language-modeling approach to
information retrieval focuses on document-specific characteristics, and
therefore does not take into account the structure of the surrounding corpus.
We propose a novel algorithmic framework in which information provided by
document-based language models is enhanced by the incorporation of information
drawn from clusters of similar documents. Using this framework, we develop a
suite of new algorithms. Even the simplest typically outperforms the standard
language-modeling approach in precision and recall, and our new interpolation
algorithm posts statistically significant improvements for both metrics over
all three corpora tested.


title:
Culture and International Usability Testing: The Effects of Culture in
  Structured Interviews

abstract:
  The global audience for software products includes members of different
countries, religions, and cultures: people who speak different languages, have
different life styles, and have different perceptions and expectations of any
given product. A major impediment in interface development is that there is
inadequate empirical evidence for the effects of culture in the usability
engineering methods used for developing user interfaces. This paper presents a
controlled study investigating the effects of culture on the effectiveness of
structured interviews in usability testing. The experiment consisted of
usability testing of a website with two independent groups of Indian
participants by two interviewers; one belonging to the Indian culture and the
other to the Anglo-American culture. Participants found more usability problems
and made more suggestions to an interviewer who was a member of the same
(Indian) culture than to the foreign (Anglo-American) interviewer. The results
of the study empirically establish that culture significantly affects the
efficacy of structured interviews during international user testing. The
implications of this work for usability engineering are discussed.


title: Soft Computing Models for Network Intrusion Detection Systems

abstract:
  Security of computers and the networks that connect them is increasingly
becoming of great significance. Computer security is defined as the protection
of computing systems against threats to confidentiality, integrity, and
availability. There are two types of intruders: external intruders, who are
unauthorized users of the machines they attack, and internal intruders, who
have permission to access the system with some restrictions. This chapter
presents a soft computing approach to detect intrusions in a network. Among the
several soft computing paradigms, we investigated fuzzy rule-based classifiers,
decision trees, support vector machines, linear genetic programming and an
ensemble method to model fast and efficient intrusion detection systems.
Empirical results clearly show that soft computing approach could play a major
role for intrusion detection.


title:
Modular technology of developing of the problem-oriented extensions of a
  CAD system of reconstruction of the plant

abstract:
  The modular technology of creation of the problem-oriented extensions of a
CAD system is described, which was realised in a system TechnoCAD GlassX for
designing of reconstruction of the plants. The modularity of the technology is
expressed in storage of all parameters of the design in one element of the
drawing - modulus, with automatic generation of a geometrical part of the
modulus from these parameters. The common principles of the system organization
of extensions developing are described: separation of the part of the design to
automize in this extension, architecture of parameters in the form of the lists
of objects with their properties and links to another objects, separation of
common and special operations, stages of the developing, boundaries of
applicability of technology.


title:
Interactive visualization of higher dimensional data in a multiview
  environment

abstract:
  We develop multiple view visualization of higher dimensional data. Our work
was chiefly motivated by the need to extract insight from four dimensional
Quantum Chromodynamic (QCD) data. We develop visualization where multiple
views, generally views of 3D projections or slices of a higher dimensional
data, are tightly coupled not only by their specific order but also by a view
synchronizing interaction style, and an internally defined interaction
language. The tight coupling of the different views allows a fast and
well-coordinated exploration of the data. In particular, the visualization
allowed us to easily make consistency checks of the 4D QCD data and to infer
the correctness of particle properties calculations. The software developed was
also successfully applied in material studies, in particular studies of
meteorite properties. Our implementation uses the VTK API. To handle a large
number of views (slices/projections) and to still maintain good resolution, we
use IBM T221 display (3840 X 2400 pixels).


title: Export Behaviour Modeling Using EvoNF Approach

abstract:
  The academic literature suggests that the extent of exporting by
multinational corporation subsidiaries (MCS) depends on their product
manufactured, resources, tax protection, customers and markets, involvement
strategy, financial independence and suppliers' relationship with a
multinational corporation (MNC). The aim of this paper is to model the complex
export pattern behaviour using a Takagi-Sugeno fuzzy inference system in order
to determine the actual volume of MCS export output (sales exported). The
proposed fuzzy inference system is optimised by using neural network learning
and evolutionary computation. Empirical results clearly show that the proposed
approach could model the export behaviour reasonable well compared to a direct
neural network approach.


title: Traffic Accident Analysis Using Decision Trees and Neural Networks

abstract:
  The costs of fatalities and injuries due to traffic accident have a great
impact on society. This paper presents our research to model the severity of
injury resulting from traffic accidents using artificial neural networks and
decision trees. We have applied them to an actual data set obtained from the
National Automotive Sampling System (NASS) General Estimates System (GES).
Experiment results reveal that in all the cases the decision tree outperforms
the neural network. Our research analysis also shows that the three most
important factors in fatal injury are: driver's seat belt usage, light
condition of the roadway, and driver's alcohol usage.


title:
Short Term Load Forecasting Models in Czech Republic Using Soft
  Computing Paradigms

abstract:
  This paper presents a comparative study of six soft computing models namely
multilayer perceptron networks, Elman recurrent neural network, radial basis
function network, Hopfield model, fuzzy inference system and hybrid fuzzy
neural network for the hourly electricity demand forecast of Czech Republic.
The soft computing models were trained and tested using the actual hourly load
data for seven years. A comparison of the proposed techniques is presented for
predicting 2 day ahead demands for electricity. Simulation results indicate
that hybrid fuzzy neural network and radial basis function networks are the
best candidates for the analysis and forecasting of electricity demand.


title: Decision Support Systems Using Intelligent Paradigms

abstract:
  Decision-making is a process of choosing among alternative courses of action
for solving complicated problems where multi-criteria objectives are involved.
The past few years have witnessed a growing recognition of Soft Computing (SC)
technologies that underlie the conception, design and utilization of
intelligent systems. In this paper, we present different SC paradigms involving
an artificial neural network trained using the scaled conjugate gradient
algorithm, two different fuzzy inference methods optimised using neural network
learning/evolutionary algorithms and regression trees for developing
intelligent decision support systems. We demonstrate the efficiency of the
different algorithms by developing a decision support system for a Tactical Air
Combat Environment (TACE). Some empirical comparisons between the different
algorithms are also provided.


title: Synchronous Relaxation for Parallel Ising Spin Simulations

abstract:
  A new parallel algorithm for simulating Ising spin systems is presented. The
sequential prototype is the n-fold way algorithm cite{BKL75}, which is
efficient but is hard to parallelize using conservative methods. Our parallel
algorithm is optimistic. Unlike other optimistic algorithms, e.g., Time Warp,
our algorithm is synchronous. It also belongs to the class of simulations known
as ``relaxation'' cite{CS8 hence it is named ``synchronous relaxation.'' We
derive performance guarantees for this algorithm. If N is the number of PEs,
then under weak assumptions we show that the number of correct events processed
per unit of time is, on average, at least of order N/log(N). All communication
delays, processing time, and busy waits are taken into account.

categories: cs.DC cond-mat.mtrl-sci cs.DS physics.comp-ph


title:
The model of the tables in design documentation for operating with the
  electronic catalogs and for specifications making in a CAD system

abstract:
  The hierarchic block model of the tables in design documentation as a part of
a CAD system is described, intended for automatic specifications making of
elements of the drawings, with usage of the electronic catalogs. The model is
created for needs of a CAD system of reconstruction of the industrial plants,
where the result of designing are the drawings, which include the
specifications of different types. The adequate simulation of the specification
tables is ensured with technology of storing in the drawing of the visible
geometric elements and invisible parametric representation, sufficient for
generation of this elements.


title:
Modular technology of developing of the extensions of a CAD system.
  Axonometric piping diagrams. Parametric representation

abstract:
  Applying the modular technology of developing of the problem-oriented
extensions of a CAD system to a problem of automation of creating of the
axonometric piping diagrams on an example of the program system TechnoCAD
GlassX is described. The proximity of composition of the schemas is detected
for special technological pipe lines, systems of a water line and water drain,
heating, heat supply, ventilating, air conditioning. The structured parametric
representation of the schemas, including properties of objects, their link,
common settings, settings by default and the special links of compatibility is
reviewed.


title:
Modular technology of developing of the extensions of a CAD system. The
  axonometric piping diagrams. Common and special operations

abstract:
  Applying the modular technology of developing of the problem-oriented
extensions of a CAD system to a problem of automation of creating of the
axonometric piping diagrams on an example of the program system TechnoCAD
GlassX is described. The features of realization of common operations,
composition and realization of special operations of a designing of the schemas
of the special technological pipe lines, systems of a water line and water
drain, heating, heat supply, ventilating, air conditioning are reviewed.


title:
Mathematical and programming toolkit of the computer aided design of the
  axonometric piping diagrams

abstract:
  The problem of the automation of the designing of the axonometric piping
diagrams include, as the minimum, manipulations with the flat schemas of
three-dimensional wireframe objects (with dimension of 2,5). The specialized
model, methodical and mathematical approaches are required because of large
bulk of calculuss. Coordinate systems, data types, common principles of
realization of operation with data and composition of the basic operations are
described which are realised in the complex CAD system of the reconstruction of
the plants TechnoCAD GlassX.


title: Neighborhood-Based Topology Recognition in Sensor Networks

abstract:
  We consider a crucial aspect of self-organization of a sensor network
consisting of a large set of simple sensor nodes with no location hardware and
only very limited communication range. After having been distributed randomly
in a given two-dimensional region, the nodes are required to develop a sense
for the environment, based on a limited amount of local communication. We
describe algorithmic approaches for determining the structure of boundary nodes
of the region, and the topology of the region. We also develop methods for
determining the outside boundary, the distance to the closest boundary for each
point, the Voronoi diagram of the different boundaries, and the geometric
thickness of the network. Our methods rely on a number of natural assumptions
that are present in densely distributed sets of nodes, and make use of a
combination of stochastics, topology, and geometry. Evaluation requires only a
limited number of simple local computations.


title: Erratum : MCColor is not optimal on Meyniel graphs

abstract:
  A Meyniel graph is a graph in which every odd cycle of length at least five
has two chords. In the manuscript "Coloring Meyniel graphs in linear time" we
claimed that our algorithm MCColor produces an optimal coloring for every
Meyniel graph. But later we found a mistake in the proof and a couterexample to
the optimality, which we present here. MCColor can still be used to find a
stable set that intersects all maximal cliques of a Meyniel graph in linear
time. Consequently it can be used to find an optimal coloring in time O(nm),
and the same holds for Algorithm MCS+Color. This is explained in the manuscript
"A linear algorithm to find a strong stable set in a Meyniel graph" but this is
equivalent to Hertz's algorithm. The current best algorithm for coloring
Meyniel graphs is the O(n^2) algorithm LexColor due to Roussel and Rusu. The
question of finding a linear-time algorithm to color Meyniel graphs is still
open.


title:
An unexpected application of minimization theory to module
  decompositions

abstract:
  The aim of this work is to show how we can decompose a module (if
decomposable) into an indecomposable module with the help of the minimization
process.


title: Jigsaw-based Security in Data Transfer in Computer Networks

abstract:
  In this paper, we present a novel encryption-less algorithm to enhance
security in transmission of data in networks. The algorithm uses an intuitively
simple idea of a 'jigsaw puzzle' to break the transformed data into multiple
parts where these parts form the pieces of the puzzle. Then these parts are
packaged into packets and sent to the receiver. A secure and efficient
mechanism is provided to convey the information that is necessary for obtaining
the original data at the receiver-end from its parts in the packets, that is,
for solving the 'jigsaw puzzle'. The algorithm is designed to provide
information-theoretic (that is, unconditional) security by the use of a
one-time pad like scheme so that no intermediate or unintended node can obtain
the entire data. An authentication code is also used to ensure authenticity of
every packet.


title:
Efficiency Enhancement of Probabilistic Model Building Genetic
  Algorithms

abstract:
  This paper presents two different efficiency-enhancement techniques for
probabilistic model building genetic algorithms. The first technique proposes
the use of a mutation operator which performs local search in the sub-solution
neighborhood identified through the probabilistic model. The second technique
proposes building and using an internal probabilistic model of the fitness
along with the probabilistic model of variable interactions. The fitness values
of some offspring are estimated using the probabilistic model, thereby avoiding
computationally expensive function evaluations. The scalability of the
aforementioned techniques are analyzed using facetwise models for convergence
time and population sizing. The speed-up obtained by each of the methods is
predicted and verified with empirical results. The results show that for
additively separable problems the competent mutation operator requires O(k 0.5
logm)--where k is the building-block size, and m is the number of building
blocks--less function evaluations than its selectorecombinative counterpart.
The results also show that the use of an internal probabilistic fitness model
reduces the required number of function evaluations to as low as 1-10% and
yields a speed-up of 2--50.


title: Let's Get Ready to Rumble: Crossover Versus Mutation Head to Head

abstract:
  This paper analyzes the relative advantages between crossover and mutation on
a class of deterministic and stochastic additively separable problems. This
study assumes that the recombination and mutation operators have the knowledge
of the building blocks (BBs) and effectively exchange or search among competing
BBs. Facetwise models of convergence time and population sizing have been used
to determine the scalability of each algorithm. The analysis shows that for
additively separable deterministic problems, the BB-wise mutation is more
efficient than crossover, while the crossover outperforms the mutation on
additively separable problems perturbed with additive Gaussian noise. The
results show that the speed-up of using BB-wise mutation on deterministic
problems is O(k^{0.5}logm), where k is the BB size, and m is the number of BBs.
Likewise, the speed-up of using crossover on stochastic problems with fixed
noise variance is O(mk^{0.5}log m).


title:
Designing Competent Mutation Operators via Probabilistic Model Building
  of Neighborhoods

abstract:
  This paper presents a competent selectomutative genetic algorithm (GA), that
adapts linkage and solves hard problems quickly, reliably, and accurately. A
probabilistic model building process is used to automatically identify key
building blocks (BBs) of the search problem. The mutation operator uses the
probabilistic model of linkage groups to find the best among competing building
blocks. The competent selectomutative GA successfully solves additively
separable problems of bounded difficulty, requiring only subquadratic number of
function evaluations. The results show that for additively separable problems
the probabilistic model building BB-wise mutation scales as O(2^km^{1.5}), and
requires O(k^{0.5}logm) less function evaluations than its selectorecombinative
counterpart, confirming theoretical results reported elsewhere (Sastry &
Goldberg, 2004).


title:
Efficiency Enhancement of Genetic Algorithms via Building-Block-Wise
  Fitness Estimation

abstract:
  This paper studies fitness inheritance as an efficiency enhancement technique
for a class of competent genetic algorithms called estimation distribution
algorithms. Probabilistic models of important sub-solutions are developed to
estimate the fitness of a proportion of individuals in the population, thereby
avoiding computationally expensive function evaluations. The effect of fitness
inheritance on the convergence time and population sizing are modeled and the
speed-up obtained through inheritance is predicted. The results show that a
fitness-inheritance mechanism which utilizes information on building-block
fitnesses provides significant efficiency enhancement. For additively separable
problems, fitness inheritance reduces the number of function evaluations to
about half and yields a speed-up of about 1.75--2.25.


title: A Logic for Reasoning about Digital Rights

abstract:
  We present a logic for reasoning about licenses, which are ``terms of use''
for digital resources. The logic provides a language for writing both
properties of licenses and specifications that govern a client's actions. We
discuss the complexity of checking properties and specifications written in our
logic and propose a technique for verification. A key feature of our approach
is that it is essentially parameterized by the language in which the licenses
are written, provided that this language can be given a trace-based semantics.
We consider two license languages to illustrate this flexibility.


title: Note on Counting Eulerian Circuits

abstract:
  We show that the problem of counting the number of Eulerian circuits in an
undirected graph is complete for the class #P.


title: Observability and Decentralized Control of Fuzzy Discrete Event Systems

abstract:
  Fuzzy discrete event systems as a generalization of (crisp) discrete event
systems have been introduced in order that it is possible to effectively
represent uncertainty, imprecision, and vagueness arising from the dynamic of
systems. A fuzzy discrete event system has been modelled by a fuzzy automaton;
its behavior is described in terms of the fuzzy language generated by the
automaton. In this paper, we are concerned with the supervisory control problem
for fuzzy discrete event systems with partial observation. Observability,
normality, and co-observability of crisp languages are extended to fuzzy
languages. It is shown that the observability, together with controllability,
of the desired fuzzy language is a necessary and sufficient condition for the
existence of a partially observable fuzzy supervisor. When a decentralized
solution is desired, it is proved that there exist local fuzzy supervisors if
and only if the fuzzy language to be synthesized is controllable and
co-observable. Moreover, the infimal controllable and observable fuzzy
superlanguage, and the supremal controllable and normal fuzzy sublanguage are
also discussed. Simple examples are provided to illustrate the theoretical
development.


title: Mining Frequent Itemsets from Secondary Memory

abstract:
  Mining frequent itemsets is at the core of mining association rules, and is
by now quite well understood algorithmically. However, most algorithms for
mining frequent itemsets assume that the main memory is large enough for the
data structures used in the mining, and very few efficient algorithms deal with
the case when the database is very large or the minimum support is very low.
Mining frequent itemsets from a very large database poses new challenges, as
astronomical amounts of raw data is ubiquitously being recorded in commerce,
science and government. In this paper, we discuss approaches to mining frequent
itemsets when data structures are too large to fit in main memory. Several
divide-and-conquer algorithms are given for mining from disks. Many novel
techniques are introduced. Experimental results show that the techniques reduce
the required disk accesses by orders of magnitude, and enable truly scalable
data mining.


title: Traffic-driven model of the World Wide Web graph

abstract:
  We propose a model for the World Wide Web graph that couples the topological
growth with the traffic's dynamical evolution. The model is based on a simple
traffic-driven dynamics and generates weighted directed graphs exhibiting the
statistical properties observed in the Web. In particular, the model yields a
non-trivial time evolution of vertices and heavy-tail distributions for the
topological and traffic properties. The generated graphs exhibit a complex
architecture with a hierarchy of cohesiveness levels similar to those observed
in the analysis of real data.


title: Regression with respect to sensing actions and partial states

abstract:
  In this paper, we present a state-based regression function for planning
domains where an agent does not have complete information and may have sensing
actions. We consider binary domains and employ the 0-approximation [Son & Baral
2001] to define the regression function. In binary domains, the use of
0-approximation means using 3-valued states. Although planning using this
approach is incomplete with respect to the full semantics, we adopt it to have
a lower complexity. We prove the soundness and completeness of our regression
formulation with respect to the definition of progression. More specifically,
we show that (i) a plan obtained through regression for a planning problem is
indeed a progression solution of that planning problem, and that (ii) for each
plan found through progression, using regression one obtains that plan or an
equivalent one. We then develop a conditional planner that utilizes our
regression function. We prove the soundness and completeness of our planning
algorithm and present experimental results with respect to several well known
planning problems in the literature.


title: Grid Databases for Shared Image Analysis in the MammoGrid Project

abstract:
  The MammoGrid project aims to prove that Grid infrastructures can be used for
collaborative clinical analysis of database-resident but geographically
distributed medical images. This requires: a) the provision of a
clinician-facing front-end workstation and b) the ability to service real-world
clinician queries across a distributed and federated database. The MammoGrid
project will prove the viability of the Grid by harnessing its power to enable
radiologists from geographically dispersed hospitals to share standardized
mammograms, to compare diagnoses (with and without computer aided detection of
tumours) and to perform sophisticated epidemiological studies across national
boundaries. This paper outlines the approach taken in MammoGrid to seamlessly
connect radiologist workstations across a Grid using an "information
infrastructure" and a DICOM-compliant object model residing in multiple
distributed data stores in Italy and the UK


title: Advanced exploitation of buffer overflow

abstract:
  This article describes in depth several ways of exploiting buffer overflows
in the UNIX operating systems.


title:
MammoGrid: A Service Oriented Architecture based Medical Grid
  Application

abstract:
  The MammoGrid project has recently delivered its first proof-of-concept
prototype using a Service-Oriented Architecture (SOA)-based Grid application to
enable distributed computing spanning national borders. The underlying AliEn
Grid infrastructure has been selected because of its practicality and because
of its emergence as a potential open source standards-based solution for
managing and coordinating distributed resources. The resultant prototype is
expected to harness the use of huge amounts of medical image data to perform
epidemiological studies, advanced image processing, radiographic education and
ultimately, tele-diagnosis over communities of medical virtual organisations.
The MammoGrid prototype comprises a high-quality clinician visualization
workstation used for data acquisition and inspection, a DICOM-compliant
interface to a set of medical services (annotation, security, image analysis,
data storage and querying services) residing on a so-called Grid-box and secure
access to a network of other Grid-boxes connected through Grid middleware. This
paper outlines the MammoGrid approach in managing a federation of
Grid-connected mammography databases in the context of the recently delivered
prototype and will also describe the next phase of prototyping.


title:
Reduction Strategies in Lambda Term Normalization and their Effects on
  Heap Usage

abstract:
  Higher-order representations of objects such as programs, proofs, formulas
and types have become important to many symbolic computation tasks. Systems
that support such representations usually depend on the implementation of an
intensional view of the terms of some variant of the typed lambda-calculus.
Various notations have been proposed for lambda-terms to explicitly treat
substitutions as basis for realizing such implementations. There are, however,
several choices in the actual reduction strategies. The most common strategy
utilizes such notations only implicitly via an incremental use of environments.
This approach does not allow the smaller substitution steps to be intermingled
with other operations of interest on lambda-terms. However, a naive strategy
explicitly using such notations can also be costly: each use of the
substitution propagation rules causes the creation of a new structure on the
heap that is often discarded in the immediately following step. There is thus a
tradeoff between these two approaches. This thesis describes the actual
realization of the two approaches, discusses their tradeoffs based on this and,
finally, offers an amalgamated approach that utilizes recursion in rewrite rule
application but also suspends substitution operations where necessary.


title: An Abductive Framework For Computing Knowledge Base Updates

abstract:
  This paper introduces an abductive framework for updating knowledge bases
represented by extended disjunctive programs. We first provide a simple
transformation from abductive programs to update programs which are logic
programs specifying changes on abductive hypotheses. Then, extended abduction,
which was introduced by the same authors as a generalization of traditional
abduction, is computed by the answer sets of update programs. Next, different
types of updates, view updates and theory updates are characterized by
abductive programs and computed by update programs. The task of consistency
restoration is also realized as special cases of these updates. Each update
problem is comparatively assessed from the computational complexity viewpoint.
The result of this paper provides a uniform framework for different types of
knowledge base updates, and each update is computed using existing procedures
of logic programming.


title: Fast Simulation of Multicomponent Dynamic Systems

abstract:
  A computer simulation has to be fast to be helpful, if it is employed to
study the behavior of a multicomponent dynamic system. This paper discusses
modeling concepts and algorithmic techniques useful for creating such fast
simulations. Concrete examples of simulations that range from econometric
modeling to communications to material science are used to illustrate these
techniques and concepts. The algorithmic and modeling methods discussed include
event-driven processing, ``anticipating'' data structures, and ``lazy''
evaluation, Poisson dispenser, parallel processing by cautious advancements and
by synchronous relaxations. The paper gives examples of how these techniques
and models are employed in assessing efficiency of capacity management methods
in wireless and wired networks, in studies of magnetization, crystalline
structure, and sediment formation in material science, in studies of
competition in economics.


title: Generative Programming of Graphical User Interfaces

abstract:
  Generative Programming (GP) is a computing paradigm allowing automatic
creation of entire software families utilizing the configuration of elementary
and reusable components. GP can be projected on different technologies, e.g.
C++-templates, Java-Beans, Aspect-Oriented Programming (AOP), or Frame
technology. This paper focuses on Frame Technology, which aids the possible
implementation and completion of software components. The purpose of this paper
is to introduce the GP paradigm in the area of GUI application generation. It
demonstrates how automatically customized executable applications with GUI
parts can be generated from an abstract specification.


title: Higher-Order Concurrent Win32 Programming

abstract:
  We present a concurrent framework for Win32 programming based on Concurrent
ML, a concurrent language with higher-order functions, static typing,
lightweight threads and synchronous communication channels. The key points of
the framework are the move from an event loop model to a threaded model for the
processing of window messages, and the decoupling of controls notifications
from the system messages. This last point allows us to derive a general way of
writing controls that leads to easy composition, and can accommodate ActiveX
Controls in a transparent way.


title: Reactive Programming in Standard ML

abstract:
  Reactive systems are systems that maintain an ongoing interaction with their
environment, activated by receiving input events from the environment and
producing output events in response. Modern programming languages designed to
program such systems use a paradigm based on the notions of instants and
activations. We describe a library for Standard ML that provides basic
primitives for programming reactive systems. The library is a low-level system
upon which more sophisticated reactive behaviors can be built, which provides a
convenient framework for prototyping extensions to existing reactive languages.


title: An Analysis of Lambek's Production Machines

abstract:
  Lambek's production machines may be used to generate and recognize sentences
in a subset of the language described by a production grammar. We determine in
this paper the subset of the language of a grammar generated and recognized by
such machines.


title:
Aspects de la Programmation d'Applications Win32 avec un Langage
  Fonctionnel

abstract:
  A useful programming language needs to support writing programs that take
advantage of services and communication mechanisms supplied by the operating
system. We examine the problem of programming native Win32 applications under
Windows with Standard ML. We introduce an framework based on the IDL interface
language et a minimal foreign-functions interface to explore the Win32 API et
COM in the context of Standard ML.


title: The Design of a COM-Oriented Module System

abstract:
  We present in this paper the preliminary design of a module system based on a
notion of components such as they are found in COM. This module system is
inspired from that of Standard ML, and features first-class instances of
components, first-class interfaces, and interface-polymorphic functions, as
well as allowing components to be both imported from the environment and
exported to the environment using simple mechanisms. The module system
automates the memory management of interfaces and hides the IUnknown interface
and QueryInterface mechanisms from the programmer, favoring instead a
higher-level approach to handling interfaces.


title: A Framework for Interoperability

abstract:
  Practical implementations of high-level languages must provide access to
libraries and system services that have APIs specified in a low-level language
(usually C). An important characteristic of such mechanisms is the
foreign-interface policy that defines how to bridge the semantic gap between
the high-level language and C. For example, IDL-based tools generate code to
marshal data into and out of the high-level representation according to user
annotations. The design space of foreign-interface policies is large and there
are pros and cons to each approach. Rather than commit to a particular policy,
we choose to focus on the problem of supporting a gamut of interoperability
policies. In this paper, we describe a framework for language interoperability
that is expressive enough to support very efficient implementations of a wide
range of different foreign-interface policies. We describe two tools that
implement substantially different policies on top of our framework and present
benchmarks that demonstrate their efficiency.


title: On the Expressive Power of First-Order Boolean Functions in PCF

abstract:
  Recent results of Bucciarelli show that the semilattice of degrees of
parallelism of first-order boolean functions in PCF has both infinite chains
and infinite antichains. By considering a simple subclass of Sieber's
sequentiality relations, we identify levels in the semilattice and derive
inexpressibility results concerning functions on different levels. This allows
us to further explore the structure of the semilattice of degrees of
parallelism: we identify semilattices characterized by simple level properties,
and show the existence of new infinite hierarchies which are in a certain sense
natural with respect to the levels.


title:
A New Dynamical Domain Decomposition Method for Parallel Molecular
  Dynamics Simulation on Grid

abstract:
  We develop a new Lagrangian material particle -- dynamical domain
decomposition method (MPD^3) for large scale parallel molecular dynamics (MD)
simulation of nonstationary heterogeneous systems on a heterogeneous computing
net. MPD^3 is based on Voronoi decomposition of simulated matter. The map of
Voronoi polygons is known as the Dirichlet tessellation and used for grid
generation in computational fluid dynamics. From the hydrodynamics point of
view the moving Voronoi polygon looks as a material particle (MP). MPs can
exchange particles and information. To balance heterogeneous computing
conditions the MP centers should be dependent on timing data. We propose a
simple and efficient iterative algorithm which based on definition of the
timing-dependent balancing displacement of MP center for next simulation step.
  The MPD^3 program was tested in various computing environments and physical
problems. We have demonstrated that MPD^3 is a high-adaptive decomposition
algorithm for MD simulation. It was shown that the well-balanced decomposition
can result from dynamical Voronoi polygon tessellation. One would expect the
similar approach can be successfully applied for other particle methods like
Monte Carlo, particle-in-cell, and smooth-particle-hydrodynamics.


title: A Grid Information Infrastructure for Medical Image Analysis

abstract:
  The storage and manipulation of digital images and the analysis of the
information held in those images are essential requirements for next-generation
medical information systems. The medical community has been exploring
collaborative approaches for managing image data and exchanging knowledge and
Grid technology [1] is a promising approach to enabling distributed analysis
across medical institutions and for developing new collaborative and
cooperative approaches for image analysis without the necessity for clinicians
to co-locate. The EU-funded MammoGrid project [2] is one example of this and it
aims to develop a Europe-wide database of mammograms to support effective
co-working between healthcare professionals across the EU. The MammoGrid
prototype comprises a high-quality clinician visualization workstation (for
data acquisition and inspection), a DICOM-compliant interface to a set of
medical services (annotation, security, image analysis, data storage and
querying services) residing on a so-called Grid-box and secure access to a
network of other Grid-boxes connected through Grid middleware. One of the main
deliverables of the project is a Grid-enabled infrastructure that manages
federated mammogram databases across Europe. This paper outlines the MammoGrid
Information Infrastructure (MII) for meta-data analysis and knowledge discovery
in the medical imaging domain.


title: High-Level Networking With Mobile Code And First Order AND-Continuations

abstract:
  We describe a scheme for moving living code between a set of distributed
processes coordinated with unification based Linda operations, and its
application to building a comprehensive Logic programming based Internet
programming framework. Mobile threads are implemented by capturing first order
continuations in a compact data structure sent over the network. Code is
fetched lazily from its original base turned into a server as the continuation
executes at the remote site. Our code migration techniques, in combination with
a dynamic recompilation scheme, ensure that heavily used code moves up smoothly
on a speed hierarchy while volatile dynamic code is kept in a quickly updatable
form. Among the examples, we describe how to build programmable client and
server components (Web servers, in particular) and mobile agents.


title: Convex Hull of Planar H-Polyhedra

abstract:
  Suppose $<A_i, \vec{c}_i>$ are planar (convex) H-polyhedra, that is, $A_i \in
\mathbb{R}^{n_i \times 2}$ and $\vec{c}_i \in \mathbb{R}^{n_i}$. Let $P_i =
\{\vec{x} \in \mathbb{R}^2 \mid A_i\vec{x} \leq \vec{c}_i \}$ and $n = n_1 +
n_2$. We present an $O(n \log n)$ algorithm for calculating an H-polyhedron
$<A, \vec{c}>$ with the smallest $P = \{\vec{x} \in \mathbb{R}^2 \mid A\vec{x}
\leq \vec{c} \}$ such that $P_1 \cup P_2 \subseteq P$.


title: Propositional Defeasible Logic has Linear Complexity

abstract:
  Defeasible logic is a rule-based nonmonotonic logic, with both strict and
defeasible rules, and a priority relation on rules. We show that inference in
the propositional form of the logic can be performed in linear time. This
contrasts markedly with most other propositional nonmonotonic logics, in which
inference is intractable.


title: CLAIRE: Combining Sets, Search And Rules To Better Express Algorithms

abstract:
  This paper presents a programming language which includes paradigms that are
usually associated with declarative languages, such as sets, rules and search,
into an imperative (functional) language. Although these paradigms are
separately well known and are available under various programming environments,
the originality of the CLAIRE language comes from the tight integration, which
yields interesting run-time performances, and from the richness of this
combination, which yields new ways in which to express complex algorithmic
patterns with few elegant lines. To achieve the opposite goals of a high
abstraction level (conciseness and readability) and run-time performance
(CLAIRE is used as a C++ preprocessor), we have developed two kinds of
compiler: first, a pattern pre-processor handles iterations over both concrete
and abstract sets (data types and program fragments), in a completely
user-extensible manner; secondly, an inference compiler transforms a set of
logical rules into a set of functions (demons that are used through procedural
attachment).


title: Learning Hybrid Algorithms for Vehicle Routing Problems

abstract:
  This paper presents a generic technique for improving hybrid algorithms
through the discovery of and tuning of meta-heuristics. The idea is to
represent a family of push/pull heuristics that are based upon inserting and
removing tasks in a current solution, with an algebra. We then let a learning
algorithm search for the best possible algebraic term, which represents a
hybrid algorithm for a given set of problems and an optimization criterion. In
a previous paper, we described this algebra in detail and provided a set of
preliminary results demonstrating the utility of this approach, using vehicle
routing with time windows (VRPTW) as a domain example. In this paper we expand
upon our results providing a more robust experimental framework and learning
algorithms, and report on some new results using the standard Solomon
benchmarks. In particular, we show that our learning algorithm is able to
achieve results similar to the best-published algorithms using only a fraction
of the CPU time. We also show that the automatic tuning of the best hybrid
combination of such techniques yields a better solution than hand tuning, with
considerably less effort.


title: Computerized Face Detection and Recognition

abstract:
  This publication presents methods for face detection, analysis and
recognition: fast normalized cross-correlation (fast correlation coefficient)
between multiple templates based face pre-detection method, method for
detection of exact face contour based on snakes and Generalized Gradient Vector
Flow field, method for combining recognition algorithms based on Cumulative
Match Characteristics in order to increase recognition speed and accuracy, and
face recognition method based on Principal Component Analysis of the Wavelet
Packet Decomposition allowing to use PCA - based recognition method with large
number of training images. For all the methods are presented experimental
results and comparisons of speed and accuracy with large face databases.


title:
The Complexity of Maximum Matroid-Greedoid Intersection and Weighted
  Greedoid Maximization

abstract:
  The maximum intersection problem for a matroid and a greedoid, given by
polynomial-time oracles, is shown $NP$-hard by expressing the satisfiability of
boolean formulas in 3-conjunctive normal form as such an intersection. The
corresponding approximation problems are shown $NP$-hard for certain
approximation performance bounds. Moreover, some natural parameterized variants
of the problem are shown $W[P]$-hard. The results are in contrast with the
maximum matroid-matroid intersection which is solvable in polynomial time by an
old result of Edmonds. We also prove that it is $NP$-hard to approximate the
weighted greedoid maximization within $2^{n^{O(1)}}$ where $n$ is the size of
the domain of the greedoid.
  A preliminary version ``The Complexity of Maximum Matroid-Greedoid
Intersection'' appeared in Proc. FCT 2001, LNCS 2138, pp. 535--539,
Springer-Verlag 2001.


title: Blind Detection and Compensation of Camera Lens Geometric Distortions

abstract:
  This paper presents a blind detection and compensation technique for camera
lens geometric distortions. The lens distortion introduces higher-order
correlations in the frequency domain and in turn it can be detected using
higher-order spectral analysis tools without assuming any specific calibration
target. The existing blind lens distortion removal method only considered a
single-coefficient radial distortion model. In this paper, two coefficients are
considered to model approximately the geometric distortion. All the models
considered have analytical closed-form inverse formulae.


title:
Developing Intellectual Network Management Facilities by Means of
  Pattern Recognition Theory

abstract:
  In this paper considered question of using pattern recognition methods in
network equipment state identification.


title: A Coalgebraic Approach to Kleene Algebra with Tests

abstract:
  Kleene algebra with tests is an extension of Kleene algebra, the algebra of
regular expressions, which can be used to reason about programs. We develop a
coalgebraic theory of Kleene algebra with tests, along the lines of the
coalgebraic theory of regular expressions based on deterministic automata.
Since the known automata-theoretic presentation of Kleene algebra with tests
does not lend itself to a coalgebraic theory, we define a new interpretation of
Kleene algebra with tests expressions and a corresponding automata-theoretic
presentation. One outcome of the theory is a coinductive proof principle, that
can be used to establish equivalence of our Kleene algebra with tests
expressions.


title: A Logic for Reasoning about Evidence

abstract:
  We introduce a logic for reasoning about evidence that essentially views
evidence as a function from prior beliefs (before making an observation) to
posterior beliefs (after making the observation). We provide a sound and
complete axiomatization for the logic, and consider the complexity of the
decision problem. Although the reasoning in the logic is mainly propositional,
we allow variables representing numbers and quantification over them. This
expressive power seems necessary to capture important properties of evidence.


title: Web search engine based on DNS

abstract:
  Now no web search engine can cover more than 60 percent of all the pages on
Internet. The update interval of most pages database is almost one month. This
condition hasn't changed for many years. Converge and recency problems have
become the bottleneck problem of current web search engine. To solve these
problems, a new system, search engine based on DNS is proposed in this paper.
This system adopts the hierarchical distributed architecture like DNS, which is
different from any current commercial search engine. In theory, this system can
cover all the web pages on Internet. Its update interval could even be one day.
The original idea, detailed content and implementation of this system all are
introduced in this paper.


title: Typing constraint logic programs

abstract:
  We present a prescriptive type system with parametric polymorphism and
subtyping for constraint logic programs. The aim of this type system is to
detect programming errors statically. It introduces a type discipline for
constraint logic programs and modules, while maintaining the capabilities of
performing the usual coercions between constraint domains, and of typing
meta-programming predicates, thanks to the flexibility of subtyping. The
property of subject reduction expresses the consistency of a prescriptive type
system w.r.t. the execution model: if a program is "well-typed", then all
derivations starting from a "well-typed" goal are again "well-typed". That
property is proved w.r.t. the abstract execution model of constraint
programming which proceeds by accumulation of constraints only, and w.r.t. an
enriched execution model with type constraints for substitutions. We describe
our implementation of the system for type checking and type inference. We
report our experimental results on type checking ISO-Prolog, the (constraint)
libraries of Sicstus Prolog and other Prolog programs.


title: Worst-Case Groundness Analysis Using Definite Boolean Functions

abstract:
  This note illustrates theoretical worst-case scenarios for groundness
analyses obtained through abstract interpretation over the abstract domains of
definite (Def) and positive (Pos) Boolean functions. For Def, an example is
given for which any Def-based abstract interpretation for groundness analysis
follows a chain which is exponential in the number of argument positions as
well as in the number of clauses but sub-exponential in the size of the
program. For Pos, we strengthen a previous result by illustrating an example
for which any Pos-based abstract interpretation for groundness analysis follows
a chain which is exponential in the size of the program. It remains an open
problem to determine if the worst case for Def is really as bad as that for
Pos.


title: A Proof Theoretic Approach to Failure in Functional Logic Programming

abstract:
  How to extract negative information from programs is an important issue in
logic programming. Here we address the problem for functional logic programs,
from a proof-theoretic perspective. The starting point of our work is CRWL
(Constructor based ReWriting Logic), a well established theoretical framework
for functional logic programming, whose fundamental notion is that of
non-strict non-deterministic function. We present a proof calculus, CRWLF,
which is able to deduce negative information from CRWL-programs. In particular,
CRWLF is able to prove finite failure of reduction within CRWL.


title: On model checking data-independent systems with arrays without reset

abstract:
  A system is data-independent with respect to a data type X iff the operations
it can perform on values of type X are restricted to just equality testing. The
system may also store, input and output values of type X. We study model
checking of systems which are data-independent with respect to two distinct
type variables X and Y, and may in addition use arrays with indices from X and
values from Y . Our main interest is the following parameterised model-checking
problem: whether a given program satisfies a given temporal-logic formula for
all non-empty nite instances of X and Y . Initially, we consider instead the
abstraction where X and Y are infinite and where partial functions with finite
domains are used to model arrays. Using a translation to data-independent
systems without arrays, we show that the u-calculus model-checking problem is
decidable for these systems. From this result, we can deduce properties of all
systems with finite instances of X and Y . We show that there is a procedure
for the above parameterised model-checking problem of the universal fragment of
the u-calculus, such that it always terminates but may give false negatives. We
also deduce that the parameterised model-checking problem of the universal
disjunction-free fragment of the u-calculus is decidable. Practical motivations
for model checking data-independent systems with arrays include verification of
memory and cache systems, where X is the type of memory addresses, and Y the
type of storable values. As an example we verify a fault-tolerant memory
interface over a set of unreliable memories.


title: Knowledge Reduction and Discovery based on Demarcation Information

abstract:
  Knowledge reduction, includes attribute reduction and value reduction, is an
important topic in rough set literature. It is also closely relevant to other
fields, such as machine learning and data mining. In this paper, an algorithm
called TWI-SQUEEZE is proposed. It can find a reduct, or an irreducible
attribute subset after two scans. Its soundness and computational complexity
are given, which show that it is the fastest algorithm at present. A measure of
variety is brought forward, of which algorithm TWI-SQUEEZE can be regarded as
an application. The author also argues the rightness of this measure as a
measure of information, which can make it a unified measure for
"differentiation, a concept appeared in cognitive psychology literature. Value
reduction is another important aspect of knowledge reduction. It is interesting
that using the same algorithm we can execute a complete value reduction
efficiently. The complete knowledge reduction, which results in an irreducible
table, can therefore be accomplished after four scans of table. The byproducts
of reduction are two classifiers of different styles. In this paper, various
cases and models will be discussed to prove the efficiency and effectiveness of
the algorithm. Some topics, such as how to integrate user preference to find a
local optimal attribute subset will also be discussed.


title: Study of Pakistan Election System as Intelligent e-Election

abstract:
  The proposed election system lies in ensuring that it is transparent and
impartial.Thus while the electoral system may vary from country to country, It
has to take into account the peculiarities of every society while at the same
time incorporating remedies to problems prevailing in the system.
  The Electoral process expressed serious concerns regarding the independence
of the Election Commission of Pakistan, the restrictions on political parties
and their candidates, the misuse of state resources, some unbalanced coverage
in the state media, deficiencies in the compilation of the voting register and
significant problems relating to the provision of ID cards.
  The holding of a general election does not in itself guarantee the
restoration of democracy. The unjustified interference with electoral
arrangements, as detailed above, irrespective of the alleged motivation,
resulted in serious flaws being inflicted on the electoral process.
Additionally, questions remain as to whether or not there will be a full
transfer of power from a military to civilian administration.
  The Independent study research has following modules:
  Login/Subscription Module Candidate Subscription Module Vote casting Module
Administration Module Intelligent decision data analysis Module


title: Pruning Search Space in Defeasible Argumentation

abstract:
  Defeasible argumentation has experienced a considerable growth in AI in the
last decade. Theoretical results have been combined with development of
practical applications in AI & Law, Case-Based Reasoning and various
knowledge-based systems. However, the dialectical process associated with
inference is computationally expensive. This paper focuses on speeding up this
inference process by pruning the involved search space. Our approach is
twofold. On one hand, we identify distinguished literals for computing defeat.
On the other hand, we restrict ourselves to a subset of all possible
conflicting arguments by introducing dialectical constraints.


title:
A Framework for Combining Defeasible Argumentation with Labeled
  Deduction

abstract:
  In the last years, there has been an increasing demand of a variety of
logical systems, prompted mostly by applications of logic in AI and other
related areas. Labeled Deductive Systems (LDS) were developed as a flexible
methodology to formalize such a kind of complex logical systems. Defeasible
argumentation has proven to be a successful approach to formalizing commonsense
reasoning, encompassing many other alternative formalisms for defeasible
reasoning. Argument-based frameworks share some common notions (such as the
concept of argument, defeater, etc.) along with a number of particular features
which make it difficult to compare them with each other from a logical
viewpoint. This paper introduces LDSar, a LDS for defeasible argumentation in
which many important issues concerning defeasible argumentation are captured
within a unified logical framework. We also discuss some logical properties and
extensions that emerge from the proposed framework.


title: "User Interfaces" and the Social Negotiation of Availability

abstract:
  In current presence or availability systems, the method of presenting a
user's state often supposes an instantaneous notion of that state - for
example, a visualization is rendered or an inference is made about the
potential actions that might be consistent with a user's state. Drawing on
observational research on the use of existing communication technology, we
argue (as have others in the past) that determination of availability is often
a joint process, and often one that takes the form of a negotiation (whether
implicit or explicit). We briefly describe our current research on applying
machine learning to infer degrees of conversational engagement from observed
conversational behavior. Such inferences can be applied to facilitate the
implicit negotiation of conversational engagement - in effect, helping users to
weave together the act of contact with the act of determining availability.


title: Conversation Analysis and the User Experience

abstract:
  We provide two case studies in the application of ideas drawn from
conversation analysis to the design of technologies that enhance the experience
of human conversation. We first present a case study of the design of an
electronic guidebook, focusing on how conversation analytic principles played a
role in the design process. We then discuss how the guidebook project has
inspired our continuing work in social, mobile audio spaces. In particular, we
describe some as yet unrealized concepts for adaptive audio spaces.


title: An analysis of a bounded resource search puzzle

abstract:
  Consider the commonly known puzzle, given $k$ glass balls, find an optimal
algorithm to determine the lowest floor of a building of $n$ floors from which
a thrown glass ball will break. This puzzle was originally posed in its
original form in \cite{focs1980}and was later cited in the book \cite{algthc}.
There are several internet sites that presents this puzzle and its solution to
the special case of $k=2$ balls. This is the first such analysis of the puzzle
in its general form. Several variations of this puzzle have been studied with
applications in Network Loading \cite{cgstctl} which analyzes a case similar to
a scenario where an adversary is changing the lowest floor with time. Although
the algorithm specified in \cite{algthc} solves the problem, it is not an
efficient algorithm. In this paper another algorithm for the same problem is
analyzed. It is shown that if $m$ is the minimum number of attempts required
then for $k \geq m$ we have $m = \log (n+1)$ and for $k < m$ we have, $1 +
\sum_{i=1}^{k}{{m-1}\choose{i}} < n \leq \sum_{i=1}^{k}{{m}\choose{i}}$


title: Attrition Defenses for a Peer-to-Peer Digital Preservation System

abstract:
  In peer-to-peer systems, attrition attacks include both traditional,
network-level denial of service attacks as well as application-level attacks in
which malign peers conspire to waste loyal peers' resources. We describe
several defenses for LOCKSS, a peer-to-peer digital preservation system, that
help ensure that application-level attacks even from powerful adversaries are
less effective than simple network-level attacks, and that network-level
attacks must be intense, wide-spread, and prolonged to impair the system.


title: Really Straight Graph Drawings

abstract:
  This paper has been withdrawn by the authors. It has been replaced by the
papers: "Drawings of Planar Graphs with Few Slopes and Segments" (math/0606450)
and "Graph Drawings with Few Slopes" (math/0606446).


title:
A proposal to design expert system for the calculations in the domain of
  QFT

abstract:
  Main purposes of the paper are followings: 1) To show examples of the
calculations in domain of QFT via ``derivative rules'' of an expert system; 2)
To consider advantages and disadvantage that technology of the calculations; 3)
To reflect about how one would develop new physical theories, what knowledge
would be useful in their investigations and how this problem can be connected
with designing an expert system.


title:
Side-Information Coding with Turbo Codes and its Application to Quantum
  Key Distribution

abstract:
  Turbo coding is a powerful class of forward error correcting codes, which can
achieve performances close to the Shannon limit. The turbo principle can be
applied to the problem of side-information source coding, and we investigate
here its application to the reconciliation problem occurring in a
continuous-variable quantum key distribution protocol.


title: A novel approach to symbolic algebra

abstract:
  A prototype for an extensible interactive graphical term manipulation system
is presented that combines pattern matching and nondeterministic evaluation to
provide a convenient framework for doing tedious algebraic manipulations that
so far had to be done manually in a semi-automatic fashion.


title: Algorithms for weighted multi-tape automata

abstract:
  This report defines various operations for weighted multi-tape automata
(WMTAs) and describes algorithms that have been implemented for those
operations in the WFSC toolkit. Some algorithms are new, others are known or
similar to known algorithms. The latter will be recalled to make this report
more complete and self-standing. We present a new approach to multi-tape
intersection, meaning the intersection of a number of tapes of one WMTA with
the same number of tapes of another WMTA. In our approach, multi-tape
intersection is not considered as an atomic operation but rather as a sequence
of more elementary ones, which facilitates its implementation. We show an
example of multi-tape intersection, actually transducer intersection, that can
be compiled with our approach but not with several other methods that we
analysed. To show the practical relavance of our work, we include an example of
application: the preservation of intermediate results in transduction cascades.


title: Application of Business Intelligence In Banks (Pakistan)

abstract:
  The financial services industry is rapidly changing. Factors such as
globalization, deregulation, mergers and acquisitions, competition from
non-financial institutions, and technological innovation, have forced companies
to re-think their business.Many large companies have been using Business
Intelligence (BI) computer software for some years to help them gain
competitive advantage. With the introduction of cheaper and more generalized
products to the market place BI is now in the reach of smaller and medium sized
companies. Business Intelligence is also known as knowledge management,
management information systems (MIS), Executive information systems (EIS) and
On-line analytical Processing (OLAP).


title: Microreboot -- A Technique for Cheap Recovery

abstract:
  A significant fraction of software failures in large-scale Internet systems
are cured by rebooting, even when the exact failure causes are unknown.
However, rebooting can be expensive, causing nontrivial service disruption or
downtime even when clusters and failover are employed. In this work we separate
process recovery from data recovery to enable microrebooting -- a fine-grain
technique for surgically recovering faulty application components, without
disturbing the rest of the application.
  We evaluate microrebooting in an Internet auction system running on an
application server. Microreboots recover most of the same failures as full
reboots, but do so an order of magnitude faster and result in an order of
magnitude savings in lost work. This cheap form of recovery engenders a new
approach to high availability: microreboots can be employed at the slightest
hint of failure, prior to node failover in multi-node clusters, even when
mistakes in failure detection are likely; failure and recovery can be masked
from end users through transparent call-level retries; and systems can be
rejuvenated by parts, without ever being shut down.


title: Dichotomy Theorems for Alternation-Bounded Quantified Boolean Formulas

abstract:
  In 1978, Schaefer proved his famous dichotomy theorem for generalized
satisfiability problems. He defined an infinite number of propositional
satisfiability problems, showed that all these problems are either in P or
NP-complete, and gave a simple criterion to determine which of the two cases
holds. This result is surprising in light of Ladner's theorem, which implies
that there are an infinite number of complexity classes between P and
NP-complete (under the assumption that P is not equal to NP).
  Schaefer also stated a dichotomy theorem for quantified generalized Boolean
formulas, but this theorem was only recently proven by Creignou, Khanna, and
Sudan, and independently by Dalmau: Determining truth of quantified Boolean
formulas is either PSPACE-complete or in P.
  This paper looks at alternation-bounded quantified generalized Boolean
formulas. In their unrestricted forms, these problems are the canonical
problems complete for the levels of the polynomial hierarchy. In this paper, we
prove dichotomy theorems for alternation-bounded quantified generalized Boolean
formulas, by showing that these problems are either $\Sigma_i^p$-complete or in
P, and we give a simple criterion to determine which of the two cases holds.
This is the first result that obtains dichotomy for an infinite number of
classes at once.


title: Parallel Mixed Bayesian Optimization Algorithm: A Scaleup Analysis

abstract:
  Estimation of Distribution Algorithms have been proposed as a new paradigm
for evolutionary optimization. This paper focuses on the parallelization of
Estimation of Distribution Algorithms. More specifically, the paper discusses
how to predict performance of parallel Mixed Bayesian Optimization Algorithm
(MBOA) that is based on parallel construction of Bayesian networks with
decision trees. We determine the time complexity of parallel Mixed Bayesian
Optimization Algorithm and compare this complexity with experimental results
obtained by solving the spin glass optimization problem. The empirical results
fit well the theoretical time complexity, so the scalability and efficiency of
parallel Mixed Bayesian Optimization Algorithm for unknown instances of spin
glass benchmarks can be predicted. Furthermore, we derive the guidelines that
can be used to design effective parallel Estimation of Distribution Algorithms
with the speedup proportional to the number of variables in the problem.


title: Image compression by rectangular wavelet transform

abstract:
  We study image compression by a separable wavelet basis
$\big\{\psi(2^{k_1}x-i)\psi(2^{k_2}y-j),$ $\phi(x-i)\psi(2^{k_2}y-j),$
$\psi(2^{k_1}(x-i)\phi(y-j),$ $\phi(x-i)\phi(y-i)\big\},$ where $k_1, k_2 \in
\mathbb{Z}_+$; $i,j\in\mathbb{Z}$; and $\phi,\psi$ are elements of a standard
biorthogonal wavelet basis in $L_2(\mathbb{R})$. Because $k_1\ne k_2$, the
supports of the basis elements are rectangles, and the corresponding transform
is known as the {\em rectangular wavelet transform}. We prove that if
one-dimensional wavelet basis has $M$ dual vanishing moments then the rate of
approximation by $N$ coefficients of rectangular wavelet transform is
$\mathcal{O}(N^{-M}\log^C N)$ for functions with mixed derivative of order $M$
in each direction.
  The square wavelet transform yields the approximation rate is
$\mathcal{O}(N^{-M/2})$ for functions with all derivatives of the total order
$M$. Thus, the rectangular wavelet transform can outperform the square one if
an image has a mixed derivative. We provide experimental comparison of image
compression which shows that rectangular wavelet transform outperform the
square one.


title: Implementation of Logical Functions in the Game of Life

abstract:
  The Game of Life cellular automaton is a classical example of a massively
parallel collision-based computing device. The automaton exhibits mobile
patterns, gliders, and generators of the mobile patterns, glider guns, in its
evolution. We show how to construct the basic logical operations, AND, OR, NOT
in space-time configurations of the cellular automaton. Also decomposition of
complicated Boolean functions is discussed. Advantages of our technique are
demonstrated on an example of binary adder, realized via collision of glider
streams.


title: Another Proof of an Extension of a Curious Identity

abstract:
  Based on Jensen formulae and the second kind of Chebyshev polynomials,
another proof is presented for an extension of a curious binomial identity due
to Z. W. Sun and K. J. Wu.


title:
Blind Construction of Optimal Nonlinear Recursive Predictors for
  Discrete Sequences

abstract:
  We present a new method for nonlinear prediction of discrete random sequences
under minimal structural assumptions. We give a mathematical construction for
optimal predictors of such processes, in the form of hidden Markov models. We
then describe an algorithm, CSSR (Causal-State Splitting Reconstruction), which
approximates the ideal predictor from data. We discuss the reliability of CSSR,
its data requirements, and its performance in simulations. Finally, we compare
our approach to existing methods using variable-length Markov models and
cross-validated hidden Markov models, and show theoretically and experimentally
that our method delivers results superior to the former and at least comparable
to the latter.

categories: cs.LG math.ST nlin.CD physics.data-an stat.TH


title: Secure Prolog-Based Mobile Code

abstract:
  LogicWeb mobile code consists of Prolog-like rules embedded in Web pages,
thereby adding logic programming behaviour to those pages. Since LogicWeb
programs are downloaded from foreign hosts and executed locally, there is a
need to protect the client from buggy or malicious code. A security model is
crucial for making LogicWeb mobile code safe to execute. This paper presents
such a model, which supports programs of varying trust levels by using
different resource access policies. The implementation of the model derives
from an extended operational semantics for the LogicWeb language, which
provides a precise meaning of safety.


title: Optimization of Bound Disjunctive Queries with Constraints

abstract:
  "To Appear in Theory and Practice of Logic Programming (TPLP)" This paper
presents a technique for the optimization of bound queries over disjunctive
deductive databases with constraints. The proposed approach is an extension of
the well-known Magic-Set technique and is well-suited for being integrated in
current bottom-up (stable) model inference engines. More specifically, it is
based on the exploitation of binding propagation techniques which reduce the
size of the data relevant to answer the query and, consequently, reduces both
the complexity of computing a single model and the number of models to be
considered. The motivation of this work stems from the observation that
traditional binding propagation optimization techniques for bottom-up model
generator systems, simulating the goal driven evaluation of top-down engines,
are only suitable for positive (disjunctive) queries, while hard problems are
expressed using unstratified negation. The main contribution of the paper
consists in the extension of a previous technique, defined for positive
disjunctive queries, to queries containing both disjunctive heads and
constraints (a simple and expressive form of unstratified negation). As the
usual way of expressing declaratively hard problems is based on the
guess-and-check technique, where the guess part is expressed by means of
disjunctive rules and the check part is expressed by means of constraints, the
technique proposed here is highly relevant for the optimization of queries
expressing hard problems. The value of the technique has been proved by several
experiments.


title: O(1) Reversible Tree Navigation Without Cycles

abstract:
  Imperative programmers often use cyclically linked trees in order to achieve
O(1) navigation time to neighbours. Some logic programmers believe that cyclic
terms are necessary to achieve the same in logic-based languages. An old but
little-known technique provides O(1) time and space navigation without cyclic
links, in the form of reversible predicates. A small modification provides O(1)
amortised time and space editing.


title: Zipf's law and the creation of musical context

abstract:
  This article discusses the extension of the notion of context from
linguistics to the domain of music. In language, the statistical regularity
known as Zipf's law -which concerns the frequency of usage of different words-
has been quantitatively related to the process of text generation. This
connection is established by Simon's model, on the basis of a few assumptions
regarding the accompanying creation of context. Here, it is shown that the
statistics of note usage in musical compositions are compatible with the
predictions of Simon's model. This result, which gives objective support to the
conceptual likeness of context in language and music, is obtained through
automatic analysis of the digital versions of several compositions. As a
by-product, a quantitative measure of context definiteness is introduced and
used to compare tonal and atonal works.


title:
Schema-based Scheduling of Event Processors and Buffer Minimization for
  Queries on Structured Data Streams

abstract:
  We introduce an extension of the XQuery language, FluX, that supports
event-based query processing and the conscious handling of main memory buffers.
Purely event-based queries of this language can be executed on streaming XML
data in a very direct way. We then develop an algorithm that allows to
efficiently rewrite XQueries into the event-based FluX language. This algorithm
uses order constraints from a DTD to schedule event handlers and to thus
minimize the amount of buffering required for evaluating a query. We discuss
the various technical aspects of query optimization and query evaluation within
our framework. This is complemented with an experimental evaluation of our
approach.


title: Using Self-Organising Mappings to Learn the Structure of Data Manifolds

abstract:
  In this paper it is shown how to map a data manifold into a simpler form by
progressively discarding small degrees of freedom. This is the key to
self-organising data fusion, where the raw data is embedded in a very
high-dimensional space (e.g. the pixel values of one or more images), and the
requirement is to isolate the important degrees of freedom which lie on a
low-dimensional manifold. A useful advantage of the approach used in this paper
is that the computations are arranged as a feed-forward processing chain, where
all the details of the processing in each stage of the chain are learnt by
self-organisation. This approach is demonstrated using hierarchically
correlated data, which causes the processing chain to split the data into
separate processing channels, and then to progressively merge these channels
wherever they are correlated with each other. This is the key to
self-organising data fusion.


title: Effects of wireless computing technology

abstract:
  Wireless technology can provide many benefits to computing including faster
response to queries, reduced time spent on paperwork, increased online time for
users, just-in-time and real time control, tighter communications between
clients and hosts. Wireless Computing is governed by two general forces:
Technology, which provides a set of basic building blocks and User
Applications, which determine a set of operations that must be carried out
efficiently on demand. This paper summarizes technological changes that are
underway and describes their impact on wireless computing development and
implementation. It also describes the applications that influence the
development and implementation of wireless computing and shows what current
systems offer.


title:
Providing Service Guarantees in High-Speed Switching Systems with
  Feedback Output Queuing

abstract:
  We consider the problem of providing service guarantees in a high-speed
packet switch. As basic requirements, the switch should be scalable to high
speeds per port, a large number of ports and a large number of traffic flows
with independent guarantees. Existing scalable solutions are based on Virtual
Output Queuing, which is computationally complex when required to provide
service guarantees for a large number of flows.
  We present a novel architecture for packet switching that provides support
for such service guarantees. A cost-effective fabric with small external
speedup is combined with a feedback mechanism that enables the fabric to be
virtually lossless, thus avoiding packet drops indiscriminate of flows. Through
analysis and simulation, we show that this architecture provides accurate
support for service guarantees, has low computational complexity and is
scalable to very high port speeds.


title: Algorithms for Drawing Media

abstract:
  We describe algorithms for drawing media, systems of states, tokens and
actions that have state transition graphs in the form of partial cubes. Our
algorithms are based on two principles: embedding the state transition graph in
a low-dimensional integer lattice and projecting the lattice onto the plane, or
drawing the medium as a planar graph with centrally symmetric faces.


title: A direct formulation for sparse PCA using semidefinite programming

abstract:
  We examine the problem of approximating, in the Frobenius-norm sense, a
positive, semidefinite symmetric matrix by a rank-one matrix, with an upper
bound on the cardinality of its eigenvector. The problem arises in the
decomposition of a covariance matrix into sparse factors, and has wide
applications ranging from biology to finance. We use a modification of the
classical variational representation of the largest eigenvalue of a symmetric
matrix, where cardinality is constrained, and derive a semidefinite programming
based relaxation for our problem. We also discuss Nesterov's smooth
minimization technique applied to the SDP arising in the direct sparse PCA
method.


title:
Uncovering the epistemological and ontological assumptions of software
  designers

abstract:
  The ontological and epistemological positions adopted by information systems
design methods are incommensur-able when pushed to their extremes. Information
systems research has therefore tended to focus on the similarities between
different positions, usually in search of a single, unifying position. However,
by focusing on the similari-ties, the clarity of argument provided by any one
philoso-phical position is necessarily diminished. Consequently, researchers
often treat the philosophical foundations of design methods as being of only
minor importance. In this paper, we have deliberately chosen to focus on the
differences between various philosophical positions. From this focus, we
believe we can offer a clearer under-standing of the empirical behaviour of
software as viewed from particular philosophical positions. Since the
em-pirical evidence does not favour any single position, we conclude by arguing
for the validity of ad hoc approaches to software design which we believe
provides a stronger and more theoretically grounded approach to software
design.


title: Notions of Equivalence in Software Design

abstract:
  Design methods in information systems frequently create software descriptions
using formal languages. Nonetheless, most software designers prefer to describe
software using natural languages. This distinction is not simply a matter of
convenience. Natural languages are not the same as formal languages; in
particular, natural languages do not follow the notions of equivalence used by
formal languages. In this paper, we show both the existence and coexistence of
different notions of equivalence by extending the no-tion of oracles used in
formal languages. This allows distinctions to be made between the trustworthy
oracles assumed by formal languages and the untrust-worthy oracles used by
natural languages. By examin-ing the notion of equivalence, we hope to
encourage designers of software to rethink the place of ambiguity in software
design.


title: Layout of Graphs with Bounded Tree-Width

abstract:
  A \emph{queue layout} of a graph consists of a total order of the vertices,
and a partition of the edges into \emph{queues}, such that no two edges in the
same queue are nested. The minimum number of queues in a queue layout of a
graph is its \emph{queue-number}. A \emph{three-dimensional (straight-line
grid) drawing} of a graph represents the vertices by points in $\mathbb{Z}^3$
and the edges by non-crossing line-segments. This paper contributes three main
results:
  (1) It is proved that the minimum volume of a certain type of
three-dimensional drawing of a graph $G$ is closely related to the queue-number
of $G$. In particular, if $G$ is an $n$-vertex member of a proper minor-closed
family of graphs (such as a planar graph), then $G$ has a $O(1)\times
O(1)\times O(n)$ drawing if and only if $G$ has O(1) queue-number.
  (2) It is proved that queue-number is bounded by tree-width, thus resolving
an open problem due to Ganley and Heath (2001), and disproving a conjecture of
Pemmaraju (1992). This result provides renewed hope for the positive resolution
of a number of open problems in the theory of queue layouts.
  (3) It is proved that graphs of bounded tree-width have three-dimensional
drawings with O(n) volume. This is the most general family of graphs known to
admit three-dimensional drawings with O(n) volume.
  The proofs depend upon our results regarding \emph{track layouts} and
\emph{tree-partitions} of graphs, which may be of independent interest.


title: Directional Consistency for Continuous Numerical Constraints

abstract:
  Bounds consistency is usually enforced on continuous constraints by first
decomposing them into binary and ternary primitives. This decomposition has
long been shown to drastically slow down the computation of solutions. To
tackle this, Benhamou et al. have introduced an algorithm that avoids formally
decomposing constraints. Its better efficiency compared to the former method
has already been experimentally demonstrated. It is shown here that their
algorithm implements a strategy to enforce on a continuous constraint a
consistency akin to Directional Bounds Consistency as introduced by Dechter and
Pearl for discrete problems. The algorithm is analyzed in this framework, and
compared with algorithms that enforce bounds consistency. These theoretical
results are eventually contrasted with new experimental results on standard
benchmarks from the interval constraint community.


title: Improving Prolog Programs: Refactoring for Prolog

abstract:
  Refactoring is an established technique from the OO-community to restructure
code: it aims at improving software readability, maintainability and
extensibility. Although refactoring is not tied to the OO-paradigm in
particular, its ideas have not been applied to Logic Programming until now.
  This paper applies the ideas of refactoring to Prolog programs. A catalogue
is presented listing refactorings classified according to scope. Some of the
refactorings have been adapted from the OO-paradigm, while others have been
specifically designed for Prolog. Also the discrepancy between intended and
operational semantics in Prolog is addressed by some of the refactorings.
  In addition, ViPReSS, a semi-automatic refactoring browser, is discussed and
the experience with applying \vipress to a large Prolog legacy system is
reported. Our main conclusion is that refactoring is not only a viable
technique in Prolog but also a rather desirable one.


title:
Fluctuation in Peer-to-Peer Networks: Mitigating Its Effect on DHT
  Performance

abstract:
  Due to the transient nature of peers, any Peer-to-Peer network is in peril to
falling apart if peers do not receive routing table updates periodically. To
this end, maintenance, which affects every peer, ensures connectedness and
sustained data operation performance. However, a high rate of change in peer
population usually incurs lots of network maintenance messages and can severely
degrade overall performance. We discuss three methods how to tackle and
mitigate the effect of peer fluctuation on a tree-based distributed hash table.


title:
Ramsey-type theorems for metric spaces with applications to online
  problems

abstract:
  A nearly logarithmic lower bound on the randomized competitive ratio for the
metrical task systems problem is presented. This implies a similar lower bound
for the extensively studied k-server problem. The proof is based on Ramsey-type
theorems for metric spaces, that state that every metric space contains a large
subspace which is approximately a hierarchically well-separated tree (and in
particular an ultrametric). These Ramsey-type theorems may be of independent
interest.


title: Subset Queries in Relational Databases

abstract:
  In this paper, we motivated the need for relational database systems to
support subset query processing. We defined new operators in relational
algebra, and new constructs in SQL for expressing subset queries. We also
illustrated the applicability of subset queries through different examples
expressed using extended SQL statements and relational algebra expressions. Our
aim is to show the utility of subset queries for next generation applications.


title: Abstract Canonical Inference

abstract:
  An abstract framework of canonical inference is used to explore how different
proof orderings induce different variants of saturation and completeness.
Notions like completion, paramodulation, saturation, redundancy elimination,
and rewrite-system reduction are connected to proof orderings. Fairness of
deductive mechanisms is defined in terms of proof orderings, distinguishing
between (ordinary) "fairness," which yields completeness, and "uniform
fairness," which yields saturation.


title:
A Public Reference Implementation of the RAP Anaphora Resolution
  Algorithm

abstract:
  This paper describes a standalone, publicly-available implementation of the
Resolution of Anaphora Procedure (RAP) given by Lappin and Leass (1994). The
RAP algorithm resolves third person pronouns, lexical anaphors, and identifies
pleonastic pronouns. Our implementation, JavaRAP, fills a current need in
anaphora resolution research by providing a reference implementation that can
be benchmarked against current algorithms. The implementation uses the
standard, publicly available Charniak (2000) parser as input, and generates a
list of anaphora-antecedent pairs as output. Alternately, an in-place
annotation or substitution of the anaphors with their antecedents can be
produced. Evaluation on the MUC-6 co-reference task shows that JavaRAP has an
accuracy of 57.9%, similar to the performance given previously in the
literature (e.g., Preiss 2002).


title: A Dynamic Clustering-Based Markov Model for Web Usage Mining

abstract:
  Markov models have been widely utilized for modelling user web navigation
behaviour. In this work we propose a dynamic clustering-based method to
increase a Markov model's accuracy in representing a collection of user web
navigation sessions. The method makes use of the state cloning concept to
duplicate states in a way that separates in-links whose corresponding
second-order probabilities diverge. In addition, the new method incorporates a
clustering technique which determines an effcient way to assign in-links with
similar second-order probabilities to the same clone. We report on experiments
conducted with both real and random data and we provide a comparison with the
N-gram Markov concept. The results show that the number of additional states
induced by the dynamic clustering method can be controlled through a threshold
parameter, and suggest that the method's performance is linear time in the size
of the model.


title: Randomized k-server algorithms for growth-rate bounded graphs

abstract: The paper referred to in the title is withdrawn.


title: Better algorithms for unfair metrical task systems and applications

abstract:
  Unfair metrical task systems are a generalization of online metrical task
systems. In this paper we introduce new techniques to combine algorithms for
unfair metrical task systems and apply these techniques to obtain improved
randomized online algorithms for metrical task systems on arbitrary metric
spaces.


title:
Optimal Free-Space Management and Routing-Conscious Dynamic Placement
  for Reconfigurable Devices

abstract:
  We describe algorithmic results for two crucial aspects of allocating
resources on computational hardware devices with partial reconfigurability. By
using methods from the field of computational geometry, we derive a method that
allows correct maintainance of free and occupied space of a set of n
rectangular modules in optimal time Theta(n log n); previous approaches needed
a time of O(n^2) for correct results and O(n) for heuristic results. We also
show that finding an optimal feasible communication-conscious placement (which
minimizes the total weighted Manhattan distance between the new module and
existing demand points) can be computed in Theta(n log n). Both resulting
algorithms are practically easy to implement and show convincing experimental
behavior.


title: Online Companion Caching

abstract:
  This paper is concerned with online caching algorithms for the
(n,k)-companion cache, defined by Brehob et. al. In this model the cache is
composed of two components: a k-way set-associative cache and a companion
fully-associative cache of size n. We show that the deterministic competitive
ratio for this problem is (n+1)(k+1)-1, and the randomized competitive ratio is
O(\log n \log k) and \Omega(\log n +\log k).


title: Propositional Computability Logic II

abstract:
  Computability logic is a formal theory of computational tasks and resources.
Its formulas represent interactive computational problems, logical operators
stand for operations on computational problems, and validity of a formula is
understood as being a scheme of problems that always have algorithmic
solutions. A comprehensive online source on the subject is available at
http://www.cis.upenn.edu/~giorgi/cl.html . The earlier article "Propositional
computability logic I" proved soundness and completeness for the (in a sense)
minimal nontrivial fragment CL1 of computability logic. The present paper
extends that result to the significantly more expressive propositional system
CL2. What makes CL2 more expressive than CL1 is the presence of two sorts of
atoms in its language: elementary atoms, representing elementary computational
problems (i.e. predicates), and general atoms, representing arbitrary
computational problems. CL2 conservatively extends CL1, with the latter being
nothing but the general-atom-free fragment of the former.


title:
A New Approach to Draw Detection by Move Repetition in Computer Chess
  Programming

abstract:
  We will try to tackle both the theoretical and practical aspects of a very
important problem in chess programming as stated in the title of this article -
the issue of draw detection by move repetition. The standard approach that has
so far been employed in most chess programs is based on utilising positional
matrices in original and compressed format as well as on the implementation of
the so-called bitboard format.
  The new approach that we will be trying to introduce is based on using
variant strings generated by the search algorithm (searcher) during the tree
expansion in decision making. We hope to prove that this approach is more
efficient than the standard treatment of the issue, especially in positions
with few pieces (endgames). To illustrate what we have in mind a machine
language routine that implements our theoretical assumptions is attached. The
routine is part of the Axon chess program, developed by the authors. Axon, in
its current incarnation, plays chess at master strength (ca. 2400-2450 Elo,
based on both Axon vs computer programs and Axon vs human masters in over 3000
games altogether).