title: A New Approach to Formal Language Theory by Kolmogorov Complexity

abstract:
  We present a new approach to formal language theory using Kolmogorov
complexity. The main results presented here are an alternative for pumping
lemma(s), a new characterization for regular languages, and a new method to
separate deterministic context-free languages and nondeterministic context-free
languages. The use of the new `incompressibility arguments' is illustrated by
many examples. The approach is also successful at the high end of the Chomsky
hierarchy since one can quantify nonrecursiveness in terms of Kolmogorov
complexity. (This is a preliminary uncorrected version. The final version is
the one published in SIAM J. Comput., 24:2(1995), 398-410.)


title: Towards Solving the Interdisciplinary Language Barrier Problem

abstract:
  This work aims to make it easier for a specialist in one field to find and
explore ideas from another field which may be useful in solving a new problem
arising in his practice. It presents a methodology which serves to represent
the relationships that exist between concepts, problems, and solution patterns
from different fields of human activity in the form of a graph. Our approach is
based upon generalization and specialization relationships and problem solving.
It is simple enough to be understood quite easily, and general enough to enable
coherent integration of concepts and problems from virtually any field. We have
built an implementation which uses the World Wide Web as a support to allow
navigation between graph nodes and collaborative development of the graph.


title: An Architecture for Security and Privacy in Mobile Communications

abstract:
  There is much discussion and debate about how to improve the security and
privacy of mobile communication systems, both voice and data. Most proposals
attempt to provide incremental improvements to systems that are deployed today.
Indeed, only incremental improvements are possible, given the regulatory,
technological, economic, and historical structure of the telecommunications
system. In this paper, we conduct a ``thought experiment'' to redesign the
mobile communications system to provide a high level of security and privacy
for the users of the system. We discuss the important requirements and how a
different architecture might successfully satisfy them. In doing so, we hope to
illuminate the possibilities for secure and private systems, as well as explore
their real limits.


title: An Overview of Computer security

abstract:
  As more business activities are being automated and an increasing number of
computers are being used to store vital and sensitive information the need for
secure computer systems becomes more apparent. These systems can be achieved
only through systematic design; they cannot be achieved through haphazard
seat-of-the-pants methods.This paper introduces some known threats to the
computer security, categorizes the threats, and analyses protection mechanisms
and techniques for countering the threats. The threats have been classified
more so as definitions and then followed by the classifications of these
threats. Also mentioned are the protection mechanisms.


title: EquiX--A Search and Query Language for XML

abstract:
  EquiX is a search language for XML that combines the power of querying with
the simplicity of searching. Requirements for such languages are discussed and
it is shown that EquiX meets the necessary criteria. Both a graph-based
abstract syntax and a formal concrete syntax are presented for EquiX queries.
In addition, the semantics is defined and an evaluation algorithm is presented.
The evaluation algorithm is polynomial under combined complexity.
  EquiX combines pattern matching, quantification and logical expressions to
query both the data and meta-data of XML documents. The result of a query in
EquiX is a set of XML documents. A DTD describing the result documents is
derived automatically from the query.


title: From 2G TO 3G - The Evolution of International Cellular Standards

abstract:
  The purpose of this paper is to examine the major factors surrouding and
contributing to the creation (and success) of Europe's 2nd generation 'GSM'
cellular system, and compare and contrast it to key events and recent
developments in 3rd generation 'IMT-2000' systems. The objective is to
ascertain whether lessons from the development of one system can be applied to
the other, and what implications 2G has for the development and assessment of
3G technologies. Among the major themes incorporated into this assessment is
the concept of cooperation, and its role in bringing about the collaboration
and integration necessary to support the success of an international cellular
standard.


title:
The Expresso Microarray Experiment Management System: The Functional
  Genomics of Stress Responses in Loblolly Pine

abstract:
  Conception, design, and implementation of cDNA microarray experiments present
a variety of bioinformatics challenges for biologists and computational
scientists. The multiple stages of data acquisition and analysis have motivated
the design of Expresso, a system for microarray experiment management. Salient
aspects of Expresso include support for clone replication and randomized
placement; automatic gridding, extraction of expression data from each spot,
and quality monitoring; flexible methods of combining data from individual
spots into information about clones and functional categories; and the use of
inductive logic programming for higher-level data analysis and mining. The
development of Expresso is occurring in parallel with several generations of
microarray experiments aimed at elucidating genomic responses to drought stress
in loblolly pine seedlings. The current experimental design incorporates 384
pine cDNAs replicated and randomly placed in two specific microarray layouts.
We describe the design of Expresso as well as results of analysis with Expresso
that suggest the importance of molecular chaperones and membrane transport
proteins in mechanisms conferring successful adaptation to long-term drought
stress.


title: Multivariant Branching Prediction, Reflection, and Retrospection

abstract:
  In branching simulation, a novel approach to simulation presented in this
paper, a multiplicity of plausible scenarios are concurrently developed and
implemented. In conventional simulations of complex systems, there arise from
time to time uncertainties as to which of two or more alternatives are more
likely to be pursued by the system being simulated. Under these conditions the
simulationist makes a judicious choice of one of these alternatives and embeds
this choice in the simulation model. By contrast, in the branching approach,
two or more of such alternatives (or branches) are included in the model and
implemented for concurrent computer solution. The theoretical foundations for
branching simulation as a computational process are in the domains of
alternating Turing machines, molecular computing, and E-machines. Branching
simulations constitute the development of diagrams of scenarios representing
significant, alternative flows of events. Logical means for interpretation and
investigation of the branching simulation and prediction are provided by the
logical theories of possible worlds, which have been formalized by the
construction of logical varieties. Under certain conditions, the branching
approach can considerably enhance the efficiency of computer simulations and
provide more complete insights into the interpretation of predictions based on
simulations. As an example, the concepts developed in this paper have been
applied to a simulation task that plays an important role in radiology - the
noninvasive treatment of brain aneurysms.


title: A Symmetric Strategy in Graph Avoidance Games

abstract:
  In the graph avoidance game two players alternatingly color edges of a graph
G in red and in blue respectively. The player who first creates a monochromatic
subgraph isomorphic to a forbidden graph F loses. A symmetric strategy of the
second player ensures that, independently of the first player's strategy, the
blue and the red subgraph are isomorphic after every round of the game. We
address the class of those graphs G that admit a symmetric strategy for all F
and discuss relevant graph-theoretic and complexity issues. We also show
examples when, though a symmetric strategy on G generally does not exist, it is
still available for a particular F.


title:
What is the minimal set of fragments that achieves maximal parse
  accuracy?

abstract:
  We aim at finding the minimal set of fragments which achieves maximal parse
accuracy in Data Oriented Parsing. Experiments with the Penn Wall Street
Journal treebank show that counts of almost arbitrary fragments within parse
trees are important, leading to improved parse accuracy over previous models
tested on this treebank (a precision of 90.8% and a recall of 90.6%). We
isolate some dependency relations which previous models neglect but which
contribute to higher parse accuracy.


title: Combining semantic and syntactic structure for language modeling

abstract:
  Structured language models for speech recognition have been shown to remedy
the weaknesses of n-gram models. All current structured language models are,
however, limited in that they do not take into account dependencies between
non-headwords. We show that non-headword dependencies contribute to
significantly improved word error rate, and that a data-oriented parsing model
trained on semantically and syntactically annotated data can exploit these
dependencies. This paper also contains the first DOP model trained by means of
a maximum likelihood reestimation procedure, which solves some of the
theoretical shortcomings of previous DOP models.


title: Mragyati : A System for Keyword-based Searching in Databases

abstract:
  The web, through many search engine sites, has popularized the keyword-based
search paradigm, where a user can specify a string of keywords and expect to
retrieve relevant documents, possibly ranked by their relevance to the query.
Since a lot of information is stored in databases (and not as HTML documents),
it is important to provide a similar search paradigm for databases, where users
can query a database without knowing the database schema and database query
languages such as SQL. In this paper, we propose such a database search system,
which accepts a free-form query as a collection of keywords, translates it into
queries on the database using the database metadata, and presents query results
in a well-structured and browsable form. Th eysytem maps keywords onto the
database schema and uses inter-relationships (i.e., data semantics) among the
referred tables to generate meaningful query results. We also describe our
prototype for database search, called Mragyati. Th eapproach proposed here is
scalable, as it does not build an in-memory graph of the entire database for
searching for relationships among the objects selected by the user's query.


title: Machine Learning in Automated Text Categorization

abstract:
  The automated categorization (or classification) of texts into predefined
categories has witnessed a booming interest in the last ten years, due to the
increased availability of documents in digital form and the ensuing need to
organize them. In the research community the dominant approach to this problem
is based on machine learning techniques: a general inductive process
automatically builds a classifier by learning, from a set of preclassified
documents, the characteristics of the categories. The advantages of this
approach over the knowledge engineering approach (consisting in the manual
definition of a classifier by domain experts) are a very good effectiveness,
considerable savings in terms of expert manpower, and straightforward
portability to different domains. This survey discusses the main approaches to
text categorization that fall within the machine learning paradigm. We will
discuss in detail issues pertaining to three different problems, namely
document representation, classifier construction, and classifier evaluation.


title: Vertex-Unfoldings of Simplicial Manifolds

abstract:
  We present an algorithm to unfold any triangulated 2-manifold (in particular,
any simplicial polyhedron) into a non-overlapping, connected planar layout in
linear time. The manifold is cut only along its edges. The resulting layout is
connected, but it may have a disconnected interior; the triangles are connected
at vertices, but not necessarily joined along edges. We extend our algorithm to
establish a similar result for simplicial manifolds of arbitrary dimension.


title:
Analytical solution of transient scalar wave and diffusion problems of
  arbitrary dimensionality and geometry by RBF wavelet series

abstract:
  This study applies the RBF wavelet series to the evaluation of analytical
solutions of linear time-dependent wave and diffusion problems of any
dimensionality and geometry. To the best of the author's knowledge, such
analytical solutions have never been achieved before. The RBF wavelets can be
understood an alternative for multidimensional problems to the standard Fourier
series via fundamental and general solutions of partial differential equation.
The present RBF wavelets are infinitely differential, compactly supported,
orthogonal over different scales and very simple. The rigorous mathematical
proof of completeness and convergence is still missing in this study. The
present work may open a new window to numerical solution and theoretical
analysis of many other high-dimensional time-dependent PDE problems under
arbitrary geometry.


title: Probabilistic analysis of a differential equation for linear programming

abstract:
  In this paper we address the complexity of solving linear programming
problems with a set of differential equations that converge to a fixed point
that represents the optimal solution. Assuming a probabilistic model, where the
inputs are i.i.d. Gaussian variables, we compute the distribution of the
convergence rate to the attracting fixed point. Using the framework of Random
Matrix Theory, we derive a simple expression for this distribution in the
asymptotic limit of large problem size. In this limit, we find that the
distribution of the convergence rate is a scaling function, namely it is a
function of one variable that is a combination of three parameters: the number
of variables, the number of constraints and the convergence rate, rather than a
function of these parameters separately. We also estimate numerically the
distribution of computation times, namely the time required to reach a vicinity
of the attracting fixed point, and find that it is also a scaling function.
Using the problem size dependence of the distribution functions, we derive high
probability bounds on the convergence rates and on the computation times.

categories: cs.CC cond-mat.stat-mech math-ph math.MP math.OC


title:
Generating Multilingual Personalized Descriptions of Museum Exhibits -
  The M-PIRO Project

abstract:
  This paper provides an overall presentation of the M-PIRO project. M-PIRO is
developing technology that will allow museums to generate automatically textual
or spoken descriptions of exhibits for collections available over the Web or in
virtual reality environments. The descriptions are generated in several
languages from information in a language-independent database and small
fragments of text, and they can be tailored according to the backgrounds of the
users, their ages, and their previous interaction with the system. An authoring
tool allows museum curators to update the system's database and to control the
language and content of the resulting descriptions. Although the project is
still in progress, a Web-based demonstrator that supports English, Greek and
Italian is already available, and it is used throughout the paper to highlight
the capabilities of the emerging technology.


title:
Teaching Parallel Programming Using Both High-Level and Low-Level
  Languages

abstract:
  We discuss the use of both MPI and OpenMP in the teaching of senior
undergraduate and junior graduate classes in parallel programming. We briefly
introduce the OpenMP standard and discuss why we have chosen to use it in
parallel programming classes. Advantages of using OpenMP over message passing
methods are discussed. We also include a brief enumeration of some of the
drawbacks of using OpenMP and how these drawbacks are being addressed by
supplementing OpenMP with additional MPI codes and projects. Several projects
given in my class are also described in this paper.


title: Nonorthogonal Polyhedra Built from Rectangles

abstract:
  We prove that any polyhedron of genus zero or genus one built out of
rectangular faces must be an orthogonal polyhedron, but that there are
nonorthogonal polyhedra of genus seven all of whose faces are rectangles. This
leads to a resolution of a question posed by Biedl, Lubiw, and Sun [BLS99].


title: Selected Topics in Asynchronous Automata

abstract:
  The paper is concerned with defining the electrical signals and their models.
The delays are discussed, the asynchronous automata - which are the models of
the asynchronous circuits - and the examples of the clock generator and of the
R-S latch are given. We write the equations of the asynchronous automata, which
combine the pure delay model and the inertial delay model; the simple gate
model and the complex gate model; the fixed, bounded and unbounded delay model.
We give the solutions of these equations, which are written on R->{0,1}
functions, where R is the time set. The connection between the real time and
the discrete time is discussed. The stability, the fundamental mode of
operation, the combinational automata, the semi-modularity are defined and
characterized. Some connections are suggested with the linear time and the
branching time temporal logic of the propositions.


title: An Asynchronous Automata Approach to the Semantics of Temporal Logic

abstract:
  The paper presents the differential equations that characterize an
asynchronous automaton and gives their solution x:R->{0,1}x...x{0,1}. Remarks
are made on the connection between the continuous time and the discrete time of
the approach. The continuous and the discrete time, the linear and the
branching temporal logics have the semantics depending on x and their formulas
give the properties of the automaton.


title:
The Delay-Insensitivity, the Hazard-Freedom, the Semi-Modularity and the
  Technical Condition of Good Running of the Discrete Time Asynchronous
  Automata

abstract:
  The paper studies some important properties of the asynchronous (=timed)
automata: the delay-insensitivity, the hazard-freedom, the semi-modularity and
the technical condition of good running. Time is discrete.


title:
The Existence of $\omega$-Chains for Transitive Mixed Linear Relations
  and Its Applications

abstract:
  We show that it is decidable whether a transitive mixed linear relation has
an $\omega$-chain. Using this result, we study a number of liveness
verification problems for generalized timed automata within a unified
framework. More precisely, we prove that (1) the mixed linear liveness problem
for a timed automaton with dense clocks, reversal-bounded counters, and a free
counter is decidable, and (2) the Presburger liveness problem for a timed
automaton with discrete clocks, reversal-bounded counters, and a pushdown stack
is decidable.


title:
Applications of the Differential Calculus in the Study of the Timed
  Automata: the Inertial Delay Buffer

abstract:
  We write the relations that characterize the simpliest timed automaton, the
inertial delay buffer, in two versions: the non-deterministic and the
deterministic one, by making use of the derivatives of the R->{0,1} functions.


title: Interfacing the ControlLogix PLC over Ethernet/IP

abstract:
  The Allen-Bradley ControlLogix line of pro-grammable logic controllers (PLCs)
offers several in-terfaces: Ethernet, ControlNet, DeviceNet, RS-232 and others.
The ControlLogix Ethernet interface module 1756-ENET uses EtherNet/IP, the
ControlNet protocol, encapsulated in Ethernet packages, with specific service
codes. A driver for the Experimental Physics and Industrial Control System
(EPICS) has been developed that utilizes this EtherNet/IP protocol for
controllers running the vxWorks RTOS as well as a Win32 and Unix/Linux test
program. Features, per-formance and limitations of this interface are
presented.


title:
Overview of the Experimental Physics and Industrial Control System
  (EPICS) Channel Archiver

abstract:
  The Channel Archiver has been operational for more than two years at Los
Alamos National Laboratory and other sites. This paper introduces the available
components (data sampling engine, viewers, scripting interface, HTTP/CGI
integration and data management), presents updated performance measurements and
reviews operational experience with the Channel Archiver.


title: Analysis of Investment Policy in Belarus

abstract:
  The optimal planning trajectory is analyzed on the basis of the growth model
with effectiveness. The saving per capital value has to be rather high
initially with smooth decrement in the future years.


title: Integrating LabVIEW into a Distributed Computing Environment

abstract:
  Being easy to learn and well suited for a self-contained desktop laboratory
setup, many casual programmers prefer to use the National Instruments LabVIEW
environment to develop their logic. An ActiveX interface is presented that
allows integration into a plant-wide distributed environment based on the
Experimental Physics and Industrial Control System (EPICS). This paper
discusses the design decisions and provides performance information, especially
considering requirements for the Spallation Neutron Source (SNS) diagnostics
system.


title:
L-Fuzzy Valued Inclusion Measure, L-Fuzzy Similarity and L-Fuzzy
  Distance

abstract:
  The starting point of this paper is the introduction of a new measure of
inclusion of fuzzy set A in fuzzy set B. Previously used inclusion measures
take values in the interval [0,1]; the inclusion measure proposed here takes
values in a Boolean lattice. In other words, inclusion is viewed as an L-fuzzy
valued relation between fuzzy sets. This relation is re exive, antisymmetric
and transitive, i.e. it is a fuzzy order relation; in addition it possesess a
number of properties which various authors have postulated as axiomatically
appropriate for an inclusion measure. We also define an L-fuzzy valued measure
of similarity between fuzzy sets and and an L-fuzzy valued distance function
between fuzzy sets; these possess properties analogous to the ones of
real-valued similarity and distance functions.
  Keywords: Fuzzy Relations, inclusion measure, subsethood, L-fuzzy sets,
similarity, distance, transitivity.


title: The Use of Classifiers in Sequential Inference

abstract:
  We study the problem of combining the outcomes of several different
classifiers in a way that provides a coherent inference that satisfies some
constraints. In particular, we develop two general approaches for an important
subproblem-identifying phrase structure. The first is a Markovian approach that
extends standard HMMs to allow the use of a rich observation structure and of
general classifiers to model state-observation dependencies. The second is an
extension of constraint satisfaction formalisms. We develop efficient
combination algorithms under both models and study them experimentally in the
context of shallow parsing.


title: The Relational Database Aspects of Argonne's ATLAS Control System

abstract:
  The Relational Database Aspects of Argonnes ATLAS Control System Argonnes
ATLAS (Argonne Tandem Linac Accelerator System) control system comprises two
separate database concepts. The first is the distributed real-time database
structure provided by the commercial product Vsystem [1]. The second is a more
static relational database archiving system designed by ATLAS personnel using
Oracle Rdb [2] and Paradox [3] software. The configuration of the ATLAS
facility has presented a unique opportunity to construct a control system
relational database that is capable of storing and retrieving complete archived
tune-up configurations for the entire accelerator. This capability has been a
major factor in allowing the facility to adhere to a rigorous operating
schedule. Most recently, a Web-based operator interface to the control systems
Oracle Rdb database has been installed. This paper explains the history of the
ATLAS database systems, how they interact with each other, the design of the
new Web-based operator interface, and future plans.


title: Automated Real-Time Testing (ARTT) for Embedded Control Systems (ECS)

abstract:
  Developing real-time automated test systems for embedded control systems has
been a real problem. Some engineers and scientists have used customized
software and hardware as a solution, which can be very expensive and time
consuming to develop. We have discovered how to integrate a suite of
commercially available off-the-shelf software tools and hardware to develop a
scalable test platform that is capable of performing complete black-box testing
for a dual-channel real-time Embedded-PLC-based control system
(www.aps.anl.gov). We will discuss how the Vali/Test Pro testing methodology
was implemented to structure testing for a personnel safety system with large
quantities of requirements and test cases.
  This work was supported by the U.S. Department of Energy, Basic Energy
Sciences, under Contract No. W-31-109-Eng-38.


title: Proliferation of SDDS Support for Various Platforms and Languages

abstract:
  Since Self-Describing Data Sets (SDDS) were first introduced, the source code
has been ported to many different operating systems and various languages. SDDS
is now available in C, Tcl, Java, Fortran, and Python. All of these versions
are supported on Solaris, Linux, and Windows. The C version of SDDS is also
supported on VxWorks. With the recent addition of the Java port, SDDS can now
be deployed on virtually any operating system. Due to this proliferation, SDDS
files serve to link not only a collection of C programs, but programs and
scripts in many languages on different operating systems. The platform
independent binary feature of SDDS also facilitates portability among operating
systems. This paper presents an overview of various benefits of SDDS platform
interoperability.


title: Explaining Scenarios for Information Personalization

abstract:
  Personalization customizes information access. The PIPE ("Personalization is
Partial Evaluation") modeling methodology represents interaction with an
information space as a program. The program is then specialized to a user's
known interests or information seeking activity by the technique of partial
evaluation. In this paper, we elaborate PIPE by considering requirements
analysis in the personalization lifecycle. We investigate the use of scenarios
as a means of identifying and analyzing personalization requirements. As our
first result, we show how designing a PIPE representation can be cast as a
search within a space of PIPE models, organized along a partial order. This
allows us to view the design of a personalization system, itself, as
specialized interpretation of an information space. We then exploit the
underlying equivalence of explanation-based generalization (EBG) and partial
evaluation to realize high-level goals and needs identified in scenarios; in
particular, we specialize (personalize) an information space based on the
explanation of a user scenario in that information space, just as EBG
specializes a theory based on the explanation of an example in that theory. In
this approach, personalization becomes the transformation of information spaces
to support the explanation of usage scenarios. An example application is
described.


title: The Control of a Beamline Over Intranet

abstract:
  The machines and beamlines controlled by VME industrial networks are very
popular in accelerator faculties. Recently new software technology, among of
which are Internet/Intranet application, Java language, and distributed
calculating environment, changes the control manner rapidly. A program based on
DCOM is composed to control of a variable included angle spherical grating
monochromator beamline at National Synchrotron Radiation Laboratory (NSRL) in
China. The control computer with a residential DCOM program is connected to
Intranet by LAN, over which the user-end-operating program located in another
computer sends driving beamline units' commands to the control computer. And
also a web page coded in Java, published by the WWW service running in the
control computer, is simply illustrated how to use web browser to query the
states of or to control the beamline units.


title:
On the complexity of inducing categorical and quantitative association
  rules

abstract:
  Inducing association rules is one of the central tasks in data mining
applications. Quantitative association rules induced from databases describe
rich and hidden relationships holding within data that can prove useful for
various application purposes (e.g., market basket analysis, customer profiling,
and others). Even though such association rules are quite widely used in
practice, a thorough analysis of the computational complexity of inducing them
is missing. This paper intends to provide a contribution in this setting. To
this end, we first formally define quantitative association rule mining
problems, which entail boolean association rules as a special case, and then
analyze their computational complexities, by considering both the standard
cases, and a some special interesting case, that is, association rule induction
over databases with null values, fixed-size attribute set databases, sparse
databases, fixed threshold problems.


title: Abduction with Penalization in Logic Programming

abstract:
  Abduction, first proposed in the setting of classical logics, has been
studied with growing interest in the logic programming area during the last
years.
  In this paper we study {\em abduction with penalization} in logic
programming. This form of abductive reasoning, which has not been previously
analyzed in logic programming, turns out to represent several relevant
problems, including optimization problems, very naturally. We define a formal
model for abduction with penalization from logic programs, which extends the
abductive framework proposed by Kakas and Mancarella. We show the high
expressiveness of this formalism, by encoding a couple of relevant problems,
including the well-know Traveling Salesman Problem from optimization theory, in
this abductive framework. The resulting encodings are very simple and elegant.
We analyze the complexity of the main decisional problems arising in this
framework. An interesting result in this course is that ``negation comes for
free.'' Indeed, the addition of (even unstratified) negation does not cause any
further increase to the complexity of the abductive reasoning tasks (which
remains the same as for not-free programs).


title: Sintesi di algoritmi con SKY

abstract:
  This paper describes the semantics and ideas about SKY, a logic programming
language intended in order to specify algorithmic strategies for the evaluation
of problems.


title: Intelligent Anticipated Exploration of Web Sites

abstract:
  In this paper we describe a web search agent, called Global Search Agent
(hereafter GSA for short). GSA integrates and enhances several search
techniques in order to achieve significant improvements in the user-perceived
quality of delivered information as compared to usual web search engines. GSA
features intelligent merging of relevant documents from different search
engines, anticipated selective exploration and evaluation of links from the
current result set, automated derivation of refined queries based on user
relevance feedback. System architecture as well as experimental accounts are
also illustrated.


title: Quality Control, Testing and Deployment Results in NIF ICCS

abstract:
  The strategy used to develop the NIF Integrated Computer Control System
(ICCS) calls for incremental cycles of construction and formal test to deliver
a total of 1 million lines of code. Each incremental release takes four to six
months to implement specific functionality and culminates when offline tests
conducted in the ICCS Integration and Test Facility verify functional,
performance, and interface requirements. Tests are then repeated on line to
confirm integrated operation in dedicated laser laboratories or ultimately in
the NIF. Test incidents along with other change requests are recorded and
tracked to closure by the software change control board (SCCB). Annual
independent audits advise management on software process improvements.
Extensive experience has been gained by integrating controls in the prototype
laser preamplifier laboratory. The control system installed in the preamplifier
lab contains five of the ten planned supervisory subsystems and seven of
sixteen planned front-end processors (FEPs). Beam alignment, timing, diagnosis
and laser pulse amplification up to 20 joules was tested through an automated
series of shots. Other laboratories have provided integrated testing of six
additional FEPs. Process measurements including earned-value, product size, and
defect densities provide software project controls and generate confidence that
the control system will be successfully deployed.


title: Visual DCT - Visual EPICS Database Configuration Tool

abstract:
  Visual DCT is an EPICS configuration tool completely written in Java and
therefore supported in various systems. It was developed to provide features
missing in existing configuration tools as Capfast and GDCT. Visually Visual
DCT resembles GDCT - records can be created, moved and linked, fields and links
can be easily modified. But Visual DCT offers more: using groups, records can
be grouped together in a logical block, which allows a hierarchical design.
Additionally indication of data flow direction using arrows makes the design
easier to understand. Visual DCT has a powerful DB parser, which allows
importing existing DB and DBD files. Output file is also DB file, all comments
and record order is preserved and visual data saved as comment, which allows
DBs to be edited in other tools or manually. Great effort has been taken and
many tricks used to optimize the performance in order to compensate for the
fact that Java is an interpreted language.


title: The SDSS SkyServer, Public Access to the Sloan Digital Sky Server Data

abstract:
  The SkyServer provides Internet access to the public Sloan Digital Sky Survey
(SDSS) data for both astronomers and for science education. This paper
describes the SkyServer goals and architecture. It also describes our
experience operating the SkyServer on the Internet. The SDSS data is public and
well-documented so it makes a good test platform for research on database
algorithms and performance.


title: Application Software Structure Enables Nif Operations Kirby W. Fong

abstract:
  The NIF Integrated Computer Control System (ICCS) application software uses a
set of service frameworks that assures uniform behavior spanning the front-end
processors (FEPs) and supervisor programs. This uniformity is visible both in
the way each program employs shared services and in the flexibility it affords
for attaching graphical user interfaces (GUIs). Uniformity of structure across
applications is desired for the benefit of programmers who will be maintaining
the many programs that constitute the ICCS. In this paper, the framework
components that have the greatest impact on the application structure are
discussed.


abstract:
  First Experiences Integrating PC Distributed I/O Into Argonne's ATLAS Control
System The roots of ATLAS (Argonne Tandem-Linac Accelerator System) date back
to the early 1960s. Located at the Argonne National Laboratory, the accelerator
has been designated a National User Facility, which focuses primarily on
heavy-ion nuclear physics. Like the accelerator it services, the control system
has been in a constant state of evolution. The present real-time portion of the
control system is based on the commercial product Vsystem [1]. While Vsystem
has always been capable of distributed I/O processing, the latest offering of
this product provides for the use of relatively inexpensive PC hardware and
software. This paper reviews the status of the ATLAS control system, and
describes first experiences with PC distributed I/O.


title:
Data Acquisition and Database Management System for Samsung
  Superconductor Test Facility

abstract:
  In order to fulfill the test requirement of KSTAR (Korea Superconducting
Tokamak Advanced Research) superconducting magnet system, a large scale
superconducting magnet and conductor test facility, SSTF (Samsung
Superconductor Test Facility), has been constructed at Samsung Advanced
Institute of Technology. The computer system for SSTF DAC (Data Acquisition and
Control) is based on UNIX system and VxWorks is used for the real-time OS of
the VME system. EPICS (Experimental Physics and Industrial Control System) is
used for the communication between IOC server and client. A database program
has been developed for the efficient management of measured data and a Linux
workstation with PENTIUM-4 CPU is used for the database server. In this paper,
the current status of SSTF DAC system, the database management system and
recent test results are presented.


title:
Application of digital regulated Power Supplies for Magnet Control at
  the Swiss Light Source

abstract:
  The Swiss Light Source (SLS) has in the order of 500 magnet power supplies
(PS) installed, ranging from from 3 A/20 V four-quadrant PS to a 950 A/1000 V
two-quadrant 3 Hz PS. All magnet PS have a local digital controller for a
digital regulation loop and a 5 MHz optical point-to-point link to the VME
level. The PS controller is running a pulse width/pulse repetition regulation
scheme, optional with multiple slave regulation loops. Many internal regulation
parameters and controller diagnostics are readable by the control system.
Industry Pack modules with standard VME carrier cards are used as VME hardware
interface with the high control density of eight links per VME card. The low
level EPICS interface is identical for all 500 magnet PS, including insertion
devices. The digital PS have proven to be very stable and reliable during
commissioning of the light source. All specifications were met for all PS. The
advanced diagnostic for the magnet PS turned out to be very useful not only for
the diagnostic of the PS but also to identify problems on the magnets.


title: Gemini MCAO Control System

abstract:
  The Gemini Observatory is planning to implement a Multi Conjugate Adaptive
Optics (MCAO) System as a facility instrument for the Gemini-South telescope.
The system will include 5 Laser Guide Stars, 3 Natural Guide Stars, and 3
Deformable mirrors optically conjugated at different altitudes to achieve
near-uniform atmospheric compensation over a 1 arc minute square field of view.
The control of such a system will be split into 3 main functions: the control
of the opto-mechanical assemblies of the whole system (including the Laser, the
Beam Transfer Optics and the Adaptive Optics bench), the control of the
Adaptive Optics System itself at a rate of 800FPS and the control of the safety
system. The control of the Adaptive Optics System is the most critical in terms
of real time performances. The control system will be an EPICS based system. In
this paper, we will describe the requirements for the whole MCAO control
system, preliminary designs for the control of the opto-mechanical devices and
architecture options for the control of the Adaptive Optics system and the
safety system.


title:
System Integration of High Level Applications during the Commissioning
  of the Swiss Light Source

abstract:
  The commissioning of the Swiss Light Source (SLS) started in Feb. 2000 with
the Linac, continued in May 2000 with the booster synchrotron and by Dec. 2000
first light in the storage ring were produced. The first four beam lines had to
be operational by August 2001. The thorough integration of all subsystems to
the control system and a high level of automation was prerequisite to meet the
tight time schedule. A careful balanced distribution of functionality into high
level and low level applications allowed an optimization of short development
cycles and high reliability of the applications. High level applications were
implemented as CORBA based client/server applications (tcl/tk and Java based
clients, C++ based servers), IDL applications using EZCA, medm/dm2k screens and
tcl/tk applications using CDEV. Low level applications were mainly built as
EPICS process databases, SNL state machines and customized drivers.
Functionality of the high level application was encapsulated and pushed to
lower levels whenever it has proven to be adequate. That enabled to reduce
machine setups to a handful of physical parameters and allow the usage of
standard EPICS tools for display, archiving and processing of complex physical
values. High reliability and reproducibility were achieved with that approach.


title: Distributed Computing for Localized and Multilayer Visualizations

abstract:
  The aim of this paper is to develop an approach to visualizations that
benefits from distributed computing. Three schemes of process distribution are
considered: parallel, pipeline, and expanding pipeline computations. Expanding
pipeline structure synthesizes the advantages and traits of both parallel and
pipeline computations. In expanding pipeline computing, a novel approach
presented in this paper, a multiplicity of processes are concurrently developed
in parallel and knotted processor pipelines. The theoretical foundations for
expanding pipeline computing as a computational process are in the domains of
alternating Turing machines, molecular computing, and E-machines. Expanding
pipeline computing constitutes the development of the conventional pipeline
architecture aimed at utilization of implicit parallel structures existing in
algorithms. Such structures appear in various kinds of visualization. Image
deriving and processing is a field that provides diverse opportunities for
utilization of the advantages of distributed computing. The most relevant to
the distributed architecture is stratified visualization with its two cases
based on data localization and layer separation. Visualization is treated here
as a special case of simulation. The conceptual approach to distributed
computing developed in this paper have been applied to visualization in a
computer support system, which is utilized in radiology and namely, for the
noninvasive treatment of brain aneurysms.


title:
Distributed Control System for the Test Interferometer of the ALMA
  Project

abstract:
  The control system (TICS) for the test interferometer being built to support
the development of the Atacama Large Millimeter Array (ALMA)will itself be a
prototype for the final ALMA array, providing a test for the distributed
control system under development. TICS will be based on the ALMA Common
Software (ACS) (developed at the European Southern Observatory), which provides
CORBA-based services and a device management framework for the control
software.
  Simple device controllers will run on single board computers, one of which
(known as an LCU) is located at each antenna; whereas complex, compound device
controllers may run on centrally located computers. In either circumstance,
client programs may obtain direct CORBA references to the devices and their
properties. Monitor and control requests are sent to devices or properties,
which then process and forward the commands to the appropriate hardware devices
as required. Timing requirements are met by tagging commands with (future)
timestamps synchronized to a timing pulse, which is regulated by a central
reference generator, and is distributed to all hardware devices in the array.
Monitoring is provided through a publish/subscribe CORBA-based service.


title: Building Multi-Platform User Interfaces with UIML

abstract:
  There has been a widespread emergence of computing devices in the past few
years that go beyond the capabilities of traditional desktop computers.
However, users want to use the same kinds of applications and access the same
data and information on these appliances that they can access on their desktop
computers. The user interfaces for these platforms go beyond the traditional
interaction metaphors. It is a challenge to build User Interfaces (UIs) for
these devices of differing capabilities that allow the end users to perform the
same kinds of tasks. The User Interface Markup Language (UIML) is an XML-based
language that allows the canonical description of UIs for different platforms.
We describe the language features of UIML that facilitate the development of
multi-platform UIs. We also describe the key aspects of our approach that makes
UIML succeed where previous approaches failed, namely the division in the
representation of a UI, the use of a generic vocabulary, and an integrated
development environment specifically designed for transformation-based UI
development. Finally we describe the initial details of a multi-step usability
engineering process for building multi-platform UI using UIML.


title:
A Multi-Step Process for Generating Multi-Platform User Interfaces using
  UIML

abstract:
  There has been a widespread emergence of computing devices in the past few
years that go beyond the capabilities of traditional desktop computers. These
devices have varying input/output characteristics, modalities and interaction
mechanisms. However, users want to use the same kinds of applications and
access the same data and information on these appliances that they can access
on their desktop computers. The user interfaces for these devices and platforms
go beyond the traditional interaction metaphors. It is a challenge to build
User Interfaces (UIs) for these devices of differing capabilities that allow
the end users to perform the same kinds of tasks. The User Interface Markup
Language (UIML) is an XML-based language that allows the canonical description
of UIs for different platforms. We present a multi-step transformation-based
framework for building Multi-Platform User Interfaces using UIML. We describe
the language features of UIML that facilitate the development of multi-platform
UIs, the multi-step process involved in our framework and the transformations
needed to build the UIs.


title: Next Generation EPICS Interface to Abstract Data

abstract:
  The set of externally visible properties associated with process variables in
the Experimental Physics and Industrial Control System (EPICS) is predefined in
the EPICS base distribution and is therefore not extensible by plug-compatible
applications. We believe that this approach, while practical for early versions
of the system with a smaller user base, is now severely limiting expansion of
the high-level application tool set for EPICS. To eliminate existing barriers,
we propose a new C++ based interface to abstract containerized data. This paper
describes the new interface, its application to message passing in distributed
systems, its application to direct communication between tightly coupled
programs co-resident in an address space, and its paramount position in an
emerging role for EPICS - the integration of dissimilar systems.


title:
Upgrade of Spring-8 Beamline Network with Vlan Technology Over Gigabit
  Ethernet

abstract:
  The beamline network system at SPring-8 consists of three LANs; a BL-LAN for
beamline component control, a BL-USER-LAN for beamline experimental users and
an OA-LAN for the information services. These LANs are interconnected by a
firewall system. Since the network traffic and the number of beamlines have
increased, we upgraded the backbone of BL-USER-LAN from Fast Ethernet to
Gigabit Ethernet. And then, to establish the independency of a beamline and to
raise flexibility of every beamline, we also introduced the IEEE802.1Q Virtual
LAN (VLAN) technology into the BL-USER-LAN. We discuss here a future plan to
build the firewall system with hardware load balancers.


title: The ESRF TANGO control system status

abstract:
  TANGO is an object oriented control system toolkit based on CORBA presently
under development at the ESRF. IN this paper, the TANGO philosophy is briefly
presented. All the existing tools developed around TANGO will also be
presented. This include a code genrator, a WEB interface to TANGO objects, an
administration tool and an interface to LabView. Finally, an xample of a TANGO
device server for OPC device is given.


title: Versatile Data Acquisition and Controls for Epics Using Vme-Based Fpgas

abstract:
  Field-Programmable Gate Arrays (FPGAs) have provided Thomas Jefferson
National Accelerator Facility (Jefferson Lab) with versatile VME-based data
acquisition and control interfaces with minimal development times. FPGA designs
have been used to interface to VME and provide control logic for numerous
systems. The building blocks of these logic designs can be tailored to the
individual needs of each system and provide system operators with read-backs
and controls via a VME interface to an EPICS based computer. This versatility
allows the system developer to choose components and define operating
parameters and options that are not readily available commercially. Jefferson
Lab has begun developing standard FPGA libraries that result in quick turn
around times and inexpensive designs.


title:
A Dual Digital Signal Processor VME Board For Instrumentation And
  Control Applications

abstract:
  A Dual Digital Signal Processing VME Board was developed for the Continuous
Electron Beam Accelerator Facility (CEBAF) Beam Current Monitor (BCM) system at
Jefferson Lab. It is a versatile general-purpose digital signal processing
board using an open architecture, which allows for adaptation to various
applications. The base design uses two independent Texas Instrument (TI)
TMS320C6711, which are 900 MFLOPS floating-point digital signal processors
(DSP). Applications that require a fixed point DSP can be implemented by
replacing the baseline DSP with the pin-for-pin compatible TMS320C6211. The
design can be manufactured with a reduced chip set without redesigning the
printed circuit board. For example it can be implemented as a single-channel
DSP with no analog I/O.


title: Large-Scale Corba-Distributed Software Framework for Nif Controls

abstract:
  The Integrated Computer Control System (ICCS) is based on a scalable software
framework that is distributed over some 325 computers throughout the NIF
facility. The framework provides templates and services at multiple levels of
abstraction for the construction of software applications that communicate via
CORBA (Common Object Request Broker Architecture). Various forms of
object-oriented software design patterns are implemented as templates to be
extended by application software. Developers extend the framework base classes
to model the numerous physical control points, thereby sharing the
functionality defined by the base classes. About 56,000 software objects each
individually addressed through CORBA are to be created in the complete ICCS.
Most objects have a persistent state that is initialized at system start-up and
stored in a database. Additional framework services are provided by centralized
server programs that implement events, alerts, reservations, message logging,
database/file persistence, name services, and process management. The ICCS
software framework approach allows for efficient construction of a software
system that supports a large number of distributed control points representing
a complex control application.


title: SNS Timing System

abstract:
  This poster describes the timing system being designed for Spallation Neutron
Source being built at Oak Ridge National lab.


title: Modernising the ESRF control system with GNU/Linux

abstract:
  he ESRF control system is in the process of being modernised. The present
contrsystem is based on VME, 10 MHz Ethernet, OS9, Solaris, HP-UX, NFS/RPC,
Motif and C. The new control system will be based on compact PCI, 100 MHz
Ethernet, Linux, Windows, Solaris, CORBA/IIOP, C++, Java and Python. The main
frontend operating system will be GNU/Linux running on Intel/x86 and
Motorola/68k. Linux will also be used on handheld devices for mobile control.
This poster describes how GNU/Linux is being used to modernise the control
system and what problems have been encountered so far


title: Experiences with advanced CORBA services

abstract:
  The Common Object Request Broker Architecture (CORBA) is successfully used in
many control systems (CS) for data transfer and device modeling. Communication
rates below 1 millisecond, high reliability, scalability, language independence
and other features make it very attractive. For common types of applications
like error logging, alarm messaging or slow monitoring, one can benefit from
standard CORBA services that are implemented by third parties and save
tremendous amount of developing time. We have started using few CORBA services
on our previous CORBA-based control system for the light source ANKA [1] and
use now several CORBA services for the ALMA Common Software (ACS) [2], the core
of the control system of the Atacama Large Millimeter Array. Our experiences
with the interface repository (IFR), the implementation repository, the naming
service, the property service, telecom log service and the notify service from
different vendors are presented. Performance and scalability benchmarks have
been performed.


title: Open Source Real Time Operating Systems Overview

abstract:
  Modern control systems applications are often built on top of a real time
operating system (RTOS) which provides the necessary hardware abstraction as
well as scheduling, networking and other services. Several open source RTOS
solutions are publicly available, which is very attractive, both from an
economic (no licensing fees) as well as from a technical (control over the
source code) point of view. This contribution gives an overview of the RTLinux
and RTEMS systems (architecture, development environment, API etc.). Both
systems feature most popular CPUs, several APIs (including Posix), networking,
portability and optional commercial support. Some performance figures are
presented, focusing on interrupt latency and context switching delay.


title:
Data Access - Experiences Implementing an Object Oriented Library on
  Various Platforms

abstract:
  Data Access will be the next generation data abstraction layer for EPICS. Its
implementation in C++ brought up a number of issues that are related to object
oriented technology's impact on CPU and memory usage.
  What is gained by the new abstract interface? What is the price that has to
be paid for these gains? What compromises seem applicable and affordable?
  This paper discusses tests that have been made about performance and memory
usage as well as the different measures that have been taken to optimize the
situation.


title: User-friendly explanations for constraint programming

abstract:
  In this paper, we introduce a set of tools for providing user-friendly
explanations in an explanation-based constraint programming system. The idea is
to represent the constraints of a problem as an hierarchy (a tree). Users are
then represented as a set of understandable nodes in that tree (a cut).
Classical explanations (sets of system constraints) just need to get projected
on that representation in order to be understandable by any user. We present
here the main interests of this idea.


title: Arc consistency for soft constraints

abstract:
  The notion of arc consistency plays a central role in constraint
satisfaction. It is known that the notion of local consistency can be extended
to constraint optimisation problems defined by soft constraint frameworks based
on an idempotent cost combination operator. This excludes non idempotent
operators such as + which define problems which are very important in practical
applications such as Max-CSP, where the aim is to minimize the number of
violated constraints. In this paper, we show that using a weak additional axiom
satisfied by most existing soft constraints proposals, it is possible to define
a notion of soft arc consistency that extends the classical notion of arc
consistency and this even in the case of non idempotent cost combination
operators. A polynomial time algorithm for enforcing this soft arc consistency
exists and its space and time complexities are identical to that of enforcing
arc consistency in CSPs when the cost combination operator is strictly
monotonic (for example Max-CSP). A directional version of arc consistency is
potentially even stronger than the non-directional version, since it allows non
local propagation of penalties. We demonstrate the utility of directional arc
consistency by showing that it not only solves soft constraint problems on
trees, but that it also implies a form of local optimality, which we call arc
irreducibility.


title:
An Integrated Development Environment for Declarative Multi-Paradigm
  Programming

abstract:
  In this paper we present CIDER (Curry Integrated Development EnviRonment), an
analysis and programming environment for the declarative multi-paradigm
language Curry. CIDER is a graphical environment to support the development of
Curry programs by providing integrated tools for the analysis and visualization
of programs. CIDER is completely implemented in Curry using libraries for GUI
programming (based on Tcl/Tk) and meta-programming. An important aspect of our
environment is the possible adaptation of the development environment to other
declarative source languages (e.g., Prolog or Haskell) and the extensibility
w.r.t. new analysis methods. To support the latter feature, the lazy evaluation
strategy of the underlying implementation language Curry becomes quite useful.


title:
Combining Propagation Information and Search Tree Visualization using
  ILOG OPL Studio

abstract:
  In this paper we give an overview of the current state of the graphical
features provided by ILOG OPL Studio for debugging and performance tuning of
OPL programs or external ILOG Solver based applications. This paper focuses on
combining propagation and search information using the Search Tree view and the
Propagation Spy. A new synthetic view is presented: the Christmas Tree, which
combines the Search Tree view with statistics on the efficiency of the domain
reduction and on the number of the propagation events triggered.


title:
On the Design of a Tool for Supporting the Construction of Logic
  Programs

abstract:
  Environments for systematic construction of logic programs are needed in the
academy as well as in the industry. Such environments should support well
defined construction methods and should be able to be extended and interact
with other programming tools like debuggers and compilers. We present a variant
of the Deville methodology for logic program development, and the design of a
tool for supporting the methodology. Our aim is to facilitate the learning of
logic programming and to set the basis of more sophisticated tools for program
development.


title:
Proceedings of the Eleventh Workshop on Logic Programming Environments
  (WLPE'01)

abstract:
  The Eleventh Workshop on Logic Programming Environments (WLPE'01) was one in
a series of international workshops in the topic area. It was held on December
1, 2001 in Paphos, Cyprus as a post-conference workshop at ICLP 2001. Eight
refereed papers were presented at the conference. A majority of the papers
involved, in some way, constraint logic programming and tools for software
development. Other topics areas addressed include execution visualization,
instructional aids (for learning users), software maintenance (including
debugging), and provisions for new paradigms.


title:
Prototyping CLP(FD) Tracers: a Trace Model and an Experimental
  Validation Environment

abstract:
  Developing and maintaining CLP programs requires visualization and
explanation tools. However, existing tools are built in an ad hoc way.
Therefore porting tools from one platform to another is very difficult. We have
shown in previous work that, from a fine-grained execution trace, a number of
interesting views about logic program executions could be generated by trace
analysis.
  In this article, we propose a trace model for constraint solving by
narrowing. This trace model is the first one proposed for CLP(FD) and does not
pretend to be the ultimate one. We also propose an instrumented
meta-interpreter in order to experiment with the model. Furthermore, we show
that the proposed trace model contains the necessary information to build known
and useful execution views. This work sets the basis for generic execution
analysis of CLP(FD) programs.


title: SNS Standard Power Supply Interface

abstract:
  The SNS has developed a standard power supply interface for the approximately
350 magnet power supplies in the SNS accumulator ring, Linac and transport
lines. Power supply manufacturers are providing supplies compatible with the
standard interface. The SNS standard consists of a VME based power supply
controller module (PSC) and a power supply interface unit (PSI) that mounts on
the power supply. Communication between the two is via a pair of multimode
fibers. This PSI/PSC system supports one 16-bit analog reference, four 16-bit
analog readbacks, fifteen digital commands and sixteen digital status bits in a
single fiber-isolated module. The system can send commands to the supplies and
read data from them synchronized to an external signal at up to a 10KHz rate.
The PSC time stamps and stores this data in a circular buffer so historical
data leading up to a fault event can be analyzed. The PSC contains a serial
port so that local testing of hardware can be accomplished with a laptop. This
paper concentrates on the software being provided to control the power supply.
It includes the EPICS driver; software to test hardware and power supplies via
the serial port and VME interface.


title:
The Overview of the National Ignition Facility Distributed Computer
  Control System

abstract:
  The Integrated Computer Control System (ICCS) for the National Ignition
Facility (NIF) is a layered architecture of 300 front-end processors (FEP)
coordinated by supervisor subsystems including automatic beam alignment and
wavefront control, laser and target diagnostics, pulse power, and shot control
timed to 30 ps. FEP computers incorporate either VxWorks on PowerPC or Solaris
on UltraSPARC processors that interface to over 45,000 control points attached
to VME-bus or PCI-bus crates respectively. Typical devices are stepping motors,
transient digitizers, calorimeters, and photodiodes. The front-end layer is
divided into another segment comprised of an additional 14,000 control points
for industrial controls including vacuum, argon, synthetic air, and safety
interlocks implemented with Allen-Bradley programmable logic controllers
(PLCs). The computer network is augmented asynchronous transfer mode (ATM) that
delivers video streams from 500 sensor cameras monitoring the 192 laser beams
to operator workstations. Software is based on an object-oriented framework
using CORBA distribution that incorporates services for archiving, machine
configuration, graphical user interface, monitoring, event logging, scripting,
alert management, and access control. Software coding using a mixed language
environment of Ada95 and Java is one-third complete at over 300 thousand source
lines. Control system installation is currently under way for the first 8
beams, with project completion scheduled for 2008.


title: HyperPro An integrated documentation environment for CLP

abstract:
  The purpose of this paper is to present some functionalities of the HyperPro
System. HyperPro is a hypertext tool which allows to develop Constraint Logic
Programming (CLP) together with their documentation. The text editing part is
not new and is based on the free software Thot. A HyperPro program is a Thot
document written in a report style. The tool is designed for CLP but it can be
adapted to other programming paradigms as well. Thot offers navigation and
editing facilities and synchronized static document views. HyperPro has new
functionalities such as document exportations, dynamic views (projections),
indexes and version management. Projection is a mechanism for extracting and
exporting relevant pieces of code program or of document according to specific
criteria. Indexes are useful to find the references and occurrences of a
relation in a document, i.e., where its predicate definition is found and where
a relation is used in other programs or document versions and, to translate
hyper-texts links into paper references. It still lack importation facilities.


title:
Virtual Laboratory: Enabling On-Demand Drug Design with the World Wide
  Grid

abstract:
  Computational Grids are emerging as a popular paradigm for solving
large-scale compute and data intensive problems in science, engineering, and
commerce. However, application composition, resource management and scheduling
in these environments is a complex undertaking. In this paper, we illustrate
the creation of a virtual laboratory environment by leveraging existing Grid
technologies to enable molecular modeling for drug design on distributed
resources. It involves screening millions of molecules of chemical compounds
against a protein target, chemical database (CDB) to identify those with
potential use for drug design. We have grid-enabled the molecular docking
process by composing it as a parameter sweep application using the Nimrod-G
tools. We then developed new tools for remote access to molecules in CDB small
molecule database. The Nimrod-G resource broker along with molecule CDB data
broker is used for scheduling and on-demand processing of jobs on distributed
grid resources. The results demonstrate the ease of use and suitability of the
Nimrod-G and virtual laboratory tools.


title:
A Computational Economy for Grid Computing and its Implementation in the
  Nimrod-G Resource Brok

abstract:
  Computational Grids, coupling geographically distributed resources such as
PCs, workstations, clusters, and scientific instruments, have emerged as a next
generation computing platform for solving large-scale problems in science,
engineering, and commerce. However, application development, resource
management, and scheduling in these environments continue to be a complex
undertaking. In this article, we discuss our efforts in developing a resource
management system for scheduling computations on resources distributed across
the world with varying quality of service. Our service-oriented grid computing
system called Nimrod-G manages all operations associated with remote execution
including resource discovery, trading, scheduling based on economic principles
and a user defined quality of service requirement. The Nimrod-G resource broker
is implemented by leveraging existing technologies such as Globus, and provides
new services that are essential for constructing industrial-strength Grids. We
discuss results of preliminary experiments on scheduling some parametric
computations using the Nimrod-G resource broker on a world-wide grid testbed
that spans five continents.


title: An Environment for the Exploration of Non Monotonic Logic Programs

abstract:
  Stable Model Semantics and Well Founded Semantics have been shown to be very
useful in several applications of non-monotonic reasoning. However, Stable
Models presents a high computational complexity, whereas Well Founded Semantics
is easy to compute and provides an approximation of Stable Models. Efficient
engines exist for both semantics of logic programs. This work presents a
computational integration of two of such systems, namely XSB and SMODELS. The
resulting system is called XNMR, and provides an interactive system for the
exploration of both semantics. Aspects such as modularity can be exploited in
order to ease debugging of large knowledge bases with the usual Prolog
debugging techniques and an interactive environment. Besides, the use of a full
Prolog system as a front-end to a Stable Models engine augments the language
usually accepted by such systems.


title:
Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes
  Polynomial Time

abstract:
  We introduce the smoothed analysis of algorithms, which is a hybrid of the
worst-case and average-case analysis of algorithms. In smoothed analysis, we
measure the maximum over inputs of the expected performance of an algorithm
under small random perturbations of that input. We measure this performance in
terms of both the input size and the magnitude of the perturbations. We show
that the simplex algorithm has polynomial smoothed complexity.


title:
Predicting RNA Secondary Structures with Arbitrary Pseudoknots by
  Maximizing the Number of Stacking Pairs

abstract:
  The paper investigates the computational problem of predicting RNA secondary
structures. The general belief is that allowing pseudoknots makes the problem
hard. Existing polynomial-time algorithms are heuristic algorithms with no
performance guarantee and can only handle limited types of pseudoknots. In this
paper we initiate the study of predicting RNA secondary structures with a
maximum number of stacking pairs while allowing arbitrary pseudoknots. We
obtain two approximation algorithms with worst-case approximation ratios of 1/2
and 1/3 for planar and general secondary structures,respectively. For an RNA
sequence of $n$ bases, the approximation algorithm for planar secondary
structures runs in $O(n^3)$ time while that for the general case runs in linear
time. Furthermore, we prove that allowing pseudoknots makes it NP-hard to
maximize the number of stacking pairs in a planar secondary structure. This
result is in contrast with the recent NP-hard results on psuedoknots which are
based on optimizing some general and complicated energy functions.


title: A comparison of Zeroes and Ones of a Boolean Polynomial

abstract:
  In this paper we consider the computational complexity of the following
problem. Let $f$ be a Boolean polynomial. What value of $f$, 0 or 1, is taken
more frequently? The problem is solved in polynomial time for polynomials of
degrees 1,2. The next case of degree 3 appears to be PP-complete under
polynomial reductions in the class of promise problems. The proof is based on
techniques of quantum computation.


title: Meaningful Information

abstract:
  The information in an individual finite object (like a binary string) is
commonly measured by its Kolmogorov complexity. One can divide that information
into two parts: the information accounting for the useful regularity present in
the object and the information accounting for the remaining accidental
information. There can be several ways (model classes) in which the regularity
is expressed. Kolmogorov has proposed the model class of finite sets,
generalized later to computable probability mass functions. The resulting
theory, known as Algorithmic Statistics, analyzes the algorithmic sufficient
statistic when the statistic is restricted to the given model class. However,
the most general way to proceed is perhaps to express the useful information as
a recursive function. The resulting measure has been called the
``sophistication'' of the object. We develop the theory of recursive functions
statistic, the maximum and minimum value, the existence of absolutely
nonstochastic objects (that have maximal sophistication--all the information in
them is meaningful and there is no residual randomness), determine its relation
with the more restricted model classes of finite sets, and computable
probability distributions, in particular with respect to the algorithmic
(Kolmogorov) minimal sufficient statistic, the relation to the halting problem
and further algorithmic properties.

categories: cs.CC math-ph math.MP math.PR physics.data-an


title: The similarity metric

abstract:
  A new class of distances appropriate for measuring similarity relations
between sequences, say one type of similarity per distance, is studied. We
propose a new ``normalized information distance'', based on the noncomputable
notion of Kolmogorov complexity, and show that it is in this class and it
minorizes every computable distance in the class (that is, it is universal in
that it discovers all computable similarities). We demonstrate that it is a
metric and call it the {\em similarity metric}. This theory forms the
foundation for a new practical tool. To evidence generality and robustness we
give two distinctive applications in widely divergent areas using standard
compression programs like gzip and GenCompress. First, we compare whole
mitochondrial genomes and infer their evolutionary history. This results in a
first completely automatic computed whole mitochondrial phylogeny tree.
Secondly, we fully automatically compute the language tree of 52 different
languages.

categories: cs.CC cond-mat.stat-mech cs.CE cs.CV math.CO math.MG math.ST physics.data-an q-bio.GN stat.TH


title: Overview of the NSTX Control System

abstract:
  The National Spherical Torus Experiment (NSTX) is an innovative magnetic
fusion device that was constructed by the Princeton Plasma Physics Laboratory
(PPPL) in collaboration with the Oak Ridge National Laboratory, Columbia
University, and the University of Washington at Seattle. Since achieving first
plasma in 1999, the device has been used for fusion research through an
international collaboration of over twenty institutions. The NSTX is operated
through a collection of control systems that encompass a wide range of
technology, from hardwired relay controls to real-time control systems with
giga-FLOPS of capability. This paper presents a broad introduction to the
control systems used on NSTX, with an emphasis on the computing controls, data
acquisition, and synchronization systems.


title:
Some Facets of Complexity Theory and Cryptography: A Five-Lectures
  Tutorial

abstract:
  In this tutorial, selected topics of cryptology and of computational
complexity theory are presented. We give a brief overview of the history and
the foundations of classical cryptography, and then move on to modern
public-key cryptography. Particular attention is paid to cryptographic
protocols and the problem of constructing the key components of such protocols
such as one-way functions. A function is one-way if it is easy to compute, but
hard to invert. We discuss the notion of one-way functions both in a
cryptographic and in a complexity-theoretic setting. We also consider
interactive proof systems and present some interesting zero-knowledge
protocols. In a zero-knowledge protocol one party can convince the other party
of knowing some secret information without disclosing any bit of this
information. Motivated by these protocols, we survey some complexity-theoretic
results on interactive proof systems and related complexity classes.


title: Towards a characterization of the star-free sets of integers

abstract:
  Let U be a numeration system, a set X of integers is U-star-free if the set
made up of the U-representations of the elements in X is a star-free regular
language. Answering a question of A. de Luca and A. Restivo, we obtain a
complete logical characterization of the U-star-free sets of integers for
suitable numeration systems related to a Pisot number and in particular for
integer base systems. For these latter systems, we study as well the problem of
the base dependence. Finally, the case of k-adic systems is also investigated.


title: Bayesian Logic Programs

abstract:
  Bayesian networks provide an elegant formalism for representing and reasoning
about uncertainty using probability theory. Theyare a probabilistic extension
of propositional logic and, hence, inherit some of the limitations of
propositional logic, such as the difficulties to represent objects and
relations. We introduce a generalization of Bayesian networks, called Bayesian
logic programs, to overcome these limitations. In order to represent objects
and relations it combines Bayesian networks with definite clause logic by
establishing a one-to-one mapping between ground atoms and random variables. We
show that Bayesian logic programs combine the advantages of both definite
clause logic and Bayesian networks. This includes the separation of
quantitative and qualitative aspects of the model. Furthermore, Bayesian logic
programs generalize both Bayesian networks as well as logic programs. So, many
ideas developed


title:
Hypotheses Founded Semantics of Logic Programs for Information
  Integration in Multi-Valued Logics

abstract:
  We address the problem of integrating information coming from different
sources. The information consists of facts that a central server collects and
tries to combine using (a) a set of logical rules, i.e. a logic program, and
(b) a hypothesis representing the server's own estimates. In such a setting
incomplete information from a source or contradictory information from
different sources necessitate the use of many-valued logics in which programs
can be evaluated and hypotheses can be tested. To carry out such activities we
propose a formal framework based on bilattices such as Belnap's four-valued
logics. In this framework we work with the class of programs defined by Fitting
and we develop a theory for information integration.
  We also establish an intuitively appealing connection between our hypothesis
testing mechanism on the one hand, and the well-founded semantics and
Kripke-Kleene semantics of Datalog programs with negation, on the other hand.


title: Gradient-based Reinforcement Planning in Policy-Search Methods

abstract:
  We introduce a learning method called ``gradient-based reinforcement
planning'' (GREP). Unlike traditional DP methods that improve their policy
backwards in time, GREP is a gradient-based method that plans ahead and
improves its policy before it actually acts in the environment. We derive
formulas for the exact policy gradient that maximizes the expected future
reward and confirm our ideas with numerical experiments.


title: On a Special Case of the Generalized Neighbourhood Problem

abstract:
  For a given finite class of finite graphs H, a graph G is called a
realization of H if the neighbourhood of its any vertex induces the subgraph
isomorphic to a graph of H. We consider the following problem known as the
Generalized Neighbourhood Problem (GNP): given a finite class of finite graphs
H, does there exist a non-empty graph G that is a realization of H? In fact,
there are two modifications of that problem, namely the finite (the existence
of a finite realization is required) and infinite one (the realization is
required to be infinite). In this paper we show that GNP and its modifications
for all finite classes H of finite graphs are reduced to the same problems with
an additional restriction on H. Namely, the orders of any two graphs of H are
equal and every graph of H has exactly s dominating vertices.


title:
One-way communication complexity and the Neciporuk lower bound on
  formula size

abstract:
  In this paper the Neciporuk method for proving lower bounds on the size of
Boolean formulae is reformulated in terms of one-way communication complexity.
We investigate the scenarios of probabilistic formulae, nondeterministic
formulae, and quantum formulae. In all cases we can use results about one-way
communication complexity to prove lower bounds on formula size. In the latter
two cases we newly develop the employed communication complexity bounds. The
main results regarding formula size are as follows: A polynomial size gap
between probabilistic/quantum and deterministic formulae. A near-quadratic size
gap for nondeterministic formulae with limited access to nondeterministic bits.
A near quadratic lower bound on quantum formula size, as well as a polynomial
separation between the sizes of quantum formulae with and without multiple read
random inputs. The methods for quantum and probabilistic formulae employ a
variant of the Neciporuk bound in terms of the VC-dimension. Regarding
communication complexity we give optimal separations between one-way and
two-way protocols in the cases of limited nondeterministic and quantum
communication, and we show that zero-error quantum one-way communication
complexity asymptotically equals deterministic one-way communication complexity
for total functions.


title: New RBF collocation methods and kernel RBF with applications

abstract:
  A few novel radial basis function (RBF) discretization schemes for partial
differential equations are developed in this study. For boundary-type methods,
we derive the indirect and direct symmetric boundary knot methods. Based on the
multiple reciprocity principle, the boundary particle method is introduced for
general inhomogeneous problems without using inner nodes. For domain-type
schemes, by using the Green integral we develop a novel Hermite RBF scheme
called the modified Kansa method, which significantly reduces calculation
errors at close-to-boundary nodes. To avoid Gibbs phenomenon, we present the
least square RBF collocation scheme. Finally, five types of the kernel RBF are
also briefly presented.


title: A procedure for unsupervised lexicon learning

abstract:
  We describe an incremental unsupervised procedure to learn words from
transcribed continuous speech. The algorithm is based on a conservative and
traditional statistical model, and results of empirical tests show that it is
competitive with other algorithms that have been proposed recently for this
task.


title: A Statistical Model for Word Discovery in Transcribed Speech

abstract:
  A statistical model for segmentation and word discovery in continuous speech
is presented. An incremental unsupervised learning algorithm to infer word
boundaries based on this model is described. Results of empirical tests showing
that the algorithm is competitive with other models that have been used for
similar tasks are also presented.


title: An Average Case NP-Complete Graph Coloring Problem

abstract:
  NP-complete problems should be hard on some instances but those may be
extremely rare. On generic instances many such problems, especially related to
random graphs, have been proven easy. We show the intractability of random
instances of a graph coloring problem: this graph problem is hard on average
unless all NP problem under all samplable (i.e., generatable in polynomial
time) distributions are easy. Worst case reductions use special gadgets and
typically map instances into a negligible fraction of possible outputs. Ours
must output nearly random graphs and avoid any super-polynomial distortion of
probabilities.


title:
Program schemes with binary write-once arrays and the complexity classes
  they capture

abstract:
  We study a class of program schemes, NPSB, in which, aside from basic
assignments, non-deterministic guessing and while loops, we have access to
arrays; but where these arrays are binary write-once in that they are
initialized to `zero' and can only ever be set to `one'. We show, amongst other
results, that: NPSB can be realized as a vectorized Lindstrom logic; there are
problems accepted by program schemes of NPSB that are not definable in the
bounded-variable infinitary logic ${\cal L}^\omega_{\infty\omega}$; all
problems accepted by the program schemes of NPSB have a zero-one law; and on
ordered structures, NPSB captures the complexity class $[ L]^[{\scriptsize
NP\normalsize}]$. The class of program schemes NPSB is actually the union of an
infinite hierarchy of classes of program schemes. When we amend the semantics
of our program schemes slightly, we find that the classes of the resulting
hierarchy capture the complexity classes $\Sigma^p_i$ (where $i\geq 1$) of the
Polynomial Hierarchy PH. Finally, we give logical equivalences of the
complexity-theoretic question `Does NP equal PSPACE?' where the logics (and
classes of program schemes) involved define only problems with zero-one laws
(and so do not define some computationally trivial problems).


title:
Using a Support-Vector Machine for Japanese-to-English Translation of
  Tense, Aspect, and Modality

abstract:
  This paper describes experiments carried out using a variety of
machine-learning methods, including the k-nearest neighborhood method that was
used in a previous study, for the translation of tense, aspect, and modality.
It was found that the support-vector machine method was the most precise of all
the methods tested.


title: Part of Speech Tagging in Thai Language Using Support Vector Machine

abstract:
  The elastic-input neuro tagger and hybrid tagger, combined with a neural
network and Brill's error-driven learning, have already been proposed for the
purpose of constructing a practical tagger using as little training data as
possible. When a small Thai corpus is used for training, these taggers have
tagging accuracies of 94.4% and 95.5% (accounting only for the ambiguous words
in terms of the part of speech), respectively. In this study, in order to
construct more accurate taggers we developed new tagging methods using three
machine learning methods: the decision-list, maximum entropy, and support
vector machine methods. We then performed tagging experiments by using these
methods. Our results showed that the support vector machine method has the best
precision (96.1%), and that it is capable of improving the accuracy of tagging
in the Thai language. Finally, we theoretically examined all these methods and
discussed how the improvements were achived.


title:
Universal Model for Paraphrasing -- Using Transformation Based on a
  Defined Criteria --

abstract:
  This paper describes a universal model for paraphrasing that transforms
according to defined criteria. We showed that by using different criteria we
could construct different kinds of paraphrasing systems including one for
answering questions, one for compressing sentences, one for polishing up, and
one for transforming written language to spoken language.


title:
A Logic Programming Approach to Knowledge-State Planning: Semantics and
  Complexity

abstract:
  We propose a new declarative planning language, called K, which is based on
principles and methods of logic programming. In this language, transitions
between states of knowledge can be described, rather than transitions between
completely described states of the world, which makes the language well-suited
for planning under incomplete knowledge. Furthermore, it enables the use of
default principles in the planning process by supporting negation as failure.
Nonetheless, K also supports the representation of transitions between states
of the world (i.e., states of complete knowledge) as a special case, which
shows that the language is very flexible. As we demonstrate on particular
examples, the use of knowledge states may allow for a natural and compact
problem representation. We then provide a thorough analysis of the
computational complexity of K, and consider different planning problems,
including standard planning and secure planning (also known as conformant
planning) problems. We show that these problems have different complexities
under various restrictions, ranging from NP to NEXPTIME in the propositional
case. Our results form the theoretical basis for the DLV^K system, which
implements the language K on top of the DLV logic programming system.


title: A Tight Upper Bound on the Number of Candidate Patterns

abstract:
  In the context of mining for frequent patterns using the standard levelwise
algorithm, the following question arises: given the current level and the
current set of frequent patterns, what is the maximal number of candidate
patterns that can be generated on the next level? We answer this question by
providing a tight upper bound, derived from a combinatorial result from the
sixties by Kruskal and Katona. Our result is useful to reduce the number of
database scans.


title: Representation of Uncertainty for Limit Processes

abstract:
  Many mathematical models utilize limit processes. Continuous functions and
the calculus, differential equations and topology, all are based on limits and
continuity. However, when we perform measurements and computations, we can
achieve only approximate results. In some cases, this discrepancy between
theoretical schemes and practical actions changes drastically outcomes of a
research and decision-making resulting in uncertainty of knowledge. In the
paper, a mathematical approach to such kind of uncertainty, which emerges in
computation and measurement, is suggested on the base of the concept of a fuzzy
limit. A mathematical technique is developed for differential models with
uncertainty. To take into account the intrinsic uncertainty of a model, it is
suggested to use fuzzy derivatives instead of conventional derivatives of
functions in this model.


title: DNA Self-Assembly For Constructing 3D Boxes

abstract:
  We propose a mathematical model of DNA self-assembly using 2D tiles to form
3D nanostructures. This is the first work to combine studies in self-assembly
and nanotechnology in 3D, just as Rothemund and Winfree did in the 2D case. Our
model is a more precise superset of their Tile Assembly Model that facilitates
building scalable 3D molecules. Under our model, we present algorithms to build
a hollow cube, which is intuitively one of the simplest 3D structures to
construct. We also introduce five basic measures of complexity to analyze these
algorithms. Our model and algorithmic techniques are applicable to more complex
2D and 3D nanostructures.


title: A Straightforward Approach to Morphological Analysis and Synthesis

abstract:
  In this paper we present a lexicon-based approach to the problem of
morphological processing. Full-form words, lemmas and grammatical tags are
interconnected in a DAWG. Thus, the process of analysis/synthesis is reduced to
a search in the graph, which is very fast and can be performed even if several
pieces of information are missing from the input. The contents of the DAWG are
updated using an on-line incremental process. The proposed approach is language
independent and it does not utilize any morphophonetic rules or any other
special linguistic information.


title: Interactive Constrained Association Rule Mining

abstract:
  We investigate ways to support interactive mining sessions, in the setting of
association rule mining. In such sessions, users specify conditions (queries)
on the associations to be generated. Our approach is a combination of the
integration of querying conditions inside the mining phase, and the incremental
querying of already generated associations. We present several concrete
algorithms and compare their performance.


title: Computing the average parallelism in trace monoids

abstract:
  The {\em height} of a trace is the height of the corresponding heap of pieces
in Viennot's representation, or equivalently the number of factors in its
Cartier-Foata decomposition. Let $h(t)$ and $|t|$ stand respectively for the
height and the length of a trace $t$. Roughly speaking, $|t|$ is the
`sequential' execution time and $h(t)$ is the `parallel' execution time. We
prove that the bivariate commutative series $\sum_t x^{h(t)}y^{|t|}$ is
rational, and we give a finite representation of it. We use the rationality to
obtain precise information on the asymptotics of the number of traces of a
given height or length. Then, we study the average height of a trace for
various probability distributions on traces. For the uniform probability
distribution on traces of the same length (resp. of the same height), the
asymptotic average height (resp. length) exists and is an algebraic number. To
illustrate our results and methods, we consider a couple of examples: the free
commutative monoid and the trace monoid whose independence graph is the ladder
graph.


title:
A Data Mining Framework for Optimal Product Selection in Retail
  Supermarket Data: The Generalized PROFSET Model

abstract:
  In recent years, data mining researchers have developed efficient association
rule algorithms for retail market basket analysis. Still, retailers often
complain about how to adopt association rules to optimize concrete retail
marketing-mix decisions. It is in this context that, in a previous paper, the
authors have introduced a product selection model called PROFSET. This model
selects the most interesting products from a product assortment based on their
cross-selling potential given some retailer defined constraints. However this
model suffered from an important deficiency: it could not deal effectively with
supermarket data, and no provisions were taken to include retail category
management principles. Therefore, in this paper, the authors present an
important generalization of the existing model in order to make it suitable for
supermarket data as well, and to enable retailers to add category restrictions
to the model. Experiments on real world data obtained from a Belgian
supermarket chain produce very promising results and demonstrate the
effectiveness of the generalized PROFSET model.


title: Guaranteeing the diversity of number generators

abstract:
  A major problem in using iterative number generators of the form
x_i=f(x_{i-1}) is that they can enter unexpectedly short cycles. This is hard
to analyze when the generator is designed, hard to detect in real time when the
generator is used, and can have devastating cryptanalytic implications. In this
paper we define a measure of security, called_sequence_diversity_, which
generalizes the notion of cycle-length for non-iterative generators. We then
introduce the class of counter assisted generators, and show how to turn any
iterative generator (even a bad one designed or seeded by an adversary) into a
counter assisted generator with a provably high diversity, without reducing the
quality of generators which are already cryptographically strong.


title: Rational Competitive Analysis

abstract:
  Much work in computer science has adopted competitive analysis as a tool for
decision making under uncertainty. In this work we extend competitive analysis
to the context of multi-agent systems. Unlike classical competitive analysis
where the behavior of an agent's environment is taken to be arbitrary, we
consider the case where an agent's environment consists of other agents. These
agents will usually obey some (minimal) rationality constraints. This leads to
the definition of rational competitive analysis. We introduce the concept of
rational competitive analysis, and initiate the study of competitive analysis
for multi-agent systems. We also discuss the application of rational
competitive analysis to the context of bidding games, as well as to the
classical one-way trading problem.


title: Pseudorandom permutations with the fast forward property

abstract:
  This paper has been withdrawn by the author(s), due to the existence of a
much better paper in http://arxiv.org/abs/cs.CR/0207027


title: Using Structural Metadata to Localize Experience of Digital Content

abstract:
  With the increasing technical sophistication of both information consumers
and providers, there is increasing demand for more meaningful experiences of
digital information. We present a framework that separates digital object
experience, or rendering, from digital object storage and manipulation, so the
rendering can be tailored to particular communities of users. Our framework
also accommodates extensible digital object behaviors and interoperability. The
two key components of our approach are 1) exposing structural metadata
associated with digital objects -- metadata about the labeled access points
within a digital object and 2) information intermediaries called context
brokers that match structural characteristics of digital objects with
mechanisms that produce behaviors. These context brokers allow for localized
rendering of digital information stored externally.


title:
Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix
  Multiplication

abstract:
  In 1975, Valiant showed that Boolean matrix multiplication can be used for
parsing context-free grammars (CFGs), yielding the asympotically fastest
(although not practical) CFG parsing algorithm known. We prove a dual result:
any CFG parser with time complexity $O(g n^{3 - \epsilson})$, where $g$ is the
size of the grammar and $n$ is the length of the input string, can be
efficiently converted into an algorithm to multiply $m \times m$ Boolean
matrices in time $O(m^{3 - \epsilon/3})$.
  Given that practical, substantially sub-cubic Boolean matrix multiplication
algorithms have been quite difficult to find, we thus explain why there has
been little progress in developing practical, substantially sub-cubic general
CFG parsers. In proving this result, we also develop a formalization of the
notion of parsing.


title: Distribution of Mutual Information

abstract:
  The mutual information of two random variables i and j with joint
probabilities t_ij is commonly used in learning Bayesian nets as well as in
many other fields. The chances t_ij are usually estimated by the empirical
sampling frequency n_ij/n leading to a point estimate I(n_ij/n) for the mutual
information. To answer questions like "is I(n_ij/n) consistent with zero?" or
"what is the probability that the true mutual information is much larger than
the point estimate?" one has to go beyond the point estimate. In the Bayesian
framework one can answer these questions by utilizing a (second order) prior
distribution p(t) comprising prior information about t. From the prior p(t) one
can compute the posterior p(t|n), from which the distribution p(I|n) of the
mutual information can be calculated. We derive reliable and quickly computable
approximations for p(I|n). We concentrate on the mean, variance, skewness, and
kurtosis, and non-informative priors. For the mean we also give an exact
expression. Numerical issues and the range of validity are discussed.


title: Concurrent computing machines and physical space-time

abstract:
  Concrete computing machines, either sequential or concurrent, rely on an
intimate relation between computation and time. We recall the general
characteristic properties of physical time and of present realizations of
computing systems. We emphasize the role of computing interferences, i.e. the
necessity to avoid them in order to give a causal implementation to logical
operations. We compare synchronous and asynchronous systems, and make a brief
survey of some methods used to deal with computing interferences. Using a
graphic representation, we show that synchronous and asynchronous circuits
reflect the same opposition as the Newtonian and relativistic causal structures
for physical space-time.