title: CHR Grammars

abstract:
  A grammar formalism based upon CHR is proposed analogously to the way
Definite Clause Grammars are defined and implemented on top of Prolog. These
grammars execute as robust bottom-up parsers with an inherent treatment of
ambiguity and a high flexibility to model various linguistic phenomena. The
formalism extends previous logic programming based grammars with a form of
context-sensitive rules and the possibility to include extra-grammatical
hypotheses in both head and body of grammar rules. Among the applications are
straightforward implementations of Assumption Grammars and abduction under
integrity constraints for language analysis. CHR grammars appear as a powerful
tool for specification and implementation of language processors and may be
proposed as a new standard for bottom-up grammars in logic programming.
  To appear in Theory and Practice of Logic Programming (TPLP), 2005


title: Calculus on Graphs

abstract:
  The purpose of this paper is to develop a "calculus" on graphs that allows
graph theory to have new connections to analysis. For example, our framework
gives rise to many new partial differential equations on graphs, most notably a
new (Laplacian based) wave equation; this wave equation gives rise to a partial
improvement on the Chung-Faber-Manteuffel diameter/eigenvalue bound in graph
theory, and the Chung-Grigoryan-Yau and (in a certain case) Bobkov-Ledoux
distance/eigenvalue bounds in analysis. Our framework also allows most
techniques for the non-linear p-Laplacian in analysis to be easily carried over
to graph theory.


title:
Tsnnls: A solver for large sparse least squares problems with
  non-negative variables

abstract:
  The solution of large, sparse constrained least-squares problems is a staple
in scientific and engineering applications. However, currently available codes
for such problems are proprietary or based on MATLAB. We announce a freely
available C implementation of the fast block pivoting algorithm of Portugal,
Judice, and Vicente. Our version is several times faster than Matstoms' MATLAB
implementation of the same algorithm. Further, our code matches the accuracy of
MATLAB's built-in lsqnonneg function.


title: The Revolution In Database System Architecture

abstract:
  Database system architectures are undergoing revolutionary changes.
Algorithms and data are being unified by integrating programming languages with
the database system. This gives an extensible object-relational system where
non-procedural relational operators manipulate object sets. Coupled with this,
each DBMS is now a web service. This has huge implications for how we structure
applications. DBMSs are now object containers. Queues are the first objects to
be added. These queues are the basis for transaction processing and workflow
applica-tions. Future workflow systems are likely to be built on this core.
Data cubes and online analytic processing are now baked into most DBMSs. Beyond
that, DBMSs have a framework for data mining and machine learning algorithms.
Decision trees, Bayes nets, clustering, and time series analysis are built in;
new algorithms can be added. Text, temporal, and spatial data access methods,
along with their probabilistic reasoning have been added to database systems.
Allowing approximate and probabilistic answers is essential for many
applications. Many believe that XML and xQuery will be the main data structure
and access pattern. Database systems must accommodate that perspective.These
changes mandate a much more dynamic query optimization strategy. Intelligence
is moving to the periphery of the network. Each disk and each sensor will be a
competent database machine. Relational algebra is a convenient way to program
these systems. Database systems are now expected to be self-managing,
self-healing, and always-up.


title: There Goes the Neighborhood: Relational Algebra for Spatial Data Search

abstract:
  We explored ways of doing spatial search within a relational database: (1)
hierarchical triangular mesh (a tessellation of the sphere), (2) a zoned
bucketing system, and (3) representing areas as disjunctive-normal form
constraints. Each of these approaches has merits. They all allow efficient
point-in-region queries. A relational representation for regions allows Boolean
operations among them and allows quick tests for point-in-region,
regions-containing-point, and region-overlap. The speed of these algorithms is
much improved by a zone and multi-scale zone-pyramid scheme. The approach has
the virtue that the zone mechanism works well on B-Trees native to all SQL
systems and integrates naturally with current query optimizers - rather than
requiring a new spatial access method and concomitant query optimizer
extensions. Over the last 5 years, we have used these techniques extensively in
our work on SkyServer.sdss.org, and SkyQuery.net.


title: Performance Characterisation of Intra-Cluster Collective Communications

abstract:
  Although recent works try to improve collective communication in grid systems
by separating intra and inter-cluster communication, the optimisation of
communications focus only on inter-cluster communications. We believe, instead,
that the overall performance of the application may be improved if
intra-cluster collective communications performance is known in advance. Hence,
it is important to have an accurate model of the intra-cluster collective
communications, which provides the necessary evidences to tune and to predict
their performance correctly. In this paper we present our experience on
modelling such communication strategies. We describe and compare different
implementation strategies with their communication models, evaluating the
models' accuracy and describing the practical challenges that can be found when
modelling collective communications.


title:
Identifying Logical Homogeneous Clusters for Efficient Wide-area
  Communications

abstract:
  Recently, many works focus on the implementation of collective communication
operations adapted to wide area computational systems, like computational Grids
or global-computing. Due to the inherently heterogeneity of such environments,
most works separate "clusters" in different hierarchy levels. to better model
the communication. However, in our opinion, such works do not give enough
attention to the delimitation of such clusters, as they normally use the
locality or the IP subnet from the machines to delimit a cluster without
verifying the "homogeneity" of such clusters. In this paper, we describe a
strategy to gather network information from different local-area networks and
to construct "logical homogeneous clusters", better suited to the performance
modelling.


title: Fast Tuning of Intra-Cluster Collective Communications

abstract:
  Recent works try to optimise collective communication in grid systems
focusing mostly on the optimisation of communications among different clusters.
We believe that intra-cluster collective communications should also be
optimised, as a way to improve the overall efficiency and to allow the
construction of multi-level collective operations. Indeed, inside homogeneous
clusters, a simple optimisation approach rely on the comparison from different
implementation strategies, through their communication models. In this paper we
evaluate this approach, comparing different implementation strategies with
their predicted performances. As a result, we are able to choose the
communication strategy that better adapts to each network environment.


title: Monitoring, Analyzing, and Controlling Internet-scale Systems with ACME

abstract:
  Analyzing and controlling large distributed services under a wide range of
conditions is difficult. Yet these capabilities are essential to a number of
important development and operational tasks such as benchmarking, testing, and
system management. To facilitate these tasks, we have built the Application
Control and Monitoring Environment (ACME), a scalable, flexible infrastructure
for monitoring, analyzing, and controlling Internet-scale systems. ACME
consists of two parts. ISING, the Internet Sensor In-Network agGregator,
queries sensors and aggregates the results as they are routed through an
overlay network. ENTRIE, the ENgine for TRiggering Internet Events, uses the
data streams supplied by ISING, in combination with a user's XML configuration
file, to trigger actuators such as killing processes during a robustness
benchmark or paging a system administrator when predefined anomalous conditions
are observed. In this paper we describe the design, implementation, and
evaluation of ACME and its constituent parts. We find that for a 512-node
system running atop an emulated Internet topology, ISING's use of in-network
aggregation can reduce end-to-end query-response latency by more than 50%
compared to using either direct network connections or the same overlay network
without aggregation. We also find that an untuned implementation of ACME can
invoke an actuator on one or all nodes in response to a discrete or aggregate
event in less than four seconds, and we illustrate ACME's applicability to
concrete benchmarking and monitoring scenarios.


title: Consensus on Transaction Commit

abstract:
  The distributed transaction commit problem requires reaching agreement on
whether a transaction is committed or aborted. The classic Two-Phase Commit
protocol blocks if the coordinator fails. Fault-tolerant consensus algorithms
also reach agreement, but do not block whenever any majority of the processes
are working. Running a Paxos consensus algorithm on the commit/abort decision
of each participant yields a transaction commit protocol that uses 2F +1
coordinators and makes progress if at least F +1 of them are working. In the
fault-free case, this algorithm requires one extra message delay but has the
same stable-storage write delay as Two-Phase Commit. The classic Two-Phase
Commit algorithm is obtained as the special F = 0 case of the general Paxos
Commit algorithm.


title:
Multi-dimensional Type Theory: Rules, Categories, and Combinators for
  Syntax and Semantics

abstract:
  We investigate the possibility of modelling the syntax and semantics of
natural language by constraints, or rules, imposed by the multi-dimensional
type theory Nabla. The only multiplicity we explicitly consider is two, namely
one dimension for the syntax and one dimension for the semantics, but the
general perspective is important. For example, issues of pragmatics could be
handled as additional dimensions.
  One of the main problems addressed is the rather complicated repertoire of
operations that exists besides the notion of categories in traditional Montague
grammar. For the syntax we use a categorial grammar along the lines of Lambek.
For the semantics we use so-called lexical and logical combinators inspired by
work in natural logic. Nabla provides a concise interpretation and a sequent
calculus as the basis for implementations.


title: The Dynamics of Group Codes: Dual Abelian Group Codes and Systems

abstract:
  Fundamental results concerning the dynamics of abelian group codes
(behaviors) and their duals are developed. Duals of sequence spaces over
locally compact abelian groups may be defined via Pontryagin duality; dual
group codes are orthogonal subgroups of dual sequence spaces. The dual of a
complete code or system is finite, and the dual of a Laurent code or system is
(anti-)Laurent. If C and C^\perp are dual codes, then the state spaces of C act
as the character groups of the state spaces of C^\perp. The controllability
properties of C are the observability properties of C^\perp. In particular, C
is (strongly) controllable if and only if C^\perp is (strongly) observable, and
the controller memory of C is the observer memory of C^\perp. The controller
granules of C act as the character groups of the observer granules of C^\perp.
Examples of minimal observer-form encoder and syndrome-former constructions are
given. Finally, every observer granule of C is an "end-around" controller
granule of C.


title: Medians and Beyond: New Aggregation Techniques for Sensor Networks

abstract:
  Wireless sensor networks offer the potential to span and monitor large
geographical areas inexpensively. Sensors, however, have significant power
constraint (battery life), making communication very expensive. Another
important issue in the context of sensor-based information systems is that
individual sensor readings are inherently unreliable. In order to address these
two aspects, sensor database systems like TinyDB and Cougar enable in-network
data aggregation to reduce the communication cost and improve reliability. The
existing data aggregation techniques, however, are limited to relatively simple
types of queries such as SUM, COUNT, AVG, and MIN/MAX. In this paper we propose
a data aggregation scheme that significantly extends the class of queries that
can be answered using sensor networks. These queries include (approximate)
quantiles, such as the median, the most frequent data values, such as the
consensus value, a histogram of the data distribution, as well as range
queries. In our scheme, each sensor aggregates the data it has received from
other sensors into a fixed (user specified) size message. We provide strict
theoretical guarantees on the approximation quality of the queries in terms of
the message size. We evaluate the performance of our aggregation scheme by
simulation and demonstrate its accuracy, scalability and low resource
utilization for highly variable input data sets.


title: Hash sort: A linear time complexity multiple-dimensional sort algorithm

abstract:
  Sorting and hashing are two completely different concepts in computer
science, and appear mutually exclusive to one another. Hashing is a search
method using the data as a key to map to the location within memory, and is
used for rapid storage and retrieval. Sorting is a process of organizing data
from a random permutation into an ordered arrangement, and is a common activity
performed frequently in a variety of applications.
  Almost all conventional sorting algorithms work by comparison, and in doing
so have a linearithmic greatest lower bound on the algorithmic time complexity.
Any improvement in the theoretical time complexity of a sorting algorithm can
result in overall larger gains in implementation performance.. A gain in
algorithmic performance leads to much larger gains in speed for the application
that uses the sort algorithm. Such a sort algorithm needs to use an alternative
method for ordering the data than comparison, to exceed the linearithmic time
complexity boundary on algorithmic performance.
  The hash sort is a general purpose non-comparison based sorting algorithm by
hashing, which has some interesting features not found in conventional sorting
algorithms. The hash sort asymptotically outperforms the fastest traditional
sorting algorithm, the quick sort. The hash sort algorithm has a linear time
complexity factor -- even in the worst case. The hash sort opens an area for
further work and investigation into alternative means of sorting.


title: Fractal geometry of literature: first attempt to Shakespeare's works

abstract:
  It was demonstrated that there is a geometrical order in the structure of
literature. Fractal geometry as a modern mathematical approach and a new
geometrical viewpoint on natural objects including both processes and
structures was employed for analysis of literature. As the first study, the
works of William Shakespeare were chosen as the most important items in western
literature. By counting the number of letters applied in a manuscript, it is
possible to study the whole manuscript statistically. A novel method based on
basic assumption of fractal geometry was proposed for the calculation of
fractal dimensions of the literature. The results were compared with Zipf's
law. Zipf's law was successfully used for letters instead of words. Two new
concepts namely Zipf's dimension and Zipf's order were also introduced. It was
found that changes of both fractal dimension and Zipf's dimension are similar
and dependent on the manuscript length. Interestingly, direct plotting the data
obtained in semi-logarithmic and logarithmic forms also led to a power-law.


title: Dynamic Localization Protocols for Mobile Sensor Networks

abstract:
  The ability of a sensor node to determine its physical location within a
network (Localization) is of fundamental importance in sensor networks.
Interpretating data from sensors will not be possible unless the context of the
data is known; this is most often accomplished by tracking its physical
location. Existing research has focused on localization in static sensor
networks where localization is a one-time (or low frequency) activity. In
contrast, this paper considers localization for mobile sensors: when sensors
are mobile, localization must be invoked periodically to enable the sensors to
track their location. The higher the frequency of localization, the lower the
error introduced because of mobility. However, localization is a costly
operation since it involves both communication and computation. In this paper,
we propose and investigate adaptive and predictive protocols that control the
frequency of localization based on sensor mobility behavior to reduce the
energy requirements for localization while bounding the localization error. We
show that such protocols can significantly reduce the localization energy
without sacrificing accuracy (in fact, improving accuracy for most situations).
Using simulation and analysis we explore the tradeoff between energy efficiency
and localization error due to mobility for several protocols.


title: The Arithmetical Complexity of Dimension and Randomness

abstract:
  Constructive dimension and constructive strong dimension are effectivizations
of the Hausdorff and packing dimensions, respectively. Each infinite binary
sequence A is assigned a dimension dim(A) in [0,1] and a strong dimension
Dim(A) in [0,1].
  Let DIM^alpha and DIMstr^alpha be the classes of all sequences of dimension
alpha and of strong dimension alpha, respectively. We show that DIM^0 is
properly Pi^0_2, and that for all Delta^0_2-computable alpha in (0,1],
DIM^alpha is properly Pi^0_3.
  To classify the strong dimension classes, we use a more powerful effective
Borel hierarchy where a co-enumerable predicate is used rather than a
enumerable predicate in the definition of the Sigma^0_1 level. For all
Delta^0_2-computable alpha in [0,1), we show that DIMstr^alpha is properly in
the Pi^0_3 level of this hierarchy. We show that DIMstr^1 is properly in the
Pi^0_2 level of this hierarchy.
  We also prove that the class of Schnorr random sequences and the class of
computably random sequences are properly Pi^0_3.


title: FLUX: A Logic Programming Method for Reasoning Agents

abstract:
  FLUX is a programming method for the design of agents that reason logically
about their actions and sensor information in the presence of incomplete
knowledge. The core of FLUX is a system of Constraint Handling Rules, which
enables agents to maintain an internal model of their environment by which they
control their own behavior. The general action representation formalism of the
fluent calculus provides the formal semantics for the constraint solver. FLUX
exhibits excellent computational behavior due to both a carefully restricted
expressiveness and the inference paradigm of progression.


title: On computing the fixpoint of a set of boolean equations

abstract:
  This paper presents a method for computing a least fixpoint of a system of
equations over booleans. The resulting computation can be significantly shorter
than the result of iteratively evaluating the entire system until a fixpoint is
reached.


title: Authenticated tree parity machine key exchange

abstract:
  The synchronisation of Tree Parity Machines (TPMs), has proven to provide a
valuable alternative concept for secure symmetric key exchange. Yet, from a
cryptographer's point of view, authentication is at least as important as a
secure exchange of keys. Adding an authentication via hashing e.g. is
straightforward but with no relation to Neural Cryptography. We consequently
formulate an authenticated key exchange within this concept. Another
alternative, integrating a Zero-Knowledge protocol into the synchronisation, is
also presented. A Man-In-The-Middle attack and even all currently known
attacks, that are based on using identically structured TPMs and
synchronisation as well, can so be averted. This in turn has practical
consequences on using the trajectory in weight space. Both suggestions have the
advantage of not affecting the previously observed physics of this interacting
system at all.


title: Pervasive Service Architecture for a Digital Business Ecosystem

abstract:
  In this paper we present ideas and architectural principles upon which we are
basing the development of a distributed, open-source infrastructure that, in
turn, will support the expression of business models, the dynamic composition
of software services, and the optimisation of service chains through automatic
self-organising and evolutionary algorithms derived from biology. The target
users are small and medium-sized enterprises (SMEs). We call the collection of
the infrastructure, the software services, and the SMEs a Digital Business
Ecosystem (DBE).


title: Journal of New Democratic Methods: An Introduction

abstract:
  This paper describes a new breed of academic journals that use statistical
machine learning techniques to make them more democratic. In particular, not
only can anyone submit an article, but anyone can also become a reviewer.
Machine learning is used to decide which reviewers accurately represent the
views of the journal's readers and thus deserve to have their opinions carry
more weight. The paper concentrates on describing a specific experimental
prototype of a democratic journal called the Journal of New Democratic Methods
(JNDM). The paper also mentions the wider implications that machine learning
and the techniques used in the JNDM may have for representative democracy in
general.


title: Using Stochastic Encoders to Discover Structure in Data

abstract:
  In this paper a stochastic generalisation of the standard Linde-Buzo-Gray
(LBG) approach to vector quantiser (VQ) design is presented, in which the
encoder is implemented as the sampling of a vector of code indices from a
probability distribution derived from the input vector, and the decoder is
implemented as a superposition of reconstruction vectors. This stochastic VQ
(SVQ) is optimised using a minimum mean Euclidean reconstruction distortion
criterion, as in the LBG case. Numerical simulations are used to demonstrate
how this leads to self-organisation of the SVQ, where different stochastically
sampled code indices become associated with different input subspaces.


title: Invariant Stochastic Encoders

abstract:
  The theory of stochastic vector quantisers (SVQ) has been extended to allow
the quantiser to develop invariances, so that only "large" degrees of freedom
in the input vector are represented in the code. This has been applied to the
problem of encoding data vectors which are a superposition of a "large" jammer
and a "small" signal, so that only the jammer is represented in the code. This
allows the jammer to be subtracted from the total input vector (i.e. the jammer
is nulled), leaving a residual that contains only the underlying signal. The
main advantage of this approach to jammer nulling is that little prior
knowledge of the jammer is assumed, because these properties are automatically
discovered by the SVQ as it is trained on examples of input vectors.


title: Scalable XSLT Evaluation

abstract:
  XSLT is an increasingly popular language for processing XML data. It is
widely supported by application platform software. However, little optimization
effort has been made inside the current XSLT processing engines. Evaluating a
very simple XSLT program on a large XML document with a simple schema may
result in extensive usage of memory. In this paper, we present a novel notion
of \emph{Streaming Processing Model} (\emph{SPM}) to evaluate a subset of XSLT
programs on XML documents, especially large ones. With SPM, an XSLT processor
can transform an XML source document to other formats without extra memory
buffers required. Therefore, our approach can not only tackle large source
documents, but also produce large results. We demonstrate with a performance
study the advantages of the SPM approach. Experimental results clearly confirm
that SPM improves XSLT evaluation typically 2 to 10 times better than the
existing approaches. Moreover, the SPM approach also features high scalability.


title: Application of the Double Metaphone Algorithm to Amharic Orthography

abstract:
  The Metaphone algorithm applies the phonetic encoding of orthographic
sequences to simplify words prior to comparison. While Metaphone has been
highly successful for the English language, for which it was designed, it may
not be applied directly to Ethiopian languages. The paper details how the
principles of Metaphone can be applied to Ethiopic script and uses Amharic as a
case study. Match results improve as specific considerations are made for
Amharic writing practices. Results are shown to improve further when common
errors from Amharic input methods are considered.


title:
Weighted average finite difference methods for fractional diffusion
  equations

abstract:
  Weighted averaged finite difference methods for solving fractional diffusion
equations are discussed and different formulae of the discretization of the
Riemann-Liouville derivative are considered. The stability analysis of the
different numerical schemes is carried out by means of a procedure close to the
well-known von Neumann method of ordinary diffusion equations. The stability
bounds are easily found and checked in some representative examples.


title: Providing Authentic Long-term Archival Access to Complex Relational Data

abstract:
  We discuss long-term preservation of and access to relational databases. The
focus is on national archives and science data archives which have to ingest
and integrate data from a broad spectrum of vendor-specific relational database
management systems (RDBMS). Furthermore, we present our solution SIARD which
analyzes and extracts data and data logic from almost any RDBMS. It enables, to
a reasonable level of authenticity, complete detachment of databases from their
vendor-specific environment. The user can add archival descriptive metadata
according to a customizable schema. A SIARD database archive integrates data,
data logic, technical metadata, and archival descriptive information in one
archival information package, independent of any specific software and
hardware, based upon plain text files and the standardized languages SQL and
XML. For usage purposes, a SIARD archive can be reloaded into any current or
future RDBMS which supports standard SQL. In addition, SIARD contains a client
that enables 'on demand' reload of archives into a target RDBMS, and multi-user
remote access for querying and browsing the data together with its technical
and descriptive metadata in one graphical user interface.


title:
Cauchy Annealing Schedule: An Annealing Schedule for Boltzmann Selection
  Scheme in Evolutionary Algorithms

abstract:
  Boltzmann selection is an important selection mechanism in evolutionary
algorithms as it has theoretical properties which help in theoretical analysis.
However, Boltzmann selection is not used in practice because a good annealing
schedule for the `inverse temperature' parameter is lacking. In this paper we
propose a Cauchy annealing schedule for Boltzmann selection scheme based on a
hypothesis that selection-strength should increase as evolutionary process goes
on and distance between two selection strengths should decrease for the process
to converge. To formalize these aspects, we develop formalism for selection
mechanisms using fitness distributions and give an appropriate measure for
selection-strength. In this paper, we prove an important result, by which we
derive an annealing schedule called Cauchy annealing schedule. We demonstrate
the novelty of proposed annealing schedule using simulations in the framework
of genetic algorithms.


title: A CHR-based Implementation of Known Arc-Consistency

abstract:
  In classical CLP(FD) systems, domains of variables are completely known at
the beginning of the constraint propagation process. However, in systems
interacting with an external environment, acquiring the whole domains of
variables before the beginning of constraint propagation may cause waste of
computation time, or even obsolescence of the acquired data at the time of use.
  For such cases, the Interactive Constraint Satisfaction Problem (ICSP) model
has been proposed as an extension of the CSP model, to make it possible to
start constraint propagation even when domains are not fully known, performing
acquisition of domain elements only when necessary, and without the need for
restarting the propagation after every acquisition.
  In this paper, we show how a solver for the two sorted CLP language, defined
in previous work, to express ICSPs, has been implemented in the Constraint
Handling Rules (CHR) language, a declarative language particularly suitable for
high level implementation of constraint solvers.


title: The role of robust semantic analysis in spoken language dialogue systems

abstract:
  In this paper we summarized a framework for designing grammar-based procedure
for the automatic extraction of the semantic content from spoken queries.
Starting with a case study and following an approach which combines the notions
of fuzziness and robustness in sentence parsing, we showed we built practical
domain-dependent rules which can be applied whenever it is possible to
superimpose a sentence-level semantic structure to a text without relying on a
previous deep syntactical analysis. This kind of procedure can be also
profitably used as a pre-processing tool in order to cut out part of the
sentence which have been recognized to have no relevance in the understanding
process. In the case of particular dialogue applications where there is no need
to build a complex semantic structure (e.g. word spotting or excerpting) the
presented methodology may represent an efficient alternative solution to a
sequential composition of deep linguistic analysis modules. Even if the query
generation problem may not seem a critical application it should be held in
mind that the sentence processing must be done on-line. Having this kind of
constraints we cannot design our system without caring for efficiency and thus
provide an immediate response. Another critical issue is related to whole
robustness of the system. In our case study we tried to make experiences on how
it is possible to deal with an unreliable and noisy input without asking the
user for any repetition or clarification. This may correspond to a similar
problem one may have when processing text coming from informal writing such as
e-mails, news and in many cases Web pages where it is often the case to have
irrelevant surrounding information.


title: Non-negative matrix factorization with sparseness constraints

abstract:
  Non-negative matrix factorization (NMF) is a recently developed technique for
finding parts-based, linear representations of non-negative data. Although it
has successfully been applied in several applications, it does not always
result in parts-based representations. In this paper, we show how explicitly
incorporating the notion of `sparseness' improves the found decompositions.
Additionally, we provide complete MATLAB code both for standard NMF and for our
extension. Our hope is that this will further the application of these methods
to solving novel data-analysis problems.


title: Proofing Tools Technology at Neurosoft S.A.

abstract:
  The aim of this paper is to present the R&D activities carried out at
Neurosoft S.A. regarding the development of proofing tools for Modern Greek.
Firstly, we focus on infrastructure issues that we faced during our initial
steps. Subsequently, we describe the most important insights of three proofing
tools developed by Neurosoft, i.e. the spelling checker, the hyphenator and the
thesaurus, outlining their efficiencies and inefficiencies. Finally, we discuss
some improvement ideas and give our future directions.


title: Verbal chunk extraction in French using limited resources

abstract:
  A way of extracting French verbal chunks, inflected and infinitive, is
explored and tested on effective corpus. Declarative morphological and local
grammar rules specifying chunks and some simple contextual structures are used,
relying on limited lexical information and some simple heuristic/statistic
properties obtained from restricted corpora. The specific goals, the
architecture and the formalism of the system, the linguistic information on
which it relies and the obtained results on effective corpus are presented.


title: An electronic dictionary as a basis for NLP tools: The Greek case

abstract:
  The existence of a Dictionary in electronic form for Modern Greek (MG) is
mandatory if one is to process MG at the morphological and syntactic levels
since MG is a highly inflectional language with marked stress and a spelling
system with many characteristics carried over from Ancient Greek. Moreover,
such a tool becomes necessary if one is to create efficient and sophisticated
NLP applications with substantial linguistic backing and coverage. The present
paper will focus on the deployment of such an electronic dictionary for Modern
Greek, which was built in two phases: first it was constructed to be the basis
for a spelling correction schema and then it was reconstructed in order to
become the platform for the deployment of a wider spectrum of NLP tools.


title: Source Coding With Distortion Side Information At The Encoder

abstract:
  We consider lossy source coding when side information affecting the
distortion measure may be available at the encoder, decoder, both, or neither.
For example, such distortion side information can model reliabilities for noisy
measurements, sensor calibration information, or perceptual effects like
masking and sensitivity to context. When the distortion side information is
statistically independent of the source, we show that in many cases (e.g, for
additive or multiplicative distortion side information) there is no penalty for
knowing the side information only at the encoder, and there is no advantage to
knowing it at the decoder. Furthermore, for quadratic distortion measures
scaled by the distortion side information, we evaluate the penalty for lack of
encoder knowledge and show that it can be arbitrarily large. In this scenario,
we also sketch transform based quantizers constructions which efficiently
exploit encoder side information in the high-resolution limit.


title:
Analysis and Visualization of Index Words from Audio Transcripts of
  Instructional Videos

abstract:
  We introduce new techniques for extracting, analyzing, and visualizing
textual contents from instructional videos of low production quality. Using
Automatic Speech Recognition, approximate transcripts (H75% Word Error Rate)
are obtained from the originally highly compressed videos of university
courses, each comprising between 10 to 30 lectures. Text material in the form
of books or papers that accompany the course are then used to filter meaningful
phrases from the seemingly incoherent transcripts. The resulting index into the
transcripts is tied together and visualized in 3 experimental graphs that help
in understanding the overall course structure and provide a tool for localizing
certain topics for indexing. We specifically discuss a Transcript Index Map,
which graphically lays out key phrases for a course, a Textbook Chapter to
Transcript Match, and finally a Lecture Transcript Similarity graph, which
clusters semantically similar lectures. We test our methods and tools on 7 full
courses with 230 hours of video and 273 transcripts. We are able to extract up
to 98 unique key terms for a given transcript and up to 347 unique key terms
for an entire course. The accuracy of the Textbook Chapter to Transcript Match
exceeds 70% on average. The methods used can be applied to genres of video in
which there are recurrent thematic words (news, sports, meetings,...)


title: Proportional Conflict Redistribution Rules for Information Fusion

abstract:
  In this paper we propose five versions of a Proportional Conflict
Redistribution rule (PCR) for information fusion together with several
examples. From PCR1 to PCR2, PCR3, PCR4, PCR5 one increases the complexity of
the rules and also the exactitude of the redistribution of conflicting masses.
PCR1 restricted from the hyper-power set to the power set and without
degenerate cases gives the same result as the Weighted Average Operator (WAO)
proposed recently by J{\o}sang, Daniel and Vannoorenberghe but does not satisfy
the neutrality property of vacuous belief assignment. That's why improved PCR
rules are proposed in this paper. PCR4 is an improvement of minC and Dempster's
rules. The PCR rules redistribute the conflicting mass, after the conjunctive
rule has been applied, proportionally with some functions depending on the
masses assigned to their corresponding columns in the mass matrix. There are
infinitely many ways these functions (weighting factors) can be chosen
depending on the complexity one wants to deal with in specific applications and
fusion systems. Any fusion combination rule is at some degree ad-hoc.


title: The Core of Directed Network Problems with Quotas

abstract:
  This paper proves the existence of non-empty cores for directed network
problems with quotas and for those combinatorial allocation problems which
permit only exclusive allocations.


title: Robust Locally Testable Codes and Products of Codes

abstract:
  We continue the investigation of locally testable codes, i.e.,
error-correcting codes for whom membership of a given word in the code can be
tested probabilistically by examining it in very few locations. We give two
general results on local testability: First, motivated by the recently proposed
notion of {\em robust} probabilistically checkable proofs, we introduce the
notion of {\em robust} local testability of codes. We relate this notion to a
product of codes introduced by Tanner, and show a very simple composition lemma
for this notion. Next, we show that codes built by tensor products can be
tested robustly and somewhat locally, by applying a variant of a test and proof
technique introduced by Raz and Safra in the context of testing low-degree
multivariate polynomials (which are a special case of tensor codes).
  Combining these two results gives us a generic construction of codes of
inverse polynomial rate, that are testable with poly-logarithmically many
queries. We note these locally testable tensor codes can be obtained from {\em
any} linear error correcting code with good distance. Previous results on local
testability, albeit much stronger quantitatively, rely heavily on algebraic
properties of the underlying codes.


title: The Expected Size of the Rule k Dominating Set

abstract:
  Rule k is a localized approximation algorithm that finds a small connected
dominating set in a graph. We estimate the expected size of the Rule k
dominating set for the model of random unit disk graphs constructed from n
random points in an s_n by s_n square region of the plane.


title: Probabilistic Analysis of Rule 2

abstract:
  Li and Wu proposed Rule 2, a localized approximation algorithm that attempts
to find a small connected dominating set in a graph. Here we study the
asymptotic performance of Rule 2 on random unit disk graphs formed from n
random points in an s_n by s_n square region of the plane. If s_n is below the
threshold for connectivity, then Rule 2 produces a dominating set whose
expected size is O(n/(loglog n)^{3/2}). We conjecture that this bound is not
optimal.


title:
The Integration of Connectionism and First-Order Knowledge
  Representation and Reasoning as a Challenge for Artificial Intelligence

abstract:
  Intelligent systems based on first-order logic on the one hand, and on
artificial neural networks (also called connectionist systems) on the other,
differ substantially. It would be very desirable to combine the robust neural
networking machinery with symbolic knowledge representation and reasoning
paradigms like logic programming in such a way that the strengths of either
paradigm will be retained. Current state-of-the-art research, however, fails by
far to achieve this ultimate goal. As one of the main obstacles to be overcome
we perceive the question how symbolic knowledge can be encoded by means of
connectionist systems: Satisfactory answers to this will naturally lead the way
to knowledge extraction algorithms and to integrated neural-symbolic systems.


title: Probabilistic heuristics for disseminating information in networks

abstract:
  We study the problem of disseminating a piece of information through all the
nodes of a network, given that it is known originally only to a single node. In
the absence of any structural knowledge on the network other than the nodes'
neighborhoods, this problem is traditionally solved by flooding all the
network's edges. We analyze a recently introduced probabilistic algorithm for
flooding and give an alternative probabilistic heuristic that can lead to some
cost-effective improvements, like better trade-offs between the message and
time complexities involved. We analyze the two algorithms both mathematically
and by means of simulations, always within a random-graph framework and
considering relevant node-degree distributions.


title: Default reasoning over domains and concept hierarchies

abstract:
  W.C. Rounds and G.-Q. Zhang (2001) have proposed to study a form of
disjunctive logic programming generalized to algebraic domains. This system
allows reasoning with information which is hierarchically structured and forms
a (suitable) domain. We extend this framework to include reasoning with default
negation, giving rise to a new nonmonotonic reasoning framework on hierarchical
knowledge which encompasses answer set programming with extended disjunctive
logic programs. We also show that the hierarchically structured knowledge on
which programming in this paradigm can be done, arises very naturally from
formal concept analysis. Together, we obtain a default reasoning paradigm for
conceptual knowledge which is in accordance with mainstream developments in
nonmonotonic reasoning.


title:
ScheduleNanny: Using GPS to Learn the User's Significant Locations,
  Travel Times and Schedule

abstract:
  As computing technology becomes more pervasive, personal devices such as the
PDA, cell-phone, and notebook should use context to determine how to act.
Location is one form of context that can be used in many ways. We present a
multiple-device system that collects and clusters GPS data into significant
locations. These locations are then used to determine travel times and a
probabilistic model of the user's schedule, which is used to intelligently
alert the user. We evaluate our system and suggest how it should be integrated
with a variety of applications.


title: The Password Change Phase is Still Insecure

abstract:
  In 2004, W. C. Ku and S. M. Chen proposed an efficient remote user
authentication scheme using smart cards to solve the security problems of Chien
et al.'s scheme. Recently, Hsu and Yoon et al. pointed out the security
weaknesses of the Ku and Chen's scheme Furthermore, Yoon et al. also proposed a
new efficient remote user authentication scheme using smart cards. Yoon et al.
also modified the password change phase of Ku and Chen's scheme. This paper
analyzes that password change phase of Yoon et al's modified scheme is still
insecure.


title:
Sharing Computer Network Logs for Security and Privacy: A Motivation for
  New Methodologies of Anonymization

abstract:
  Logs are one of the most fundamental resources to any security professional.
It is widely recognized by the government and industry that it is both
beneficial and desirable to share logs for the purpose of security research.
However, the sharing is not happening or not to the degree or magnitude that is
desired. Organizations are reluctant to share logs because of the risk of
exposing sensitive information to potential attackers. We believe this
reluctance remains high because current anonymization techniques are weak and
one-size-fits-all--or better put, one size tries to fit all. We must develop
standards and make anonymization available at varying levels, striking a
balance between privacy and utility. Organizations have different needs and
trust other organizations to different degrees. They must be able to map
multiple anonymization levels with defined risks to the trust levels they share
with (would-be) receivers. It is not until there are industry standards for
multiple levels of anonymization that we will be able to move forward and
achieve the goal of widespread sharing of logs for security researchers.


title: Maple+GrTensorII libraries for cosmology

abstract:
  The article mainly presents some results in using MAPLE platform for computer
algebra and GrTensorII package in doing calculations for theoretical and
numerical cosmology


title: The Generalized Pignistic Transformation

abstract:
  This paper presents in detail the generalized pignistic transformation (GPT)
succinctly developed in the Dezert-Smarandache Theory (DSmT) framework as a
tool for decision process. The GPT allows to provide a subjective probability
measure from any generalized basic belief assignment given by any corpus of
evidence. We mainly focus our presentation on the 3D case and provide the
complete result obtained by the GPT and its validation drawn from the
probability theory.


title: A Model for Fine-Grained Alignment of Multilingual Texts

abstract:
  While alignment of texts on the sentential level is often seen as being too
coarse, and word alignment as being too fine-grained, bi- or multilingual texts
which are aligned on a level in-between are a useful resource for many
purposes. Starting from a number of examples of non-literal translations, which
tend to make alignment difficult, we describe an alignment model which copes
with these cases by explicitly coding them. The model is based on
predicate-argument structures and thus covers the middle ground between
sentence and word alignment. The model is currently used in a recently
initiated project of a parallel English-German treebank (FuSe), which can in
principle be extended with additional languages.


title: CrocoPat 2.1 Introduction and Reference Manual

abstract:
  CrocoPat is an efficient, powerful and easy-to-use tool for manipulating
relations of arbitrary arity, including directed graphs. This manual provides
an introduction to and a reference for CrocoPat and its programming language
RML. It includes several application examples, in particular from the analysis
of structural models of software systems.


title: Distance properties of expander codes

abstract:
  We study the minimum distance of codes defined on bipartite graphs. Weight
spectrum and the minimum distance of a random ensemble of such codes are
computed. It is shown that if the vertex codes have minimum distance $\ge 3$,
the overall code is asymptotically good, and sometimes meets the
Gilbert-Varshamov bound.
  Constructive families of expander codes are presented whose minimum distance
asymptotically exceeds the product bound for all code rates between 0 and 1.


title:
Shannon meets Wiener II: On MMSE estimation in successive decoding
  schemes

abstract:
  We continue to discuss why MMSE estimation arises in coding schemes that
approach the capacity of linear Gaussian channels. Here we consider schemes
that involve successive decoding, such as decision-feedback equalization or
successive cancellation.


title: A New Look at Survey Propagation and its Generalizations

abstract:
  This paper provides a new conceptual perspective on survey propagation, which
is an iterative algorithm recently introduced by the statistical physics
community that is very effective in solving random k-SAT problems even with
densities close to the satisfiability threshold. We first describe how any SAT
formula can be associated with a novel family of Markov random fields (MRFs),
parameterized by a real number \rho \in [0,1]. We then show that applying
belief propagation--a well-known ``message-passing'' technique for estimating
marginal probabilities--to this family of MRFs recovers a known family of
algorithms, ranging from pure survey propagation at one extreme (\rho = 1) to
standard belief propagation on the uniform distribution over SAT assignments at
the other extreme (\rho = 0). Configurations in these MRFs have a natural
interpretation as partial satisfiability assignments, on which a partial order
can be defined. We isolate cores as minimal elements in this partial ordering,
which are also fixed points of survey propagation and the only assignments with
positive probability in the MRF for \rho=1. Our experimental results for k=3
suggest that solutions of random formulas typically do not possess non-trivial
cores. This makes it necessary to study the structure of the space of partial
assignments for \rho<1 and investigate the role of assignments that are very
close to being cores. To that end, we investigate the associated lattice
structure, and prove a weight-preserving identity that shows how any MRF with
\rho>0 can be viewed as a ``smoothed'' version of the uniform distribution over
satisfying assignments (\rho=0). Finally, we isolate properties of Gibbs
sampling and message-passing algorithms that are typical for an ensemble of
k-SAT problems.


title: Locally connected spanning trees on graphs

abstract:
  A locally connected spanning tree of a graph $G$ is a spanning tree $T$ of
$G$ such that the set of all neighbors of $v$ in $T$ induces a connected
subgraph of $G$ for every $v\in V(G)$. The purpose of this paper is to give
linear-time algorithms for finding locally connected spanning trees on strongly
chordal graphs and proper circular-arc graphs, respectively.


title: A Digital Signature with Threshold Generation and Verification

abstract:
  This paper proposes a signature scheme where the signatures are generated by
the cooperation of a number of people from a given group of senders and the
signatures are verified by a certain number of people from the group of
recipients. Shamir's threshold scheme and Schnorr's signature scheme are used
to realize the proposed scheme.


title: The strength of replacement in weak arithmetic

abstract:
  The replacement (or collection or choice) axiom scheme asserts bounded
quantifier exchange. We prove the independence of this scheme from various weak
theories of arithmetic, sometimes under a complexity assumption.


title:
Using a hierarchy of Domain Specific Languages in complex software
  systems design

abstract:
  A new design methodology is introduced, with some examples on building Domain
Specific Languages hierarchy on top of Scheme.


title:
Near Optimal Routing for Small-World Networks with Augmented Local
  Awareness

abstract:
  In order to investigate the routing aspects of small-world networks,
Kleinberg proposes a network model based on a $d$-dimensional lattice with
long-range links chosen at random according to the $d$-harmonic distribution.
Kleinberg shows that the greedy routing algorithm by using only local
information performs in $O(\log^2 n)$ expected number of hops, where $n$
denotes the number of nodes in the network. Martel and Nguyen have found that
the expected diameter of Kleinberg's small-world networks is $\Theta(\log n)$.
Thus a question arises naturally: Can we improve the routing algorithms to
match the diameter of the networks while keeping the amount of information
stored on each node as small as possible? We extend Kleinberg's model and add
three augmented local links for each node: two of which are connected to nodes
chosen randomly and uniformly within $\log^2 n$ Mahattan distance, and the
third one is connected to a node chosen randomly and uniformly within $\log n$
Mahattan distance. We show that if each node is aware of $O(\log n)$ number of
neighbors via the augmented local links, there exist both non-oblivious and
oblivious algorithms that can route messages between any pair of nodes in
$O(\log n \log \log n)$ expected number of hops, which is a near optimal
routing complexity and outperforms the other related results for routing in
Kleinberg's small-world networks. Our schemes keep only $O(\log^2 n)$ bits of
routing information on each node, thus they are scalable with the network size.
Besides adding new light to the studies of social networks, our results may
also find applications in the design of large-scale distributed networks, such
as peer-to-peer systems, in the same spirit of Symphony.


title: PKI Scalability Issues

abstract:
  This report surveys different PKI technologies such as PKIX and SPKI and the
issues of PKI that affect scalability. Much focus is spent on certificate
revocation methodologies and status verification systems such as CRLs,
Delta-CRLs, CRS, Certificate Revocation Trees, Windowed Certificate Revocation,
OCSP, SCVP and DVCS.


title: Outlier Detection by Logic Programming

abstract:
  The development of effective knowledge discovery techniques has become in the
recent few years a very active research area due to the important impact it has
in several relevant application areas. One interesting task thereof is that of
singling out anomalous individuals from a given population, e.g., to detect
rare events in time-series analysis settings, or to identify objects whose
behavior is deviant w.r.t. a codified standard set of "social" rules. Such
exceptional individuals are usually referred to as outliers in the literature.
  Recently, outlier detection has also emerged as a relevant KR&R problem. In
this paper, we formally state the concept of outliers by generalizing in
several respects an approach recently proposed in the context of default logic,
for instance, by having outliers not being restricted to single individuals
but, rather, in the more general case, to correspond to entire (sub)theories.
We do that within the context of logic programming and, mainly through
examples, we discuss its potential practical impact in applications. The
formalization we propose is a novel one and helps in shedding some light on the
real nature of outliers. Moreover, as a major contribution of this work, we
illustrate the exploitation of minimality criteria in outlier detection. The
computational complexity of outlier detection problems arising in this novel
setting is thoroughly investigated and accounted for in the paper as well.
Finally, we also propose a rewriting algorithm that transforms any outlier
detection problem into an equivalent inference problem under the stable model
semantics, thereby making outlier computation effective and realizable on top
of any stable model solver.


title:
A Generalized Disjunctive Paraconsistent Data Model for Negative and
  Disjunctive Information

abstract:
  This paper presents a generalization of the disjunctive paraconsistent
relational data model in which disjunctive positive and negative information
can be represented explicitly and manipulated. There are situations where the
closed world assumption to infer negative facts is not valid or undesirable and
there is a need to represent and reason with negation explicitly. We consider
explicit disjunctive negation in the context of disjunctive databases as there
is an interesting interplay between these two types of information. Generalized
disjunctive paraconsistent relation is introduced as the main structure in this
model. The relational algebra is appropriately generalized to work on
generalized disjunctive paraconsistent relations and their correctness is
established.


title: Should Cyberspace Chat Rooms be closed to protect Children?

abstract:
  The explosion of people networking in cyberspace, disseminating terabytes of
information, is being promoted through the use of broadband, bluetooth
technology, and wireless mobile computing facilities. New communities within
such venues as virtual chat rooms discussion groups, newsgroups etc are being
created daily and even hourly. This is raising issues of cyberethics concerning
privacy,security, crime, human needs, e-business, e-healthcare, e-government
and intellectual property among others that need to be evaluated and reflected
upon. With this new freedom come new moral and ethical responsibilities, which
raise questions as to whether anything can be published or whether there should
be restrictions. This paper addresses one specific area, that has come into the
public eye, the closure by Microsoft of all of its free chat rooms.


title: Two Models for the Study of Congested Internet Connections

abstract:
  In this paper, we introduce two deterministic models aimed at capturing the
dynamics of congested Internet connections. The first model is a
continuous-time model that combines a system of differential equations with a
sudden change in one of the state variables. The second model is a
discrete-time model with a time step that arises naturally from the system.
Results from these models show good agreement with the well-known ns network
simulator, better than the results of a previous, similar model. This is due in
large part to the use of the sudden change to reflect the impact of lost data
packets. We also discuss the potential use of this model in network traffic
state estimation.


title: Proximity Inversion Functions on the Non-Negative Integers

abstract:
  We consider functions mapping non-negative integers to non-negative real
numbers such that a and a+n are mapped to values at least 1/n apart. In this
paper we use a novel method to construct such a function. We conjecture that
the supremum of the generated function is optimal and pose some unsolved
problems.


title: Aperiodic Tilings: Breaking Translational Symmetry

abstract:
  Classical results on aperiodic tilings are rather complicated and not widely
understood. Below, an alternative approach is discussed in hope to provide
additional intuition not apparent in classical works.


title: Topics in asynchronous systems

abstract:
  In the paper we define and characterize the asynchronous systems from the
point of view of their autonomy, determinism, order, non-anticipation, time
invariance, symmetry, stability and other important properties. The study is
inspired by the models of the asynchronous circuits.


title:
Capacity-achieving ensembles for the binary erasure channel with bounded
  complexity

abstract:
  We present two sequences of ensembles of non-systematic irregular
repeat-accumulate codes which asymptotically (as their block length tends to
infinity) achieve capacity on the binary erasure channel (BEC) with bounded
complexity per information bit. This is in contrast to all previous
constructions of capacity-achieving sequences of ensembles whose complexity
grows at least like the log of the inverse of the gap (in rate) to capacity.
The new bounded complexity result is achieved by puncturing bits, and allowing
in this way a sufficient number of state nodes in the Tanner graph representing
the codes. We also derive an information-theoretic lower bound on the decoding
complexity of randomly punctured codes on graphs. The bound holds for every
memoryless binary-input output-symmetric channel and is refined for the BEC.


title: Bounds on the decoding complexity of punctured codes on graphs

abstract:
  We present two sequences of ensembles of non-systematic irregular
repeat-accumulate codes which asymptotically (as their block length tends to
infinity) achieve capacity on the binary erasure channel (BEC) with bounded
complexity per information bit. This is in contrast to all previous
constructions of capacity-achieving sequences of ensembles whose complexity
grows at least like the log of the inverse of the gap (in rate) to capacity.
The new bounded complexity result is achieved by puncturing bits, and allowing
in this way a sufficient number of state nodes in the Tanner graph representing
the codes. We also derive an information-theoretic lower bound on the decoding
complexity of randomly punctured codes on graphs. The bound holds for every
memoryless binary-input output-symmetric channel, and is refined for the BEC.


title: Incentive Systems in Multi-Level Markets for Virtual Goods

abstract:
  As an alternative to rigid DRM measures, ways of marketing virtual goods
through multi-level or networked marketing have raised some interest. This
report is a first approach to multi-level markets for virtual goods from the
viewpoint of theoretical economy. A generic, kinematic model for the monetary
flow in multi-level markets, which quantitatively describes the incentives that
buyers receive through resales revenues, is devised. Building on it, the
competition of goods is examined in a dynamical, utility-theoretic model
enabling, in particular, a treatment of the free-rider problem. The most
important implications for the design of multi-level market mechanisms for
virtual goods, or multi-level incentive management systems, are outlined.


title:
Efficient polynomial time algorithms computing industrial-strength
  primitive roots

abstract:
  E. Bach, following an idea of T. Itoh, has shown how to build a small set of
numbers modulo a prime p such that at least one element of this set is a
generator of $\pF{p}$\cite{Bach:1997:sppr,Itoh:2001:PPR}. E. Bach suggests also
that at least half of his set should be generators. We show here that a slight
variant of this set can indeed be made to contain a ratio of primitive roots as
close to 1 as necessary. We thus derive several algorithms computing primitive
roots correct with very high probability in polynomial time. In particular we
present an asymptotically $O^{\sim}(\sqrt{\frac{1}{\epsilon}}log^1.5(p) +
\log^2(p))$ algorithm providing primitive roots of $p$ with probability of
correctness greater than $1-\epsilon$ and several $O(log^\alpha(p))$, $\alpha
\leq 5.23$ algorithms computing "Industrial-strength" primitive roots with
probabilities e.g. greater than the probability of "hardware malfunctions".


title: Automatic Generation of CHR Constraint Solvers

abstract:
  In this paper, we present a framework for automatic generation of CHR solvers
given the logical specification of the constraints. This approach takes
advantage of the power of tabled resolution for constraint logic programming,
in order to check the validity of the rules. Compared to previous works where
different methods for automatic generation of constraint solvers have been
proposed, our approach enables the generation of more expressive rules (even
recursive and splitting rules) that can be used directly as CHR solvers.


title:
Field Geology with a Wearable Computer: First Results of the Cyborg
  Astrobiologist System

abstract:
  We present results from the first geological field tests of the `Cyborg
Astrobiologist', which is a wearable computer and video camcorder system that
we are using to test and train a computer-vision system towards having some of
the autonomous decision-making capabilities of a field-geologist. The Cyborg
Astrobiologist platform has thus far been used for testing and development of
these algorithms and systems: robotic acquisition of quasi-mosaics of images,
real-time image segmentation, and real-time determination of interesting points
in the image mosaics. The hardware and software systems function reliably, and
the computer-vision algorithms are adequate for the first field tests. In
addition to the proof-of-concept aspect of these field tests, the main result
of these field tests is the enumeration of those issues that we can improve in
the future, including: dealing with structural shadow and microtexture, and
also, controlling the camera's zoom lens in an intelligent manner. Nonetheless,
despite these and other technical inadequacies, this Cyborg Astrobiologist
system, consisting of a camera-equipped wearable-computer and its
computer-vision algorithms, has demonstrated its ability of finding genuinely
interesting points in real-time in the geological scenery, and then gathering
more information about these interest points in an automated manner.


title:
Desynchronization and Speedup in an Asynchronous Conservative Parallel
  Update Protocol

abstract:
  In a state-update protocol for a system of $L$ asynchronous parallel
processes that communicate only with nearest neighbors, global
desynchronization in operation times can be deduced from kinetic roughening of
the corresponding virtual-time horizon (VTH). The utilization of the parallel
processing environment can be deduced by analyzing the microscopic structure of
the VTH. We give an overview of how the methods of non-equilibrium surface
growth (physics of complex systems) can be applied to uncover some properties
of state update algorithms used in distributed parallel discrete-event
simulations (PDES). In particular, we focus on the asynchronous conservative
PDES algorithm in a ring communication topology. The time evolution of its VTH
is simulated numerically as asynchronous cellular automaton whose update rule
corresponds to the update rule followed by this algorithm. We give theoretical
estimates of the performance as a function of $L$ and the load per processor,
i.e., approximate formulas for the mean speedup and for the desynchronization.
It is established that, for a given simulation size, there is a theoretical
upper bound for the desynchronization and a theoretical non-zero lower bound
for the utilization. The new approach to performance studies, outlined in this
chapter, is particularly useful in the search for the design of a
new-generation of algorithms that would efficiently carry out an autonomous or
tunable synchronization.


title: Mean and Variance Estimation by Kriging

abstract:
  The aim of the paper is to derive the numerical least-squares estimator for
mean and variance of random variable. In order to do so the following questions
have to be answered: (i) what is the statistical model for the estimation
procedure? (ii) what are the properties of the estimator, like optimality (in
which class) or asymptotic properties? (iii) how does the estimator work in
practice, how compared to competing estimators?


title: Securing Data in Storage: A Review of Current Research

abstract:
  Protecting data from malicious computer users continues to grow in
importance. Whether preventing unauthorized access to personal photographs,
ensuring compliance with federal regulations, or ensuring the integrity of
corporate secrets, all applications require increased security to protect data
from talented intruders. Specifically, as more and more files are preserved on
disk the requirement to provide secure storage has increased in importance.
This paper presents a survey of techniques for securely storing data, including
theoretical approaches, prototype systems, and existing systems currently
available. Due to the wide variety of potential solutions available and the
variety of techniques to arrive at a particular solution, it is important to
review the entire field prior to selecting an implementation that satisfies
particular requirements. This paper provides an overview of the prominent
characteristics of several systems to provide a foundation for making an
informed decision. Initially, the paper establishes a set of criteria for
evaluating a storage solution based on confidentiality, integrity,
availability, and performance. Then, using these criteria, the paper explains
the relevant characteristics of select storage systems and provides a
comparison of the major differences.


title:
Parallel Computing Environments and Methods for Power Distribution
  System Simulation

abstract:
  The development of cost-effective highperformance parallel computing on
multi-processor supercomputers makes it attractive to port excessively time
consuming simulation software from personal computers (PC) to super computes.
The power distribution system simulator (PDSS) takes a bottom-up approach and
simulates load at the appliance level, where detailed thermal models for
appliances are used. This approach works well for a small power distribution
system consisting of a few thousand appliances. When the number of appliances
increases, the simulation uses up the PC memory and its runtime increases to a
point where the approach is no longer feasible to model a practical large power
distribution system. This paper presents an effort made to port a PC-based
power distribution system simulator to a 128-processor shared-memory
supercomputer. The paper offers an overview of the parallel computing
environment and a description of the modification made to the PDSS model. The
performance of the PDSS running on a standalone PC and on the supercomputer is
compared. Future research direction of utilizing parallel computing in the
power distribution system simulation is also addressed.


title: A Directed Signature Scheme and its Applications

abstract:
  This paper presents a directed signature scheme with the property that the
signature can be verified only with the help of signer or signature receiver.
We also propose its applications to share verification of signatures and to
threshold cryptosystems.


title:
Business Processes: The Theoretical Impact of Process Thinking on
  Information Systems Development

abstract:
  This paper investigates two aspects of process thinking that affect the
success rate of IT projects. These two aspects are the changes in the structure
of organizations and the epistemology of Information Systems Development.
Firstly, the conception of business processes within the management of
organizations increases the structural complexity of Information Systems,
because existing systems have to be integrated into a coherent cross-functional
architecture. Secondly, process thinking leads to a particular view of
organizations that ultimately has a negative effect on the support of
Information Systems. As an illustration of process thinking, the Business
Process Reengineering movement adheres to a technocratic management perspective
of organizations. Particularly this conception of organization views people as
mechanisms to realize certain organizational goals. As a result of this view
stakeholders are confronted with the implemented systems, rather than consulted
about the scope and functionality of those systems. Therefore, both aspects of
process thinking have a negative impact on the success of IT projects. The
problem of structural complexity is an area that is addressed by Enterprise
Application Integration, and mainly requires technical solutions. However, the
problems associated with the conception of organization require a different,
markedly non-technical, perspective. Several directions are discussed to
overcome some limitations of process thinking, but these directions are merely
small pointers. If truly effective and useful Information Systems are to be
acquired, IT practitioners and scientists require a completely different
mindset.


title: Checking modes of HAL programs

abstract:
  Recent constraint logic programming (CLP) languages, such as HAL and Mercury,
require type, mode and determinism declarations for predicates. This
information allows the generation of efficient target code and the detection of
many errors at compile-time. Unfortunately, mode checking in such languages is
difficult. One of the main reasons is that, for each predicate mode
declaration, the compiler is required to appropriately re-order literals in the
predicate's definition. The task is further complicated by the need to handle
complex instantiations (which interact with type declarations and higher-order
predicates) and automatic initialization of solver variables. Here we define
mode checking for strongly typed CLP languages which require reordering of
clause body literals. In addition, we show how to handle a simple case of
polymorphic modes by using the corresponding polymorphic types.


title: NP - P is not empty

abstract:
  We present the MEoP problem that decides the existence of solutions to
certain modular equations over prime numbers and show how this separates the
complexity class NP from its subclass P


title: Unification of Fusion Theories

abstract:
  Since no fusion theory neither rule fully satisfy all needed applications,
the author proposes a Unification of Fusion Theories and a combination of
fusion rules in solving problems/applications. For each particular application,
one selects the most appropriate model, rule(s), and algorithm of
implementation. We are working in the unification of the fusion theories and
rules, which looks like a cooking recipe, better we'd say like a logical chart
for a computer programmer, but we don't see another method to comprise/unify
all things. The unification scenario presented herein, which is now in an
incipient form, should periodically be updated incorporating new discoveries
from the fusion and engineering research.


title: Four Principles Fundamental to Design Practice for Human Centred Systems

abstract:
  A Survey of the principal literature on Human Centred Design reveals the four
most referenced principles. These are discussed with reference to the
application of a particular website, and a user survey is constructed based
upon the four principles.


title: A new architecture for making highly scalable applications

abstract:
  An application is a logical image of the world on a computer. A scalable
application is an application that allows one to update that logical image at
run time. To put it in operational terms: an application is scalable if a
client can change between time T1 and time T2 - the logic of the application as
expressed by language L;
  - the structure and volume of the stored knowledge;
  - the user interface of the application; while clients working with the
application at time T1 will work with the changed application at time T2
without performing any special action between T1 and T2. In order to realize
such a scalable application a new architecture has been developed that fully
orbits around language. In order to verify the soundness of that architecture a
program has been build. Both architecture and program are called CommunSENS.
The main purpose of this paper is: - to list the relevant elements of the
architecture; - to give a visual presentation of how the program and its image
of the world look like; - to give a visual presentation of how the image can be
updated. Some relevant philosophical and practical backgrounds are included in
the appendixes.


title: Inapproximability of Combinatorial Optimization Problems

abstract:
  We survey results on the hardness of approximating combinatorial optimization
problems.


title: Some Applications of Coding Theory in Computational Complexity

abstract:
  Error-correcting codes and related combinatorial constructs play an important
role in several recent (and old) results in computational complexity theory. In
this paper we survey results on locally-testable and locally-decodable
error-correcting codes, and their applications to complexity theory and to
cryptography.
  Locally decodable codes are error-correcting codes with sub-linear time
error-correcting algorithms. They are related to private information retrieval
(a type of cryptographic protocol), and they are used in average-case
complexity and to construct ``hard-core predicates'' for one-way permutations.
  Locally testable codes are error-correcting codes with sub-linear time
error-detection algorithms, and they are the combinatorial core of
probabilistically checkable proofs.


title:
Augmenting ALC(D) (atemporal) roles and (aspatial) concrete domain with
  temporal roles and a spatial concrete domain -first results

abstract:
  We consider the well-known family ALC(D) of description logics with a
concrete domain, and provide first results on a framework obtained by
augmenting ALC(D) atemporal roles and aspatial concrete domain with temporal
roles and a spatial concrete domain.


title:
A TCSP-like decidable constraint language generalising existing cardinal
  direction relations

abstract:
  We define a quantitative constraint language subsuming two calculi well-known
in QSR (Qualitative Spatial Reasoning): Frank's cone-shaped and
projection-based calculi of cardinal direction relations. We show how to solve
a CSP (Constraint Satisfaction Problem) expressed in the language.


title:
An ALC(D)-based combination of temporal constraints and spatial
  constraints suitable for continuous (spatial) change

abstract:
  We present a family of spatio-temporal theories suitable for continuous
spatial change in general, and for continuous motion of spatial scenes in
particular. The family is obtained by spatio-temporalising the well-known
ALC(D) family of Description Logics (DLs) with a concrete domain D, as follows,
where TCSPs denotes "Temporal Constraint Satisfaction Problems", a well-known
constraint-based framework:
  (1) temporalisation of the roles, so that they consist of TCSP constraints
(specifically, of an adaptation of TCSP constraints to interval variables); and
  (2) spatialisation of the concrete domain D: the concrete domain is now
$D_x$, and is generated by a spatial Relation Algebra (RA) $x$, in the style of
the Region-Connection Calculus RCC8.
  We assume durative truth (i.e., holding during a durative interval). We also
assume the homogeneity property (if a truth holds during a given interval, it
holds during all of its subintervals). Among other things, these assumptions
raise the "conflicting" problem of overlapping truths, which the work solves
with the use of a specific partition of the 13 atomic relations of Allen's
interval algebra.


title: FORM Matters: Fast Symbolic Computation under UNIX

abstract:
  We give a brief introduction to FORM, a symbolic programming language for
massive batch operations, designed by J.A.M. Vermaseren. In particular, we
stress various methods to efficiently use FORM under the UNIX operating system.
Several scripts and examples are given, and suggestions on how to use the vim
editor as development platform.


title: A Directed -Threshold Multi-Signature Scheme

abstract:
  In this paper, we propose a Directed Threshold Multi-Signature Scheme. In
this threshold signature scheme, any malicious set of signers cannot
impersonate any other set of signers to forge the signatures. In case of
forgery, it is possible to trace the signing set. This threshold signature
scheme is applicable when the message is sensitive to the signature receiver;
and the signatures are generated by the cooperation of a number of people from
a given group of senders.


title: Some Applications of Directed Signature Scheme

abstract:
  Directed signature scheme is applicable when the signed message contains
information sensitive to the receiver, because only receiver can directly
verify the signature and that he/she can prove its validity to any third party,
whenever necessary. This paper presents two applications of directed signature
scheme. (i) Directed –Delegated Signature Scheme. This scheme combines
the idea of proxy signatures with directed signature scheme. (ii) Allocation of
registration number. This scheme proposes a registration scheme in which the
registration number cannot be forged and misused.


title: Quantum Complexity Classes

abstract:
  In our thesis, we try to shed more light onto the complexity of quantum
complexity classes by refining the related part of the hierarchy. First, we
review the basic concepts of quantum computing in general. Then, inspired by
BQP, we define new complexity classes. They are placed between BPP and PSPACE.
We show that they incorporate the current important quantum algorithms.
Furthermore, the importance of the unitarity constraint given by quantum
mechanics is revealed. Without this requirement, we naturally arrive at the
class AWPP, which was up to now thought to be just an artificially defined
class. We hope that some of our newly defined classes could find their use in
proving results about BQP.


title: Better Quasi-Ordered Transition Systems

abstract:
  Many existing algorithms for model checking of infinite-state systems operate
on constraints which are used to represent (potentially infinite) sets of
states. A general powerful technique which can be employed for proving
termination of these algorithms is that of well quasi-orderings. Several
methodologies have been proposed for derivation of new well quasi-ordered
constraint systems. However, many of these constraint systems suffer from a
"constraint explosion problem", as the number of the generated constraints
grows exponentially with the size of the problem. In this paper, we demonstrate
that a refinement of the theory of well quasi-orderings, called the theory of
better quasi-orderings, is more appropriate for symbolic model checking, since
it allows inventing constraint systems which are both well quasi-ordered and
compact. As a main application, we introduce existential zones, a constraint
system for verification of systems with unboundedly many clocks and use our
methodology to prove that existential zones are better quasi-ordered. We show
how to use existential zones in verification of timed Petri nets and present
some experimental results. Also, we apply our methodology to derive new
constraint systems for verification of broadcast protocols, lossy channel
systems, and integral relational automata. The new constraint systems are
exponentially more succinct than existing ones, and their well quasi-ordering
cannot be shown by previous methods in the literature.


title:
On the role of MMSE estimation in approaching the information-theoretic
  limits of linear Gaussian channels: Shannon meets Wiener

abstract:
  We discuss why MMSE estimation arises in lattice-based schemes for
approaching the capacity of linear Gaussian channels, and comment on its
properties.


title: An Approximation Algorithm for Stackelberg Network Pricing

abstract:
  We consider the problem of maximizing the revenue raised from tolls set on
the arcs of a transportation network, under the constraint that users are
assigned to toll-compatible shortest paths. We first prove that this problem is
strongly NP-hard. We then provide a polynomial time algorithm with a worst-case
precision guarantee of ${1/2}\log_2 m_T+1$, where $m_T$ denotes the number of
toll arcs. Finally we show that the approximation is tight with respect to a
natural relaxation by constructing a family of instances for which the
relaxation gap is reached.


title:
The Building of Online Communities: An approach for learning
  organizations, with a particular focus on the museum sector

abstract:
  This paper considers the move toward and potential of building online
communities, with a particular focus on the museum sector. For instance, the
increase in the use of `personalized' toolkits that are becoming an integral
part of the online presence for learning organizations, like museums, can
provide a basis for creating and sustaining communities. A set of case studies
further illustrates working examples of the ways in which personalization and
specific tools are developing collaborative spaces, community channels and
group interactions.


title:
Using sparse matrices and splines-based interpolation in computational
  fluid dynamics simulations

abstract:
  In this relation I present a technique of construction and fast evaluation of
a family of cubic polynomials for analytic smoothing and graphical rendering of
particles trajectories for flows in a generic geometry. The principal result of
the work was implementation and test of a method for interpolating 3D points by
regular parametric curves and their fast and efficient evaluation for a good
resolution of rendering. For the purpose a parallel environment using a
multiprocessor cluster architecture has been used. This work has been developed
for the Research and Development Department of my company for planning advanced
customized models of industrial burners.


title:
Fast Construction of Nets in Low Dimensional Metrics, and Their
  Applications

abstract:
  We present a near linear time algorithm for constructing hierarchical nets in
finite metric spaces with constant doubling dimension. This data-structure is
then applied to obtain improved algorithms for the following problems:
Approximate nearest neighbor search, well-separated pair decomposition, compact
representation scheme, doubling measure, and computation of the (approximate)
Lipschitz constant of a function. In all cases, the running (preprocessing)
time is near-linear and the space being used is linear.


title:
A Sentimental Education: Sentiment Analysis Using Subjectivity
  Summarization Based on Minimum Cuts

abstract:
  Sentiment analysis seeks to identify the viewpoint(s) underlying a text span;
an example application is classifying a movie review as "thumbs up" or "thumbs
down". To determine this sentiment polarity, we propose a novel
machine-learning method that applies text-categorization techniques to just the
subjective portions of the document. Extracting these portions can be
implemented using efficient techniques for finding minimum cuts in graphs; this
greatly facilitates incorporation of cross-sentence contextual constraints.


title: From Digital Television to Internet?

abstract:
  This paper provides a general technical overview of the Multimedia Home
Platform (MHP) specifications. MHP is a generic interface between digital
applications and user machines, whether they happen to be set top boxes,
digital TV sets or Multimedia PC's. MHP extends the DVB open standards.
Addressed are MHP architexture, System core and MHP Profiles.


title: The Infati Data

abstract:
  The ability to perform meaningful empirical studies is of essence in research
in spatio-temporal query processing. Such studies are often necessary to gain
detailed insight into the functional and performance characteristics of
proposals for new query processing techniques.
  We present a collection of spatio-temporal data, collected during an
intelligent speed adaptation project, termed INFATI, in which some two dozen
cars equipped with GPS receivers and logging equipment took part. We describe
how the data was collected and how it was "modified" to afford the drivers some
degree of anonymity.
  We also present the road network in which the cars were moving during data
collection.
  The GPS data is publicly available for non-commercial purposes. It is our
hope that this resource will help the spatio-temporal research community in its
efforts to develop new and better query processing techniques.


title: Shannon Information and Kolmogorov Complexity

abstract:
  We compare the elementary theories of Shannon information and Kolmogorov
complexity, the extent to which they have a common purpose, and where they are
fundamentally different. We discuss and relate the basic notions of both
theories: Shannon entropy versus Kolmogorov complexity, the relation of both to
universal coding, Shannon mutual information versus Kolmogorov (`algorithmic')
mutual information, probabilistic sufficient statistic versus algorithmic
sufficient statistic (related to lossy compression in the Shannon theory versus
meaningful information in the Kolmogorov theory), and rate distortion theory
versus Kolmogorov's structure function. Part of the material has appeared in
print before, scattered through various publications, but this is the first
comprehensive systematic comparison. The last mentioned relations are new.


title:
Capacity and Random-Coding Exponents for Channel Coding with Side
  Information

abstract:
  Capacity formulas and random-coding exponents are derived for a generalized
family of Gel'fand-Pinsker coding problems. These exponents yield asymptotic
upper bounds on the achievable log probability of error. In our model,
information is to be reliably transmitted through a noisy channel with finite
input and output alphabets and random state sequence, and the channel is
selected by a hypothetical adversary. Partial information about the state
sequence is available to the encoder, adversary, and decoder. The design of the
transmitter is subject to a cost constraint. Two families of channels are
considered: 1) compound discrete memoryless channels (CDMC), and 2) channels
with arbitrary memory, subject to an additive cost constraint, or more
generally to a hard constraint on the conditional type of the channel output
given the input. Both problems are closely connected. The random-coding
exponent is achieved using a stacked binning scheme and a maximum penalized
mutual information decoder, which may be thought of as an empirical generalized
Maximum a Posteriori decoder. For channels with arbitrary memory, the
random-coding exponents are larger than their CDMC counterparts. Applications
of this study include watermarking, data hiding, communication in presence of
partially known interferers, and problems such as broadcast channels, all of
which involve the fundamental idea of binning.


title: Applying Policy Iteration for Training Recurrent Neural Networks

abstract:
  Recurrent neural networks are often used for learning time-series data. Based
on a few assumptions we model this learning task as a minimization problem of a
nonlinear least-squares cost function. The special structure of the cost
function allows us to build a connection to reinforcement learning. We exploit
this connection and derive a convergent, policy iteration-based algorithm.
Furthermore, we argue that RNN training can be fit naturally into the
reinforcement learning framework.


title: A dynamical model of a GRID market

abstract:
  We discuss potential market mechanisms for the GRID. A complete dynamical
model of a GRID market is defined with three types of agents. Providers,
middlemen and users exchange universal GRID computing units (GCUs) at varying
prices. Providers and middlemen have strategies aimed at maximizing profit
while users are 'satisficing' agents, and only change their behavior if the
service they receive is sufficiently poor or overpriced. Preliminary results
from a multi-agent numerical simulation of the market model shows that the
distribution of price changes has a power law tail.


title: Demo or Practice: Critical Analysis of the Language/Action Perspective

abstract:
  Despite offering several promising concepts, the Language/Action Perspective
(LAP) is still not in the mainstream of Information Systems Development (ISD).
Since at present there is only a limited understanding of LAP theory and
practice, it remains unclear whether the lack of LAP's impact is due to
shortcomings in LAP theory itself. One classic problem within ISD is the
dichotomy between social perspectives and technical perspectives. LAP claims it
offers a solution to this problem. This paper investigates this claim as a
means to review LAP theory. To provide a structure to a critical analysis of
DEMO - an example methodology that belongs to the LAP research community - this
paper utilizes a paradigmatic framework. This framework is augmented by the
opinion of several DEMO practitioners by means of an expert discussion. With
use of a comparative evaluation of LAP theory and DEMO theory, the implication
of DEMO's reflection upon LAP is determined. The paper concludes by outlining
an agenda for further research if LAP is to improve its footprint in the field.


title:
A Shared Write-protected Root Filesystem for a Group of Networked
  Clients

abstract:
  A method to boot a cluster of diskless network clients from a single
write-protected NFS root file system is shown. The problems encountered when
first implementing the setup and their solution are discussed. Finally, the
setup is briefly compared to using a kernel-embedded root file system.


title: Source Coding with Fixed Lag Side Information

abstract:
  We consider source coding with fixed lag side information at the decoder. We
focus on the special case of perfect side information with unit lag
corresponding to source coding with feedforward (the dual of channel coding
with feedback) introduced by Pradhan. We use this duality to develop a linear
complexity algorithm which achieves the rate-distortion bound for any
memoryless finite alphabet source and distortion measure.


title:
Diffusive Load Balancing of Loosely-Synchronous Parallel Programs over
  Peer-to-Peer Networks

abstract:
  The use of under-utilized Internet resources is widely recognized as a viable
form of high performance computing. Sustained processing power of roughly 40T
FLOPS using 4 million volunteered Internet hosts has been reported for
embarrassingly parallel problems. At the same time, peer-to-peer (P2P) file
sharing networks, with more than 50 million participants, have demonstrated the
capacity for scale in distributed systems. This paper contributes a study of
load balancing techniques for a general class of loosely-synchronous parallel
algorithms when executed over a P2P network. We show that decentralized,
diffusive load balancing can be effective at balancing load and is facilitated
by the dynamic properties of P2P. While a moderate degree of dynamicity can
benefit load balancing, significant dynamicity hinders the parallel program
performance due to the need for increased load migration. To the best of our
knowledge this study provides new insight into the performance of
loosely-synchronous parallel programs over the Internet.


title: A New Proxy Ring Signature Scheme

abstract:
  The concept of ring signature was introduced by Rivest, Shamir and Tauman.
This signature is considered to be a simplified group signature from which
identity of signer is ambiguous although verifier knows the group to which
signer belong. In this paper we introduce a new proxy ring signature scheme.


title: Comment on A dynamic ID-based Remote User Authentication Scheme

abstract:
  Since 1981, when Lamport introduced the remote user authentication scheme
using table, a plenty of schemes had been proposed with tables or without table
using. Recently Das et al. proposed a dynamic id-based remote user
authentication scheme. They claimed that their scheme is secure against
ID-theft, and can resist the reply attacks, forgery attacks, insider attacks an
so on. In this paper we show that Das et al's scheme is completly insecure and
using of this scheme is like an open server access without password.


title: DiPerF: an automated DIstributed PERformance testing Framework

abstract:
  We present DiPerF, a distributed performance testing framework, aimed at
simplifying and automating service performance evaluation. DiPerF coordinates a
pool of machines that test a target service, collects and aggregates
performance metrics, and generates performance statistics. The aggregate data
collected provide information on service throughput, on service "fairness" when
serving multiple clients concurrently, and on the impact of network latency on
service performance. Furthermore, using this data, it is possible to build
predictive models that estimate a service performance given the service load.
We have tested DiPerF on 100+ machines on two testbeds, Grid3 and PlanetLab,
and explored the performance of job submission services (pre WS GRAM and WS
GRAM) included with Globus Toolkit 3.2.


title: Fibonacci connection between Huffman codes and Wythoff array

abstract:
  Fibonacci connection between non-decreasing sequences of positive integers
producing maximum height Huffman trees and the Wythoff array has been proved.


title: Normal forms for Answer Sets Programming

abstract:
  Normal forms for logic programs under stable/answer set semantics are
introduced. We argue that these forms can simplify the study of program
properties, mainly consistency. The first normal form, called the {\em kernel}
of the program, is useful for studying existence and number of answer sets. A
kernel program is composed of the atoms which are undefined in the Well-founded
semantics, which are those that directly affect the existence of answer sets.
The body of rules is composed of negative literals only. Thus, the kernel form
tends to be significantly more compact than other formulations. Also, it is
possible to check consistency of kernel programs in terms of colorings of the
Extended Dependency Graph program representation which we previously developed.
The second normal form is called {\em 3-kernel.} A 3-kernel program is composed
of the atoms which are undefined in the Well-founded semantics. Rules in
3-kernel programs have at most two conditions, and each rule either belongs to
a cycle, or defines a connection between cycles. 3-kernel programs may have
positive conditions. The 3-kernel normal form is very useful for the static
analysis of program consistency, i.e., the syntactic characterization of
existence of answer sets. This result can be obtained thanks to a novel
graph-like representation of programs, called Cycle Graph which presented in
the companion article \cite{Cos04b}.


title:
L1 regularization is better than L2 for learning and predicting chaotic
  systems

abstract:
  Emergent behaviors are in the focus of recent research interest. It is then
of considerable importance to investigate what optimizations suit the learning
and prediction of chaotic systems, the putative candidates for emergence. We
have compared L1 and L2 regularizations on predicting chaotic time series using
linear recurrent neural networks. The internal representation and the weights
of the networks were optimized in a unifying framework. Computational tests on
different problems indicate considerable advantages for the L1 regularization:
It had considerably better learning time and better interpolating capabilities.
We shall argue that optimization viewed as a maximum likelihood estimation
justifies our results, because L1 regularization fits heavy-tailed
distributions -- an apparently general feature of emergent systems -- better.