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.


title: Exact Complexity of the Winner Problem for Young Elections

abstract: In 1977, Young proposed a voting scheme that extends the Condorcet Principle based on the fewest possible number of voters whose removal yields a Condorcet winner. We prove that both the winner and the ranking problem for Young elections is complete for the class of problems solvable in polynomial time by parallel access to NP. Analogous results for Lewis Carroll's 1876 voting scheme were recently established by Hemaspaandra et al. In contrast, we prove that the winner and ranking problems in Fishburn's homogeneous variant of Carroll's voting scheme can be solved efficiently by linear programming.


title: Faster Algorithm of String Comparison

abstract: In many applications, it is necessary to determine the string similarity. Edit distance[WF74] approach is a classic method to determine Field Similarity. A well known dynamic programming algorithm [GUS97] is used to calculate edit distance with the time complexity O(nm). (for worst case, average case and even best case) Instead of continuing with improving the edit distance approach, [LL+99] adopted a brand new approach-token-based approach. Its new concept of token-base-retain the original semantic information, good time complex-O(nm) (for worst, average and best case) and good experimental performance make it a milestone paper in this area. Further study indicates that there is still room for improvement of its Field Similarity algorithm. Our paper is to introduce a package of substring-based new algorithms to determine Field Similarity. Combined together, our new algorithms not only achieve higher accuracy but also gain the time complexity O(knm) (k<0.75) for worst case, O(*n) where <6 for average case and O(1) for best case. Throughout the paper, we use the approach of comparative examples to show higher accuracy of our algorithms compared to the one proposed in [LL+99]. Theoretical analysis, concrete examples and experimental result show that our algorithms can significantly improve the accuracy and time complexity of the calculation of Field Similarity. [US97] D. Guseld. Algorithms on Strings, Trees and Sequences, in Computer Science and Computational Biology. [LL+99] Mong Li Lee, Cleansing data for mining and warehousing, In Proceedings of the 10th International Conference on Database and Expert Systems Applications (DEXA99), pages 751-760,August 1999. [WF74] R. Wagner and M. Fisher, The String to String Correction Problem, JACM 21 pages 168-173, 1974.


title: Lower Bound on the Chromatic Number by Spectra of Weighted Adjacency Matrices

abstract: A lower bound on the chromatic number of a graph is derived by majorization of spectra of weighted adjacency matrices. These matrices are given by Hadamard products of the adjacency matrix and arbitrary Hermitian matrices.


title: Media Objects in Time - A Multimedia Streaming System

abstract: The widespread availability of networked multimedia potentials embedded in an infrastructure of qualitative superior kind gives rise to new approaches in the areas of teleteaching and internet presentation: The distribution of professionally styled multimedia streams has fallen in the realm of possibility. This paper presents a prototype - both model and runtime environment - of a time directed media system treating any kind of presentational contribution as reusable media object components. The plug-in free runtime system is based on a database and allows for a flexible support of static media types as well as for easy extensions by streaming media servers. The prototypic implementation includes a preliminary Web Authoring platform.


title: Lower Bounds for Matrix Product

abstract: We prove lower bounds on the number of product gates in bilinear and quadratic circuits that compute the product of two $n \cross n$ matrices over finite fields. In particular we obtain the following results: 1. We show that the number of product gates in any bilinear (or quadratic) circuit that computes the product of two $n \cross n$ matrices over $F_2$ is at least $3 n^2 - o(n^2)$. 2. We show that the number of product gates in any bilinear circuit that computes the product of two $n \cross n$ matrices over $F_p$ is at least $(2.5 + \frac{1.5}{p^3 -1})n^2 -o(n^2)$. These results improve the former results of Bshouty '89 and Blaser '99 who proved lower bounds of $2.5 n^2 - o(n^2)$.


title: Incremental Construction of Compact Acyclic NFAs

abstract: This paper presents and analyzes an incremental algorithm for the construction of Acyclic Non-deterministic Finite-state Automata (NFA). Automata of this type are quite useful in computational linguistics, especially for storing lexicons. The proposed algorithm produces compact NFAs, i.e. NFAs that do not contain equivalent states. Unlike Deterministic Finite-state Automata (DFA), this property is not sufficient to ensure minimality, but still the resulting NFAs are considerably smaller than the minimal DFAs for the same languages.


title: Trust enhancement by multiple random beacons

abstract: Random beacons-information sources that broadcast a stream of random digits unknown by anyone beforehand-are useful for various cryptographic purposes. But such beacons can be easily and undetectably sabotaged, so that their output is known beforehand by a dishonest party, who can use this information to defeat the cryptographic protocols supposedly protected by the beacon. We explore a strategy to reduce this hazard by combining the outputs from several noninteracting (eg spacelike-separated) beacons by XORing them together to produce a single digit stream which is more trustworthy than any individual beacon, being random and unpredictable if at least one of the contributing beacons is honest. If the contributing beacons are not spacelike separated, so that a dishonest beacon can overhear and adapt to earlier outputs of other beacons, the beacons' trustworthiness can still be enhanced to a lesser extent by a time sharing strategy. We point out some disadvantages of alternative trust amplification methods based on one-way hash functions.


title: Analysis of Non-Gaussian Nature of Network Traffic

abstract: To study mechanisms that cause the non-Gaussian nature of network traffic, we analyzed IP flow statistics. For greedy flows in particular, we investigated the hop counts between source and destination nodes, and classified applications by the port number. We found that the main flows contributing to the non-Gaussian nature of network traffic were HTTP flows with relatively small hop counts compared with the average hop counts of all flows.


title: Sharpening Occam's Razor

abstract: We provide a new representation-independent formulation of Occam's razor theorem, based on Kolmogorov complexity. This new formulation allows us to: (i) Obtain better sample complexity than both length-based and VC-based versions of Occam's razor theorem, in many applications. (ii) Achieve a sharper reverse of Occam's razor theorem than previous work. Specifically, we weaken the assumptions made in an earlier publication, and extend the reverse to superpolynomial running times.

categories: cs.LG cond-mat.dis-nn cs.AI cs.CC math.PR physics.data-an


title: On the Importance of Having an Identity or, is Consensus really Universal?

abstract: We show that Naming-- the existence of distinct IDs known to all-- is a hidden but necessary assumption of Herlihy's universality result for Consensus. We then show in a very precise sense that Naming is harder than Consensus and bring to the surface some important differences existing between popular shared memory models.


title: Algorithm for generating orthogonal matrices with rational elements

abstract: Special orthogonal matrices with rational elements form the group SO(n,Q), where Q is the field of rational numbers. A theorem describing the structure of an arbitrary matrix from this group is proved. This theorem yields an algorithm for generating such matrices by means of random number routines.


title: Using Tree Automata and Regular Expressions to Manipulate Hierarchically Structured Data

abstract: Information, stored or transmitted in digital form, is often structured. Individual data records are usually represented as hierarchies of their elements. Together, records form larger structures. Information processing applications have to take account of this structuring, which assigns different semantics to different data elements or records. Big variety of structural schemata in use today often requires much flexibility from applications--for example, to process information coming from different sources. To ensure application interoperability, translators are needed that can convert one structure into another. This paper puts forward a formal data model aimed at supporting hierarchical data processing in a simple and flexible way. The model is based on and extends results of two classical theories, studying finite string and tree automata. The concept of finite automata and regular languages is applied to the case of arbitrarily structured tree-like hierarchical data records, represented as "structured strings." These automata are compared with classical string and tree automata; the model is shown to be a superset of the classical models. Regular grammars and expressions over structured strings are introduced. Regular expression matching and substitution has been widely used for efficient unstructured text processing; the model described here brings the power of this proven technique to applications that deal with information trees. A simple generic alternative is offered to replace today's specialised ad-hoc approaches. The model unifies structural and content transformations, providing applications with a single data type. An example scenario of how to build applications based on this theory is discussed. Further research directions are outlined.


title: The performance of the batch learner algorithm

abstract: We analyze completely the convergence speed of the \emph{batch learning algorithm}, and compare its speed to that of the memoryless learning algorithm and of learning with memory. We show that the batch learning algorithm is never worse than the memoryless learning algorithm (at least asymptotically). Its performance \emph{vis-a-vis} learning with full memory is less clearcut, and depends on certain probabilistic assumptions.


title: Bundling Equilibrium in Combinatorial auctions

abstract: This paper analyzes individually-rational ex post equilibrium in the VC (Vickrey-Clarke) combinatorial auctions. If $\Sigma$ is a family of bundles of goods, the organizer may restrict the participants by requiring them to submit their bids only for bundles in $\Sigma$. The $\Sigma$-VC combinatorial auctions (multi-good auctions) obtained in this way are known to be individually-rational truth-telling mechanisms. In contrast, this paper deals with non-restricted VC auctions, in which the buyers restrict themselves to bids on bundles in $\Sigma$, because it is rational for them to do so. That is, it may be that when the buyers report their valuation of the bundles in $\Sigma$, they are in an equilibrium. We fully characterize those $\Sigma$ that induce individually rational equilibrium in every VC auction, and we refer to the associated equilibrium as a bundling equilibrium. The number of bundles in $\Sigma$ represents the communication complexity of the equilibrium. A special case of bundling equilibrium is partition-based equilibrium, in which $\Sigma$ is a field, that is, it is generated by a partition. We analyze the tradeoff between communication complexity and economic efficiency of bundling equilibrium, focusing in particular on partition-based equilibrium.


title: A Backward Analysis for Constraint Logic Programs

abstract: One recurring problem in program development is that of understanding how to re-use code developed by a third party. In the context of (constraint) logic programming, part of this problem reduces to figuring out how to query a program. If the logic program does not come with any documentation, then the programmer is forced to either experiment with queries in an ad hoc fashion or trace the control-flow of the program (backward) to infer the modes in which a predicate must be called so as to avoid an instantiation error. This paper presents an abstract interpretation scheme that automates the latter technique. The analysis presented in this paper can infer moding properties which if satisfied by the initial query, come with the guarantee that the program and query can never generate any moding or instantiation errors. Other applications of the analysis are discussed. The paper explains how abstract domains with certain computational properties (they condense) can be used to trace control-flow backward (right-to-left) to infer useful properties of initial queries. A correctness argument is presented and an implementation is reported.


title: Efficient Groundness Analysis in Prolog

abstract: Boolean functions can be used to express the groundness of, and trace grounding dependencies between, program variables in (constraint) logic programs. In this paper, a variety of issues pertaining to the efficient Prolog implementation of groundness analysis are investigated, focusing on the domain of definite Boolean functions, Def. The systematic design of the representation of an abstract domain is discussed in relation to its impact on the algorithmic complexity of the domain operations; the most frequently called operations should be the most lightweight. This methodology is applied to Def, resulting in a new representation, together with new algorithms for its domain operations utilising previously unexploited properties of Def -- for instance, quadratic-time entailment checking. The iteration strategy driving the analysis is also discussed and a simple, but very effective, optimisation of induced magic is described. The analysis can be implemented straightforwardly in Prolog and the use of a non-ground representation results in an efficient, scalable tool which does not require widening to be invoked, even on the largest benchmarks. An extensive experimental evaluation is given


title: Computing Preferred Answer Sets by Meta-Interpretation in Answer Set Programming

abstract: Most recently, Answer Set Programming (ASP) is attracting interest as a new paradigm for problem solving. An important aspect which needs to be supported is the handling of preferences between rules, for which several approaches have been presented. In this paper, we consider the problem of implementing preference handling approaches by means of meta-interpreters in Answer Set Programming. In particular, we consider the preferred answer set approaches by Brewka and Eiter, by Delgrande, Schaub and Tompits, and by Wang, Zhou and Lin. We present suitable meta-interpreters for these semantics using DLV, which is an efficient engine for ASP. Moreover, we also present a meta-interpreter for the weakly preferred answer set approach by Brewka and Eiter, which uses the weak constraint feature of DLV as a tool for expressing and solving an underlying optimization problem. We also consider advanced meta-interpreters, which make use of graph-based characterizations and often allow for more efficient computations. Our approach shows the suitability of ASP in general and of DLV in particular for fast prototyping. This can be fruitfully exploited for experimenting with new languages and knowledge-representation formalisms.


title: The Dynamics of AdaBoost Weights Tells You What's Hard to Classify

abstract: The dynamical evolution of weights in the Adaboost algorithm contains useful information about the role that the associated data points play in the built of the Adaboost model. In particular, the dynamics induces a bipartition of the data set into two (easy/hard) classes. Easy points are ininfluential in the making of the model, while the varying relevance of hard points can be gauged in terms of an entropy value associated to their evolution. Smooth approximations of entropy highlight regions where classification is most uncertain. Promising results are obtained when methods proposed are applied in the Optimal Sampling framework.


title: On the Significance of Digits in Interval Notation

abstract: To analyse the significance of the digits used for interval bounds, we clarify the philosophical presuppositions of various interval notations. We use information theory to determine the information content of the last digit of the numeral used to denote the interval's bounds. This leads to the notion of efficiency of a decimal digit: the actual value as percentage of the maximal value of its information content. By taking this efficiency into account, many presentations of intervals can be made more readable at the expense of negligible loss of information.


title: A computer scientist looks at game theory

abstract: I consider issues in distributed computation that should be of relevance to game theory. In particular, I focus on (a) representing knowledge and uncertainty, (b) dealing with failures, and (c) specification of mechanisms.


title: Collusion in Unrepeated, First-Price Auctions with an Uncertain Number of Participants

abstract: We consider the question of whether collusion among bidders (a "bidding ring") can be supported in equilibrium of unrepeated first-price auctions. Unlike previous work on the topic such as that by McAfee and McMillan [1992] and Marshall and Marx [2007], we do not assume that non-colluding agents have perfect knowledge about the number of colluding agents whose bids are suppressed by the bidding ring, and indeed even allow for the existence of multiple cartels. Furthermore, while we treat the association of bidders with bidding rings as exogenous, we allow bidders to make strategic decisions about whether to join bidding rings when invited. We identify a bidding ring protocol that results in an efficient allocation in Bayes{Nash equilibrium, under which non-colluding agents bid straightforwardly, and colluding agents join bidding rings when invited and truthfully declare their valuations to the ring center. We show that bidding rings benefit ring centers and all agents, both members and non-members of bidding rings, at the auctioneer's expense. The techniques we introduce in this paper may also be useful for reasoning about other problems in which agents have asymmetric information about a setting.


title: Long Proteins with Unique Optimal Foldings in the H-P Model

abstract: It is widely accepted that (1) the natural or folded state of proteins is a global energy minimum, and (2) in most cases proteins fold to a unique state determined by their amino acid sequence. The H-P (hydrophobic-hydrophilic) model is a simple combinatorial model designed to answer qualitative questions about the protein folding process. In this paper we consider a problem suggested by Brian Hayes in 1998: what proteins in the two-dimensional H-P model have unique optimal (minimum energy) foldings? In particular, we prove that there are closed chains of monomers (amino acids) with this property for all (even) lengths; and that there are open monomer chains with this property for all lengths divisible by four.


title: Structure from Motion: Theoretical Foundations of a Novel Approach Using Custom Built Invariants

abstract: We rephrase the problem of 3D reconstruction from images in terms of intersections of projections of orbits of custom built Lie groups actions. We then use an algorithmic method based on moving frames "a la Fels-Olver" to obtain a fundamental set of invariants of these groups actions. The invariants are used to define a set of equations to be solved by the points of the 3D object, providing a new technique for recovering 3D structure from motion.


title: A Modal Logic Framework for Multi-agent Belief Fusion

abstract: This paper is aimed at providing a uniform framework for reasoning about beliefs of multiple agents and their fusion. In the first part of the paper, we develop logics for reasoning about cautiously merged beliefs of agents with different degrees of reliability. The logics are obtained by combining the multi-agent epistemic logic and multi-sources reasoning systems. Every ordering for the reliability of the agents is represented by a modal operator, so we can reason with the merged results under different situations. The fusion is cautious in the sense that if an agent's belief is in conflict with those of higher priorities, then his belief is completely discarded from the merged result. We consider two strategies for the cautious merging of beliefs. In the first one, if inconsistency occurs at some level, then all beliefs at the lower levels are discarded simultaneously, so it is called level cutting strategy. For the second one, only the level at which the inconsistency occurs is skipped, so it is called level skipping strategy. The formal semantics and axiomatic systems for these two strategies are presented. In the second part, we extend the logics both syntactically and semantically to cover some more sophisticated belief fusion and revision operators. While most existing approaches treat belief fusion operators as meta-level constructs, these operators are directly incorporated into our object logic language. Thus it is possible to reason not only with the merged results but also about the fusion process in our logics. The relationship of our extended logics with the conditional logics of belief revision is also discussed.


title: Learning to Play Games in Extensive Form by Valuation

abstract: A valuation for a player in a game in extensive form is an assignment of numeric values to the players moves. The valuation reflects the desirability moves. We assume a myopic player, who chooses a move with the highest valuation. Valuations can also be revised, and hopefully improved, after each play of the game. Here, a very simple valuation revision is considered, in which the moves made in a play are assigned the payoff obtained in the play. We show that by adopting such a learning process a player who has a winning strategy in a win-lose game can almost surely guarantee a win in a repeated game. When a player has more than two payoffs, a more elaborate learning procedure is required. We consider one that associates with each move the average payoff in the rounds in which this move was made. When all players adopt this learning procedure, with some perturbations, then, with probability 1, strategies that are close to subgame perfect equilibrium are played after some time. A single player who adopts this procedure can guarantee only her individually rational payoff.


title: A theory of experiment

abstract: This article aims at clarifying the language and practice of scientific experiment, mainly by hooking observability on calculability.


title: Model-Based Software Engineering and Ada: Synergy for the Development of Safety-Critical Systems

abstract: In this paper we outline a software development process for safety-critical systems that aims at combining some of the specific strengths of model-based development with those of programming language based development using safety-critical subsets of Ada. Model-based software development and model-based test case generation techniques are combined with code generation techniques and tools providing a transition from model to code both for a system itself and for its test cases. This allows developers to combine domain-oriented, model-based techniques with source code based validation techniques, as required for conformity with standards for the development of safety-critical software, such as the avionics standard RTCA/DO-178B. We introduce the AutoFocus and Validator modeling and validation toolset and sketch its usage for modeling, test case generation, and code generation in a combined approach, which is further illustrated by a simplified leading edge aerospace model with built-in fault tolerance.


title: Design of statistical quality control procedures using genetic algorithms

abstract: In general, we can not use algebraic or enumerative methods to optimize a quality control (QC) procedure so as to detect the critical random and systematic analytical errors with stated probabilities, while the probability for false rejection is minimum. Genetic algorithms (GAs) offer an alternative, as they do not require knowledge of the objective function to be optimized and search through large parameter spaces quickly. To explore the application of GAs in statistical QC, we have developed an interactive GAs based computer program that designs a novel near optimal QC procedure, given an analytical process. The program uses the deterministic crowding algorithm. An illustrative application of the program suggests that it has the potential to design QC procedures that are significantly better than 45 alternative ones that are used in the clinical laboratories.


title: Core Services in the Architecture of the National Digital Library for Science Education (NSDL)

abstract: We describe the core components of the architecture for the (NSDL) National Science, Mathematics, Engineering, and Technology Education Digital Library. Over time the NSDL will include heterogeneous users, content, and services. To accommodate this, a design for a technical and organization infrastructure has been formulated based on the notion of a spectrum of interoperability. This paper describes the first phase of the interoperability infrastructure including the metadata repository, search and discovery services, rights management services, and user interface portal facilities.


title: An Empirical Model for Volatility of Returns and Option Pricing

abstract: In a seminal paper in 1973, Black and Scholes argued how expected distributions of stock prices can be used to price options. Their model assumed a directed random motion for the returns and consequently a lognormal distribution of asset prices after a finite time. We point out two problems with their formulation. First, we show that the option valuation is not uniquely determined; in particular, stratergies based on the delta-hedge and CAMP (Capital Asset Pricing Model) are shown to provide different valuations of an option. Second, asset returns are known not to be Gaussian distributed. Empirically, distributions of returns are seen to be much better approximated by an exponential distribution. This exponential distribution of asset prices can be used to develop a new pricing model for options that is shown to provide valuations that agree very well with those used by traders. We show how the Fokker-Planck formulation of fluctuations (i.e., the dynamics of the distribution) can be modified to provide an exponential distribution for returns. We also show how a singular volatility can be used to go smoothly from exponential to Gaussian returns and thereby illustrate why exponential returns cannot be reached perturbatively starting from Gaussian ones, and explain how the theory of 'stochastic volatility' can be obtained from our model by making a bad approximation. Finally, we show how to calculate put and call prices for a stretched exponential density.


title: Components of an NSDL Architecture: Technical Scope and Functional Model

abstract: We describe work leading toward specification of a technical architecture for the National Science, Mathematics, Engineering, and Technology Education Digital Library (NSDL). This includes a technical scope and a functional model, with some elaboration on the particularly rich set of library services that NSDL is expected eventually to encompass.


title: Software Validation using Power Profiles

abstract: The validation of modern software systems incorporates both functional and quality requirements. This paper proposes a validation approach for software quality requirement - its power consumption. This approach validates whether the software produces the desired results with a minimum expenditure of energy. We present energy requirements and an approach for their validation using a power consumption model, test-case specification, software traces, and power measurements. Three different approaches for power data gathering are described. The power consumption of mobile phone applications is obtained and matched against the power consumption model.


title: The Witness Properties and the Semantics of the Prolog Cut

abstract: The semantics of the Prolog ``cut'' construct is explored in the context of some desirable properties of logic programming systems, referred to as the witness properties. The witness properties concern the operational consistency of responses to queries. A generalization of Prolog with negation as failure and cut is described, and shown not to have the witness properties. A restriction of the system is then described, which preserves the choice and first-solution behaviour of cut but allows the system to have the witness properties. The notion of cut in the restricted system is more restricted than the Prolog hard cut, but retains the useful first-solution behaviour of hard cut, not retained by other proposed cuts such as the ``soft cut''. It is argued that the restricted system achieves a good compromise between the power and utility of the Prolog cut and the need for internal consistency in logic programming systems. The restricted system is given an abstract semantics, which depends on the witness properties; this semantics suggests that the restricted system has a deeper connection to logic than simply permitting some computations which are logical. Parts of this paper appeared previously in a different form in the Proceedings of the 1995 International Logic Programming Symposium.


title: The Deductive Database System LDL++

abstract: This paper describes the LDL++ system and the research advances that have enabled its design and development. We begin by discussing the new nonmonotonic and nondeterministic constructs that extend the functionality of the LDL++ language, while preserving its model-theoretic and fixpoint semantics. Then, we describe the execution model and the open architecture designed to support these new constructs and to facilitate the integration with existing DBMSs and applications. Finally, we describe the lessons learned by using LDL++ on various tested applications, such as middleware and datamining.


title: A Refinement Calculus for Logic Programs

abstract: Existing refinement calculi provide frameworks for the stepwise development of imperative programs from specifications. This paper presents a refinement calculus for deriving logic programs. The calculus contains a wide-spectrum logic programming language, including executable constructs such as sequential conjunction, disjunction, and existential quantification, as well as specification constructs such as general predicates, assumptions and universal quantification. A declarative semantics is defined for this wide-spectrum language based on executions. Executions are partial functions from states to states, where a state is represented as a set of bindings. The semantics is used to define the meaning of programs and specifications, including parameters and recursion. To complete the calculus, a notion of correctness-preserving refinement over programs in the wide-spectrum language is defined and refinement laws for developing programs are introduced. The refinement calculus is illustrated using example derivations and prototype tool support is discussed.


title: Simple Optimal Wait-free Multireader Registers

abstract: Multireader shared registers are basic objects used as communication medium in asynchronous concurrent computation. We propose a surprisingly simple and natural scheme to obtain several wait-free constructions of bounded 1-writer multireader registers from atomic 1-writer 1-reader registers, that is easier to prove correct than any previous construction. Our main construction is the first symmetric pure timestamp one that is optimal with respect to the worst-case local use of control bits; the other one is optimal with respect to global use of control bits; both are optimal in time.


title: A Qualitative Dynamical Modelling Approach to Capital Accumulation in Unregulated Fisheries

abstract: Capital accumulation has been a major issue in fisheries economics over the last two decades, whereby the interaction of the fish and capital stocks were of particular interest. Because bio-economic systems are intrinsically complex, previous efforts in this field have relied on a variety of simplifying assumptions. The model presented here relaxes some of these simplifications. Problems of tractability are surmounted by using the methodology of qualitative differential equations (QDE). The theory of QDEs takes into account that scientific knowledge about particular fisheries is usually limited, and facilitates an analysis of the global dynamics of systems with more than two ordinary differential equations. The model is able to trace the evolution of capital and fish stock in good agreement with observed patterns, and shows that over-capitalization is unavoidable in unregulated fisheries.