title: A family of metrics on contact structures based on edge ideals

abstract: The measurement of the similarity of RNA secondary structures, and in general of contact structures, of a fixed length has several specific applications. For instance, it is used in the analysis of the ensemble of suboptimal secondary structures generated by a given algorithm on a given RNA sequence, and in the comparison of the secondary structures predicted by different algorithms on a given RNA molecule. It is also a useful tool in the quantitative study of sequence-structure maps. A way to measure this similarity is by means of metrics. In this paper we introduce a new class of metrics $d_{m}$, $m\geq 3$, on the set of all contact structures of a fixed length, based on their representation by means of edge ideals in a polynomial ring. These metrics can be expressed in terms of Hilbert functions of monomial ideals, which allows the use of several public domain computer algebra systems to compute them. We study some abstract properties of these metrics, and we obtain explicit descriptions of them for $m=3,4$ on arbitrary contact structures and for $m=5,6$ on RNA secondary structures.


title: Making refactoring decisions in large-scale Java systems: an empirical stance

abstract: Decisions on which classes to refactor are fraught with difficulty. The problem of identifying candidate classes becomes acute when confronted with large systems comprising hundreds or thousands of classes. In this paper, we describe a metric by which key classes, and hence candidates for refactoring, can be identified. Measures quantifying the usage of two forms of coupling, inheritance and aggregation, together with two other class features (number of methods and attributes) were extracted from the source code of three large Java systems. Our research shows that metrics from other research domains can be adapted to the software engineering process. Substantial differences were found between each of the systems in terms of the key classes identified and hence opportunities for refactoring those classes varied between those systems.


title: An Improved k-Nearest Neighbor Algorithm for Text Categorization

abstract: k is the most important parameter in a text categorization system based on k-Nearest Neighbor algorithm (kNN).In the classification process, k nearest documents to the test one in the training set are determined firstly. Then, the predication can be made according to the category distribution among these k nearest neighbors. Generally speaking, the class distribution in the training set is uneven. Some classes may have more samples than others. Therefore, the system performance is very sensitive to the choice of the parameter k. And it is very likely that a fixed k value will result in a bias on large categories. To deal with these problems, we propose an improved kNN algorithm, which uses different numbers of nearest neighbors for different categories, rather than a fixed number across all categories. More samples (nearest neighbors) will be used for deciding whether a test document should be classified to a category, which has more samples in the training set. Preliminary experiments on Chinese text categorization show that our method is less sensitive to the parameter k than the traditional one, and it can properly classify documents belonging to smaller classes with a large k. The method is promising for some cases, where estimating the parameter k via cross-validation is not allowed.


title: Site Authorization Service (SAZ)

abstract: In this paper we present a methodology to provide an additional level of centralized control for the grid resources. This centralized control is applied to site-wide distribution of various grids and thus providing an upper hand in the maintenance.


title: The DataFlow System of the ATLAS Trigger and DAQ

abstract: The baseline design and implementation of the DataFlow system, to be documented in the ATLAS DAQ/HLT Technical Design Report in summer 2003, will be presented. Empahsis will be placed on the system performance and scalability based on the results from prototyping studies which have maximised the use of commercially available hardware.


title: Prototyping Virtual Data Technologies in ATLAS Data Challenge 1 Production

abstract: For efficiency of the large production tasks distributed worldwide, it is essential to provide shared production management tools comprised of integratable and interoperable services. To enhance the ATLAS DC1 production toolkit, we introduced and tested a Virtual Data services component. For each major data transformation step identified in the ATLAS data processing pipeline (event generation, detector simulation, background pile-up and digitization, etc) the Virtual Data Cookbook (VDC) catalogue encapsulates the specific data transformation knowledge and the validated parameters settings that must be provided before the data transformation invocation. To provide for local-remote transparency during DC1 production, the VDC database server delivered in a controlled way both the validated production parameters and the templated production recipes for thousands of the event generation and detector simulation jobs around the world, simplifying the production management solutions.


title: Primary Numbers Database for ATLAS Detector Description Parameters

abstract: We present the design and the status of the database for detector description parameters in ATLAS experiment. The ATLAS Primary Numbers are the parameters defining the detector geometry and digitization in simulations, as well as certain reconstruction parameters. Since the detailed ATLAS detector description needs more than 10,000 such parameters, a preferred solution is to have a single verified source for all these data. The database stores the data dictionary for each parameter collection object, providing schema evolution support for object-based retrieval of parameters. The same Primary Numbers are served to many different clients accessing the database: the ATLAS software framework Athena, the Geant3 heritage framework Atlsim, the Geant4 developers framework FADS/Goofy, the generator of XML output for detector description, and several end-user clients for interactive data navigation, including web-based browsers and ROOT. The choice of the MySQL database product for the implementation provides additional benefits: the Primary Numbers database can be used on the developers laptop when disconnected (using the MySQL embedded server technology), with data being updated when the laptop is connected (using the MySQL database replication).


title: Efficient pebbling for list traversal synopses

abstract: We show how to support efficient back traversal in a unidirectional list, using small memory and with essentially no slowdown in forward steps. Using $O(\log n)$ memory for a list of size $n$, the $i$'th back-step from the farthest point reached so far takes $O(\log i)$ time in the worst case, while the overhead per forward step is at most $\epsilon$ for arbitrary small constant $\epsilon>0$. An arbitrary sequence of forward and back steps is allowed. A full trade-off between memory usage and time per back-step is presented: $k$ vs. $kn^{1/k}$ and vice versa. Our algorithms are based on a novel pebbling technique which moves pebbles on a virtual binary, or $t$-ary, tree that can only be traversed in a pre-order fashion. The compact data structures used by the pebbling algorithms, called list traversal synopses, extend to general directed graphs, and have other interesting applications, including memory efficient hash-chain implementation. Perhaps the most surprising application is in showing that for any program, arbitrary rollback steps can be efficiently supported with small overhead in memory, and marginal overhead in its ordinary execution. More concretely: Let $P$ be a program that runs for at most $T$ steps, using memory of size $M$. Then, at the cost of recording the input used by the program, and increasing the memory by a factor of $O(\log T)$ to $O(M \log T)$, the program $P$ can be extended to support an arbitrary sequence of forward execution and rollback steps: the $i$'th rollback step takes $O(\log i)$ time in the worst case, while forward steps take O(1) time in the worst case, and $1+\epsilon$ amortized time per step.


title: Design, implementation and deployment of the Saclay muon reconstruction algorithms (Muonbox/y) in the Athena software framework of the ATLAS experiment

abstract: This paper gives an overview of a reconstruction algorithm for muon events in ATLAS experiment at CERN. After a short introduction on ATLAS Muon Spectrometer, we will describe the procedure performed by the algorithms Muonbox and Muonboy (last version) in order to achieve correctly the reconstruction task. These algorithms have been developed in Fortran language and are working in the official C++ framework Athena, as well as in stand alone mode. A description of the interaction between Muonboy and Athena will be given, together with the reconstruction performances (efficiency and momentum resolution) obtained with MonteCarlo data.


title: Lexicographic probability, conditional probability, and nonstandard probability

abstract: The relationship between Popper spaces (conditional probability spaces that satisfy some regularity conditions), lexicographic probability systems (LPS's), and nonstandard probability spaces (NPS's) is considered. If countable additivity is assumed, Popper spaces and a subclass of LPS's are equivalent; without the assumption of countable additivity, the equivalence no longer holds. If the state space is finite, LPS's are equivalent to NPS's. However, if the state space is infinite, NPS's are shown to be more general than LPS's.


title: On the Relationship between Strand Spaces and Multi-Agent Systems

abstract: Strand spaces are a popular framework for the analysis of security protocols. Strand spaces have some similarities to a formalism used successfully to model protocols for distributed systems, namely multi-agent systems. We explore the exact relationship between these two frameworks here. It turns out that a key difference is the handling of agents, which are unspecified in strand spaces and explicit in multi-agent systems. We provide a family of translations from strand spaces to multi-agent systems parameterized by the choice of agents in the strand space. We also show that not every multi-agent system of interest can be expressed as a strand space. This reveals a lack of expressiveness in the strand-space framework that can be characterized by our translation. To highlight this lack of expressiveness, we show one simple way in which strand spaces can be extended to model more systems.


title: Web Engineering

abstract: Web Engineering is the application of systematic, disciplined and quantifiable approaches to development, operation, and maintenance of Web-based applications. It is both a pro-active approach and a growing collection of theoretical and empirical research in Web application development. This paper gives an overview of Web Engineering by addressing the questions: a) why is it needed? b) what is its domain of operation? c) how does it help and what should it do to improve Web application development? and d) how should it be incorporated in education and training? The paper discusses the significant differences that exist between Web applications and conventional software, the taxonomy of Web applications, the progress made so far and the research issues and experience of creating a specialisation at the master's level. The paper reaches a conclusion that Web Engineering at this stage is a moving target since Web technologies are constantly evolving, making new types of applications possible, which in turn may require innovations in how they are built, deployed and maintained.


title: Distributed Heterogeneous Relational Data Warehouse In A Grid Environment

abstract: This paper examines how a "Distributed Heterogeneous Relational Data Warehouse" can be integrated in a Grid environment that will provide physicists with efficient access to large and small object collections drawn from databases at multiple sites. This paper investigates the requirements of Grid-enabling such a warehouse, and explores how these requirements may be met by extensions to existing Grid middleware. We present initial results obtained with a working prototype warehouse of this kind using both SQLServer and Oracle9i, where a Grid-enabled web-services interface makes it easier for web-applications to access the distributed contents of the databases securely. Based on the success of the prototype, we proposes a framework for using heterogeneous relational data warehouse through the web-service interface and create a single "Virtual Database System" for users. The ability to transparently access data in this way, as shown in prototype, is likely to be a very powerful facility for HENP and other grid users wishing to collate and analyze information distributed over Grid.


title: Run Control and Monitor System for the CMS Experiment

abstract: The Run Control and Monitor System (RCMS) of the CMS experiment is the set of hardware and software components responsible for controlling and monitoring the experiment during data-taking. It provides users with a "virtual counting room", enabling them to operate the experiment and to monitor detector status and data quality from any point in the world. This paper describes the architecture of the RCMS with particular emphasis on its scalability through a distributed collection of nodes arranged in a tree-based hierarchy. The current implementation of the architecture in a prototype RCMS used in test beam setups, detector validations and DAQ demonstrators is documented. A discussion of the key technologies used, including Web Services, and the results of tests performed with a 128-node system are presented.


title: Sharing a conceptual model of grid resources and services

abstract: Grid technologies aim at enabling a coordinated resource-sharing and problem-solving capabilities over local and wide area networks and span locations, organizations, machine architectures and software boundaries. The heterogeneity of involved resources and the need for interoperability among different grid middlewares require the sharing of a common information model. Abstractions of different flavors of resources and services and conceptual schemas of domain specific entities require a collaboration effort in order to enable a coherent information services cooperation. With this paper, we present the result of our experience in grid resources and services modelling carried out within the Grid Laboratory Uniform Environment (GLUE) effort, a joint US and EU High Energy Physics projects collaboration towards grid interoperability. The first implementation-neutral agreement on services such as batch computing and storage manager, resources such as the hierarchy cluster, sub-cluster, host and the storage library are presented. Design guidelines and operational results are depicted together with open issues and future evolutions.


title: Adapting SAM for CDF

abstract: The CDF and D0 experiments probe the high-energy frontier and as they do so have accumulated hundreds of Terabytes of data on the way to petabytes of data over the next two years. The experiments have made a commitment to use the developing Grid based on the SAM system to handle these data. The D0 SAM has been extended for use in CDF as common patterns of design emerged to meet the similar requirements of these experiments. The process by which the merger was achieved is explained with particular emphasis on lessons learned concerning the database design patterns plus realization of the use cases.


title: Symbolic Parametric Analysis of Embedded Systems with BDD-like Data-Structures

abstract: We use dense variable-ordering to define HRD (Hybrid-Restriction Diagram), a new BDD-like data-structure for the representation and manipulation of state-spaces of linear hybrid automata. We present and discuss various manipulation algorithms for HRD, including the basic set-oriented operations, weakest precondition calculation, and normalization. We implemented the ideas and experimented to see their performance. Finally, we have also developed a pruning technique for state-space exploration based on parameter valuation space characterization. The technique showed good promise in our experiment.


title: D0 Data Handling Operational Experience

abstract: We report on the production experience of the D0 experiment at the Fermilab Tevatron, using the SAM data handling system with a variety of computing hardware configurations, batch systems, and mass storage strategies. We have stored more than 300 TB of data in the Fermilab Enstore mass storage system. We deliver data through this system at an average rate of more than 2 TB/day to analysis programs, with a substantial multiplication factor in the consumed data through intelligent cache management. We handle more than 1.7 Million files in this system and provide data delivery to user jobs at Fermilab on four types of systems: a reconstruction farm, a large SMP system, a Linux batch cluster, and a Linux desktop cluster. In addition, we import simulation data generated at 6 sites worldwide, and deliver data to jobs at many more sites. We describe the scope of the data handling deployment worldwide, the operational experience with this system, and the feedback of that experience.


title: D0 Regional Analysis Center Concepts

abstract: The D0 experiment is facing many exciting challenges providing a computing environment for its worldwide collaboration. Transparent access to data for processing and analysis has been enabled through deployment of its SAM system to collaborating sites and additional functionality will be provided soon with SAMGrid components. In order to maximize access to global storage, computational and intellectual resources, and to enable the system to scale to the large demands soon to be realized, several strategic sites have been identified as Regional Analysis Centers (RAC's). These sites play an expanded role within the system. The philosophy and function of these centers is discussed and details of their composition and operation are outlined. The plan for future additional centers is also addressed.


title: Global Platform for Rich Media Conferencing and Collaboration

abstract: The Virtual Rooms Videoconferencing Service (VRVS) provides a worldwide videoconferencing service and collaborative environment to the research and education communities. This system provides a low cost, bandwidth-efficient, extensible means for videoconferencing and remote collaboration over networks within the High Energy and Nuclear Physics communities (HENP). VRVS has become a standard part of the toolset used daily by a large sector of HENP, and it is used increasingly for other DoE/NSF-supported programs. The current features included multi-protocol, multi-OS support for all significant video enabled clients including: H.323, Mbone, QuickTime, MPEG2, Java Media Framework, and other clients. The current architecture makes VRVS a distributed, highly functional, and efficient software-only system for multipoint audio, video and web conferencing and collaboration over global IP networks. VRVS has developed the VRVS-AG Reflector and a specialized Web interface that enables end users to connect to any Access Grid (AG) session, in any of the AG "virtual venues" from anywhere worldwide. The VRVS system has now been running for the last five and half years, offering to the HENP community a working and reliable tool for collaboration within groups and among physicists dispersed world-wide. The goal of this ongoing effort is to develop the next generation collaborative systems running over next generation networks. The new developments area integrate emerging standards, include all security aspects, and will extend the range of VRVS video technologies supported to cover the latest high end standards quality. We will focus the discussion on the new capability provides by the latest version V3.0 and its future evolution.


title: Deciding regular grammar logics with converse through first-order logic

abstract: We provide a simple translation of the satisfiability problem for regular grammar logics with converse into GF2, which is the intersection of the guarded fragment and the 2-variable fragment of first-order logic. This translation is theoretically interesting because it translates modal logics with certain frame conditions into first-order logic, without explicitly expressing the frame conditions. A consequence of the translation is that the general satisfiability problem for regular grammar logics with converse is in EXPTIME. This extends a previous result of the first author for grammar logics without converse. Using the same method, we show how some other modal logics can be naturally translated into GF2, including nominal tense logics and intuitionistic logic. In our view, the results in this paper show that the natural first-order fragment corresponding to regular grammar logics is simply GF2 without extra machinery such as fixed point-operators.


title: On coalgebra based on classes

abstract: Every endofunctor of the category of classes is proved to be set-based in the sense of Aczel and Mendler, therefore, it has a final coalgebra. Other basic properties of these endofunctors are proved, e.g. the existence of a free completely iterative theory.


title: A Method for Solving Distributed Service Allocation Problems

abstract: We present a method for solving service allocation problems in which a set of services must be allocated to a set of agents so as to maximize a global utility. The method is completely distributed so it can scale to any number of services without degradation. We first formalize the service allocation problem and then present a simple hill-climbing, a global hill-climbing, and a bidding-protocol algorithm for solving it. We analyze the expected performance of these algorithms as a function of various problem parameters such as the branching factor and the number of agents. Finally, we use the sensor allocation problem, an instance of a service allocation problem, to show the bidding protocol at work. The simulations also show that phase transition on the expected quality of the solution exists as the amount of communication between agents increases.


title: Reinforcement Learning with Linear Function Approximation and LQ control Converges

abstract: Reinforcement learning is commonly used with function approximation. However, very few positive results are known about the convergence of function approximation based RL control algorithms. In this paper we show that TD(0) and Sarsa(0) with linear function approximation is convergent for a simple class of problems, where the system is linear and the costs are quadratic (the LQ control problem). Furthermore, we show that for systems with Gaussian noise and non-completely observable states (the LQG problem), the mentioned RL algorithms are still convergent, if they are combined with Kalman filtering.


title: Reachability problems for communicating finite state machines

abstract: The paper deals with the verification of reachability properties in a commonly used state transition model of communication protocols, which consists of finite state machines connected by potentially unbounded FIFO channels. Although simple reachability problems are undecidable for general protocols with unbounded channels, they are decidable for the protocols with the recognizable channel property. The decidability question is open for the protocols with the rational channel property.


title: The Best Trail Algorithm for Assisted Navigation of Web Sites

abstract: We present an algorithm called the Best Trail Algorithm, which helps solve the hypertext navigation problem by automating the construction of memex-like trails through the corpus. The algorithm performs a probabilistic best-first expansion of a set of navigation trees to find relevant and compact trails. We describe the implementation of the algorithm, scoring methods for trails, filtering algorithms and a new metric called \emph{potential gain} which measures the potential of a page for future navigation opportunities.


title: Heuristic to reduce the complexity of complete bipartite graphs to accelerate the search for maximum weighted matchings with small error

abstract: A maximum weighted matching for bipartite graphs $G=(A \cup B,E)$ can be found by using the algorithm of Edmonds and Karp with a Fibonacci Heap and a modified Dijkstra in $O(nm + n^2 \log{n})$ time where n is the number of nodes and m the number of edges. For the case that $|A|=|B|$ the number of edges is $n^2$ and therefore the complexity is $O(n^3)$. In this paper we want to present a simple heuristic method to reduce the number of edges of complete bipartite graphs $G=(A \cup B,E)$ with $|A|=|B|$ such that $m = n\log{n}$ and therefore the complexity of such that $m = n\log{n}$ and therefore the complexity of $O(n^2 \log{n})$. The weights of all edges in G must be uniformly distributed in [0,1].


title: Updating Probabilities

abstract: As examples such as the Monty Hall puzzle show, applying conditioning to update a probability distribution on a ``naive space'', which does not take into account the protocol used, can often lead to counterintuitive results. Here we examine why. A criterion known as CAR (``coarsening at random'') in the statistical literature characterizes when ``naive'' conditioning in a naive space works. We show that the CAR condition holds rather infrequently, and we provide a procedural characterization of it, by giving a randomized algorithm that generates all and only distributions for which CAR holds. This substantially extends previous characterizations of CAR. We also consider more generalized notions of update such as Jeffrey conditioning and minimizing relative entropy (MRE). We give a generalization of the CAR condition that characterizes when Jeffrey conditioning leads to appropriate answers, and show that there exist some very simple settings in which MRE essentially never gives the right results. This generalizes and interconnects previous results obtained in the literature on CAR and MRE.


title: Predicting Response-Function Results of Electrical/Mechanical Systems Through Artificial Neural Network

abstract: In the present paper a newer application of Artificial Neural Network (ANN) has been developed i.e., predicting response-function results of electrical-mechanical system through ANN. This method is specially useful to complex systems for which it is not possible to find the response-function because of complexity of the system. The proposed approach suggests that how even without knowing the response-function, the response-function results can be predicted with the use of ANN to the system. The steps used are: (i) Depending on the system, the ANN-architecture and the input & output parameters are decided, (ii) Training & test data are generated from simplified circuits and through tactic-superposition of it for complex circuits, (iii) Training the ANN with training data through many cycles and (iv) Test-data are used for predicting the response-function results. It is found that the proposed novel method for response prediction works satisfactorily. Thus this method could be used specially for complex systems where other methods are unable to tackle it. In this paper the application of ANN is particularly demonstrated to electrical-circuit system but can be applied to other systems too.


title: Bayesian Treatment of Incomplete Discrete Data applied to Mutual Information and Feature Selection

abstract: Given the joint chances of a pair of random variables one can compute quantities of interest, like the mutual information. The Bayesian treatment of unknown chances involves computing, from a second order prior distribution and the data likelihood, a posterior distribution of the chances. A common treatment of incomplete data is to assume ignorability and determine the chances by the expectation maximization (EM) algorithm. The two different methods above are well established but typically separated. This paper joins the two approaches in the case of Dirichlet priors, and derives efficient approximations for the mean, mode and the (co)variance of the chances and the mutual information. Furthermore, we prove the unimodality of the posterior distribution, whence the important property of convergence of EM to the global maximum in the chosen framework. These results are applied to the problem of selecting features for incremental learning and naive Bayes classification. A fast filter based on the distribution of mutual information is shown to outperform the traditional filter based on empirical mutual information on a number of incomplete real data sets.


title: Development of a Java Package for Matrix Programming

abstract: We had assembled a Java package, known as MatrixPak, of four classes for the purpose of numerical matrix computation. The classes are matrix, matrix_operations, StrToMatrix, and MatrixToStr; all of which are inherited from java.lang.Object class. Class matrix defines a matrix as a two-dimensional array of float types, and contains the following mathematical methods: transpose, adjoint, determinant, inverse, minor and cofactor. Class matrix_operations contains the following mathematical methods: matrix addition, matrix subtraction, matrix multiplication, and matrix exponential. Class StrToMatrix contains methods necessary to parse a string representation (for example, [[2 3 4]-[5 6 7]]) of a matrix into a matrix definition, whereas class MatrixToStr does the reverse.


title: On the suitability of the 2 x 2 games for studying reciprocal cooperation and kin selection

abstract: The 2 x 2 games, in particular the Prisoner's Dilemma, have been extensively used in studies into reciprocal cooperation and, to a lesser extent, kin selection. This paper examines the suitability of the 2 x 2 games for modelling the evolution of cooperation through reciprocation and kin selection. This examination is not restricted to the Prisoner's Dilemma, but includes the other non-trivial symmetric 2 x 2 games. We show that the popularity of the Prisoner's Dilemma for modelling social and biotic interaction is justified by its superiority according to these criteria. Indeed, the Prisoner's Dilemma is unique in providing the simplest support for reciprocal cooperation, and additive kin-selected altruism. However, care is still required in choosing the particular Prisoner's Dilemma payoff matrix to use. This paper reviews the impact of non-linear payoffs for the application of Hamilton's rule to typical altruistic interactions, and derives new results for cases in which the roles of potential altruist and beneficiary are separated. In doing so we find the same equilibrium condition holds in continuous games between relatives, and in discrete games with roles.


title: Security for Grid Services

abstract: Grid computing is concerned with the sharing and coordinated use of diverse resources in distributed "virtual organizations." The dynamic and multi-institutional nature of these environments introduces challenging security issues that demand new technical approaches. In particular, one must deal with diverse local mechanisms, support dynamic creation of services, and enable dynamic creation of trust domains. We describe how these issues are addressed in two generations of the Globus Toolkit. First, we review the Globus Toolkit version 2 (GT2) approach; then, we describe new approaches developed to support the Globus Toolkit version 3 (GT3) implementation of the Open Grid Services Architecture, an initiative that is recasting Grid concepts within a service oriented framework based on Web services. GT3's security implementation uses Web services security mechanisms for credential exchange and other purposes, and introduces a tight least-privilege model that avoids the need for any privileged network service.


title: Anusaaraka: Machine Translation in Stages

abstract: Fully-automatic general-purpose high-quality machine translation systems (FGH-MT) are extremely difficult to build. In fact, there is no system in the world for any pair of languages which qualifies to be called FGH-MT. The reasons are not far to seek. Translation is a creative process which involves interpretation of the given text by the translator. Translation would also vary depending on the audience and the purpose for which it is meant. This would explain the difficulty of building a machine translation system. Since, the machine is not capable of interpreting a general text with sufficient accuracy automatically at present - let alone re-expressing it for a given audience, it fails to perform as FGH-MT. FOOTNOTE{The major difficulty that the machine faces in interpreting a given text is the lack of general world knowledge or common sense knowledge.}


title: Complexity of Cycle Length Modularity Problems in Graphs

abstract: The even cycle problem for both undirected and directed graphs has been the topic of intense research in the last decade. In this paper, we study the computational complexity of \emph{cycle length modularity problems}. Roughly speaking, in a cycle length modularity problem, given an input (undirected or directed) graph, one has to determine whether the graph has a cycle $C$ of a specific length (or one of several different lengths), modulo a fixed integer. We denote the two families (one for undirected graphs and one for directed graphs) of problems by $(S,m)\hbox{-}{\rm UC}$ and $(S,m)\hbox{-}{\rm DC}$, where $m \in \mathcal{N}$ and $S \subseteq \{0,1, ..., m-1\}$. $(S,m)\hbox{-}{\rm UC}$ (respectively, $(S,m)\hbox{-}{\rm DC}$) is defined as follows: Given an undirected (respectively, directed) graph $G$, is there a cycle in $G$ whose length, modulo $m$, is a member of $S$? In this paper, we fully classify (i.e., as either polynomial-time solvable or as ${\rm NP}$-complete) each problem $(S,m)\hbox{-}{\rm UC}$ such that $0 \in S$ and each problem $(S,m)\hbox{-}{\rm DC}$ such that $0 \notin S$. We also give a sufficient condition on $S$ and $m$ for the following problem to be polynomial-time computable: $(S,m)\hbox{-}{\rm UC}$ such that $0 \notin S$.


title: Classical and Nonextensive Information Theory

abstract: In this work we firstly review some results in Classical Information Theory. Next, we try to generalize these results by using the Tsallis entropy. We present a preliminary result and discuss our aims in this field.


title: GRAPPA: Grid Access Portal for Physics Applications

abstract: Grappa is a Grid portal effort designed to provide physicists convenient access to Grid tools and services. The ATLAS analysis and control framework, Athena, was used as the target application. Grappa provides basic Grid functionality such as resource configuration, credential testing, job submission, job monitoring, results monitoring, and preliminary integration with the ATLAS replica catalog system, MAGDA. Grappa uses Jython to combine the ease of scripting with the power of java-based toolkits. This provides a powerful framework for accessing diverse Grid resources with uniform interfaces. The initial prototype system was based on the XCAT Science Portal developed at the Indiana University Extreme Computing Lab and was demonstrated by running Monte Carlo production on the U.S. ATLAS test-bed. The portal also communicated with a European resource broker on WorldGrid as part of the joint iVDGL-DataTAG interoperability project for the IST2002 and SC2002 demonstrations. The current prototype replaces the XCAT Science Portal with an xbooks jetspeed portlet for managing user scripts.


title: The Complexity of Boolean Constraint Isomorphism

abstract: In 1978, Schaefer proved his famous dichotomy theorem for generalized satisfiability problems. He defined an infinite number of propositional satisfiability problems (nowadays usually called Boolean constraint satisfaction problems) and showed that all these satisfiability problems are either in P or NP-complete. In recent years, similar results have been obtained for quite a few other problems for Boolean constraints.Almost all of these problems are variations of the satisfiability problem. In this paper, we address a problem that is not a variation of satisfiability, namely, the isomorphism problem for Boolean constraints. Previous work by B\"ohler et al. showed that the isomorphism problem is either coNP-hard or reducible to the graph isomorphism problem (a problem that is in NP, but not known to be NP-hard), thus distinguishing a hard case and an easier case. However, they did not classify which cases are truly easy, i.e., in P. This paper accomplishes exactly that. It shows that Boolean constraint isomorphism is coNP-hard (and GI-hard), or equivalent to graph isomorphism, or in P, and it gives simple criteria to determine which case holds.


title: Pruning Isomorphic Structural Sub-problems in Configuration

abstract: Configuring consists in simulating the realization of a complex product from a catalog of component parts, using known relations between types, and picking values for object attributes. This highly combinatorial problem in the field of constraint programming has been addressed with a variety of approaches since the foundation system R1(McDermott82). An inherent difficulty in solving configuration problems is the existence of many isomorphisms among interpretations. We describe a formalism independent approach to improve the detection of isomorphisms by configurators, which does not require to adapt the problem model. To achieve this, we exploit the properties of a characteristic subset of configuration problems, called the structural sub-problem, which canonical solutions can be produced or tested at a limited cost. In this paper we present an algorithm for testing the canonicity of configurations, that can be added as a symmetry breaking constraint to any configurator. The cost and efficiency of this canonicity test are given.


title: Distributive Computability

abstract: This thesis presents a series of theoretical results and practical realisations about the theory of computation in distributive categories. Distributive categories have been proposed as a foundational tool for Computer Science in the last years, starting from the papers of R.F.C. Walters. We shall focus on two major topics: distributive computability, i.e., a generalized theory of computability based on distributive categories, and the Imp(G) language, which is a language based on the syntax of distributive categories. The link between the former and the latter is that the functions computed by Imp(G) programs are exactly the distributively computable functions.


title: Serving Database Information Using a Flexible Server in a Three Tier Architecture

abstract: The D0 experiment at Fermilab relies on a central Oracle database for storing all detector calibration information. Access to this data is needed by hundreds of physics applications distributed worldwide. In order to meet the demands of these applications from scarce resources, we have created a distributed system that isolates the user applications from the database facilities. This system, known as the Database Application Network (DAN) operates as the middle tier in a three tier architecture. A DAN server employs a hierarchical caching scheme and database connection management facility that limits access to the database resource. The modular design allows for caching strategies and database access components to be determined by runtime configuration. To solve scalability problems, a proxy database component allows for DAN servers to be arranged in a hierarchy. Also included is an event based monitoring system that is currently being used to collect statistics for performance analysis and problem diagnosis. DAN servers are currently implemented as a Python multithreaded program using CORBA for network communications and interface specification. The requirement details, design, and implementation of DAN are discussed along with operational experience and future plans.


title: AWESOME: A General Multiagent Learning Algorithm that Converges in Self-Play and Learns a Best Response Against Stationary Opponents

abstract: A satisfactory multiagent learning algorithm should, {\em at a minimum}, learn to play optimally against stationary opponents and converge to a Nash equilibrium in self-play. The algorithm that has come closest, WoLF-IGA, has been proven to have these two properties in 2-player 2-action repeated games--assuming that the opponent's (mixed) strategy is observable. In this paper we present AWESOME, the first algorithm that is guaranteed to have these two properties in {\em all} repeated (finite) games. It requires only that the other players' actual actions (not their strategies) can be observed at each step. It also learns to play optimally against opponents that {\em eventually become} stationary. The basic idea behind AWESOME ({\em Adapt When Everybody is Stationary, Otherwise Move to Equilibrium}) is to try to adapt to the others' strategies when they appear stationary, but otherwise to retreat to a precomputed equilibrium strategy. The techniques used to prove the properties of AWESOME are fundamentally different from those used for previous algorithms, and may help in analyzing other multiagent learning algorithms also.


abstract: In multiagent settings where the agents have different preferences, preference aggregation is a central issue. Voting is a general method for preference aggregation, but seminal results have shown that all general voting protocols are manipulable. One could try to avoid manipulation by using voting protocols where determining a beneficial manipulation is hard computationally. The complexity of manipulating realistic elections where the number of candidates is a small constant was recently studied (Conitzer 2002), but the emphasis was on the question of whether or not a protocol becomes hard to manipulate for some constant number of candidates. That work, in many cases, left open the question: How many candidates are needed to make elections hard to manipulate? This is a crucial question when comparing the relative manipulability of different voting protocols. In this paper we answer that question for the voting protocols of the earlier study: plurality, Borda, STV, Copeland, maximin, regular cup, and randomized cup. We also answer that question for two voting protocols for which no results on the complexity of manipulation have been derived before: veto and plurality with runoff. It turns out that the voting protocols under study become hard to manipulate at 3 candidates, 4 candidates, 7 candidates, or never.


title: State complexes for metamorphic robots

abstract: A metamorphic robotic system is an aggregate of homogeneous robot units which can individually and selectively locomote in such a way as to change the global shape of the system. We introduce a mathematical framework for defining and analyzing general metamorphic robots. This formal structure, combined with ideas from geometric group theory, leads to a natural extension of a configuration space for metamorphic robots -- the state complex -- which is especially adapted to parallelization. We present an algorithm for optimizing reconfiguration sequences with respect to elapsed time. A universal geometric property of state complexes -- non-positive curvature -- is the key to proving convergence to the globally time-optimal solution.


title: Optimal Adaptive Algorithms for Finding the Nearest and Farthest Point on a Parametric Black-Box Curve

abstract: We consider a general model for representing and manipulating parametric curves, in which a curve is specified by a black box mapping a parameter value between 0 and 1 to a point in Euclidean d-space. In this model, we consider the nearest-point-on-curve and farthest-point-on-curve problems: given a curve C and a point p, find a point on C nearest to p or farthest from p. In the general black-box model, no algorithm can solve these problems. Assuming a known bound on the speed of the curve (a Lipschitz condition), the answer can be estimated up to an additive error of epsilon using O(1/epsilon) samples, and this bound is tight in the worst case. However, many instances can be solved with substantially fewer samples, and we give algorithms that adapt to the inherent difficulty of the particular instance, up to a logarithmic factor. More precisely, if OPT(C,p,epsilon) is the minimum number of samples of C that every correct algorithm must perform to achieve tolerance epsilon, then our algorithm performs O(OPT(C,p,epsilon) log (epsilon^(-1)/OPT(C,p,epsilon))) samples. Furthermore, any algorithm requires Omega(k log (epsilon^(-1)/k)) samples for some instance C' with OPT(C',p,epsilon) = k; except that, for the nearest-point-on-curve problem when the distance between C and p is less than epsilon, OPT is 1 but the upper and lower bounds on the number of samples are both Theta(1/epsilon). When bounds on relative error are desired, we give algorithms that perform O(OPT log (2+(1+epsilon^(-1)) m^(-1)/OPT)) samples (where m is the exact minimum or maximum distance from p to C) and prove that Omega(OPT log (1/epsilon)) samples are necessary on some problem instances.


title: BL-WoLF: A Framework For Loss-Bounded Learnability In Zero-Sum Games

abstract: We present BL-WoLF, a framework for learnability in repeated zero-sum games where the cost of learning is measured by the losses the learning agent accrues (rather than the number of rounds). The game is adversarially chosen from some family that the learner knows. The opponent knows the game and the learner's learning strategy. The learner tries to either not accrue losses, or to quickly learn about the game so as to avoid future losses (this is consistent with the Win or Learn Fast (WoLF) principle; BL stands for ``bounded loss''). Our framework allows for both probabilistic and approximate learning. The resultant notion of {\em BL-WoLF}-learnability can be applied to any class of games, and allows us to measure the inherent disadvantage to a player that does not know which game in the class it is in. We present {\em guaranteed BL-WoLF-learnability} results for families of games with deterministic payoffs and families of games with stochastic payoffs. We demonstrate that these families are {\em guaranteed approximately BL-WoLF-learnable} with lower cost. We then demonstrate families of games (both stochastic and deterministic) that are not guaranteed BL-WoLF-learnable. We show that those families, nevertheless, are {\em BL-WoLF-learnable}. To prove these results, we use a key lemma which we derive.


title: Management of Grid Jobs and Information within SAMGrid

abstract: We describe some of the key aspects of the SAMGrid system, used by the D0 and CDF experiments at Fermilab. Having sustained success of the data handling part of SAMGrid, we have developed new services for job and information services. Our job management is rooted in \CondorG and uses enhancements that are general applicability for HEP grids. Our information system is based on a uniform framework for configuration management based on XML data representation and processing.


title: Eprints and the Open Archives Initiative

abstract: The Open Archives Initiative (OAI) was created as a practical way to promote interoperability between eprint repositories. Although the scope of the OAI has been broadened, eprint repositories still represent a significant fraction of OAI data providers. In this article I present a brief survey of OAI eprint repositories, and of services using metadata harvested from eprint repositories using the OAI protocol for metadata harvesting (OAI-PMH). I then discuss several situations where metadata harvesting may be used to further improve the utility of eprint archives as a component of the scholarly communication infrastructure.


title: Finding the "truncated" polynomial that is closest to a function

abstract: When implementing regular enough functions (e.g., elementary or special functions) on a computing system, we frequently use polynomial approximations. In most cases, the polynomial that best approximates (for a given distance and in a given interval) a function has coefficients that are not exactly representable with a finite number of bits. And yet, the polynomial approximations that are actually implemented do have coefficients that are represented with a finite - and sometimes small - number of bits: this is due to the finiteness of the floating-point representations (for software implementations), and to the need to have small, hence fast and/or inexpensive, multipliers (for hardware implementations). We then have to consider polynomial approximations for which the degree-$i$ coefficient has at most $m_i$ fractional bits (in other words, it is a rational number with denominator $2^{m_i}$). We provide a general method for finding the best polynomial approximation under this constraint. Then, we suggest refinements than can be used to accelerate our method.


title: Probabilistic Reasoning as Information Compression by Multiple Alignment, Unification and Search: An Introduction and Overview

abstract: This article introduces the idea that probabilistic reasoning (PR) may be understood as "information compression by multiple alignment, unification and search" (ICMAUS). In this context, multiple alignment has a meaning which is similar to but distinct from its meaning in bio-informatics, while unification means a simple merging of matching patterns, a meaning which is related to but simpler than the meaning of that term in logic. A software model, SP61, has been developed for the discovery and formation of 'good' multiple alignments, evaluated in terms of information compression. The model is described in outline. Using examples from the SP61 model, this article describes in outline how the ICMAUS framework can model various kinds of PR including: PR in best-match pattern recognition and information retrieval; one-step 'deductive' and 'abductive' PR; inheritance of attributes in a class hierarchy; chains of reasoning (probabilistic decision networks and decision trees, and PR with 'rules'); geometric analogy problems; nonmonotonic reasoning and reasoning with default values; modelling the function of a Bayesian network.


title: Supporting Out-of-turn Interactions in a Multimodal Web Interface

abstract: Multimodal interfaces are becoming increasingly important with the advent of mobile devices, accessibility considerations, and novel software technologies that combine diverse interaction media. This article investigates systems support for web browsing in a multimodal interface. Specifically, we outline the design and implementation of a software framework that integrates hyperlink and speech modes of interaction. Instead of viewing speech as merely an alternative interaction medium, the framework uses it to support out-of-turn interaction, providing a flexibility of information access not possible with hyperlinks alone. This approach enables the creation of websites that adapt to the needs of users, yet permits the designer fine-grained control over what interactions to support. Design methodology, implementation details, and two case studies are presented.


title: Observation-based Cooperation Enforcement in Ad Hoc Networks

abstract: Ad hoc networks rely on the cooperation of the nodes participating in the network to forward packets for each other. A node may decide not to cooperate to save its resources while still using the network to relay its traffic. If too many nodes exhibit this behavior, network performance degrades and cooperating nodes may find themselves unfairly loaded. Most previous efforts to counter this behavior have relied on further cooperation between nodes to exchange reputation information about other nodes. If a node observes another node not participating correctly, it reports this observation to other nodes who then take action to avoid being affected and potentially punish the bad node by refusing to forward its traffic. Unfortunately, such second-hand reputation information is subject to false accusations and requires maintaining trust relationships with other nodes. The objective of OCEAN is to avoid this trust-management machinery and see how far we can get simply by using direct first-hand observations of other nodes' behavior. We find that, in many scenarios, OCEAN can do as well as, or even better than, schemes requiring second-hand reputation exchanges. This encouraging result could possibly help obviate solutions requiring trust-management for some contexts.


title: 'Computing' as Information Compression by Multiple Alignment, Unification and Search

abstract: This paper argues that the operations of a 'Universal Turing Machine' (UTM) and equivalent mechanisms such as the 'Post Canonical System' (PCS) - which are widely accepted as definitions of the concept of `computing' - may be interpreted as *information compression by multiple alignment, unification and search* (ICMAUS). The motivation for this interpretation is that it suggests ways in which the UTM/PCS model may be augmented in a proposed new computing system designed to exploit the ICMAUS principles as fully as possible. The provision of a relatively sophisticated search mechanism in the proposed 'SP' system appears to open the door to the integration and simplification of a range of functions including unsupervised inductive learning, best-match pattern recognition and information retrieval, probabilistic reasoning, planning and problem solving, and others. Detailed consideration of how the ICMAUS principles may be applied to these functions is outside the scope of this article but relevant sources are cited in this article.


title: Syntax, Parsing and Production of Natural Language in a Framework of Information Compression by Multiple Alignment, Unification and Search

abstract: This article introduces the idea that "information compression by multiple alignment, unification and search" (ICMAUS) provides a framework within which natural language syntax may be represented in a simple format and the parsing and production of natural language may be performed in a transparent manner. The ICMAUS concepts are embodied in a software model, SP61. The organisation and operation of the model are described and a simple example is presented showing how the model can achieve parsing of natural language. Notwithstanding the apparent paradox of 'decompression by compression', the ICMAUS framework, without any modification, can produce a sentence by decoding a compressed code for the sentence. This is illustrated with output from the SP61 model. The article includes four other examples - one of the parsing of a sentence in French and three from the domain of English auxiliary verbs. These examples show how the ICMAUS framework and the SP61 model can accommodate 'context sensitive' features of syntax in a relatively simple and direct manner.


title: Architecture of an Open-Sourced, Extensible Data Warehouse Builder: InterBase 6 Data Warehouse Builder (IB-DWB)

abstract: We report the development of an open-sourced data warehouse builder, InterBase Data Warehouse Builder (IB-DWB), based on Borland InterBase 6 Open Edition Database Server. InterBase 6 is used for its low maintenance and small footprint. IB-DWB is designed modularly and consists of 5 main components, Data Plug Platform, Discoverer Platform, Multi-Dimensional Cube Builder, and Query Supporter, bounded together by a Kernel. It is also an extensible system, made possible by the Data Plug Platform and the Discoverer Platform. Currently, extensions are only possible via dynamic linked-libraries (DLLs). Multi-Dimensional Cube Builder represents a basal mean of data aggregation. The architectural philosophy of IB-DWB centers around providing a base platform that is extensible, which is functionally supported by expansion modules. IB-DWB is currently being hosted by sourceforge.net (Project Unix Name: ib-dwb), licensed under GNU General Public License, Version 2.


title: Complexity of Determining Nonemptiness of the Core

abstract: Coalition formation is a key problem in automated negotiation among self-interested agents, and other multiagent applications. A coalition of agents can sometimes accomplish things that the individual agents cannot, or can do things more efficiently. However, motivating the agents to abide to a solution requires careful analysis: only some of the solutions are stable in the sense that no group of agents is motivated to break off and form a new coalition. This constraint has been studied extensively in cooperative game theory. However, the computational questions around this constraint have received less attention. When it comes to coalition formation among software agents (that represent real-world parties), these questions become increasingly explicit. In this paper we define a concise general representation for games in characteristic form that relies on superadditivity, and show that it allows for efficient checking of whether a given outcome is in the core. We then show that determining whether the core is nonempty is $\mathcal{NP}$-complete both with and without transferable utility. We demonstrate that what makes the problem hard in both cases is determining the collaborative possibilities (the set of outcomes possible for the grand coalition), by showing that if these are given, the problem becomes tractable in both cases. However, we then demonstrate that for a hybrid version of the problem, where utility transfer is possible only within the grand coalition, the problem remains $\mathcal{NP}$-complete even when the collaborative possibilities are given.


title: Definition and Complexity of Some Basic Metareasoning Problems

abstract: In most real-world settings, due to limited time or other resources, an agent cannot perform all potentially useful deliberation and information gathering actions. This leads to the metareasoning problem of selecting such actions. Decision-theoretic methods for metareasoning have been studied in AI, but there are few theoretical results on the complexity of metareasoning. We derive hardness results for three settings which most real metareasoning systems would have to encompass as special cases. In the first, the agent has to decide how to allocate its deliberation time across anytime algorithms running on different problem instances. We show this to be $\mathcal{NP}$-complete. In the second, the agent has to (dynamically) allocate its deliberation or information gathering resources across multiple actions that it has to choose among. We show this to be $\mathcal{NP}$-hard even when evaluating each individual action is extremely simple. In the third, the agent has to (dynamically) choose a limited number of deliberation or information gathering actions to disambiguate the state of the world. We show that this is $\mathcal{NP}$-hard under a natural restriction, and $\mathcal{PSPACE}$-hard in general.


title: Universal Voting Protocol Tweaks to Make Manipulation Hard

abstract: Voting is a general method for preference aggregation in multiagent settings, but seminal results have shown that all (nondictatorial) voting protocols are manipulable. One could try to avoid manipulation by using voting protocols where determining a beneficial manipulation is hard computationally. A number of recent papers study the complexity of manipulating existing protocols. This paper is the first work to take the next step of designing new protocols that are especially hard to manipulate. Rather than designing these new protocols from scratch, we instead show how to tweak existing protocols to make manipulation hard, while leaving much of the original nature of the protocol intact. The tweak studied consists of adding one elimination preround to the election. Surprisingly, this extremely simple and universal tweak makes typical protocols hard to manipulate! The protocols become NP-hard, #P-hard, or PSPACE-hard to manipulate, depending on whether the schedule of the preround is determined before the votes are collected, after the votes are collected, or the scheduling and the vote collecting are interleaved, respectively. We prove general sufficient conditions on the protocols for this tweak to introduce the hardness, and show that the most common voting protocols satisfy those conditions. These are the first results in voting settings where manipulation is in a higher complexity class than NP (presuming PSPACE $\neq$ NP).


title: Lattice QCD Production on Commodity Clusters at Fermilab

abstract: We describe the construction and results to date of Fermilab's three Myrinet-networked lattice QCD production clusters (an 80-node dual Pentium III cluster, a 48-node dual Xeon cluster, and a 128-node dual Xeon cluster). We examine a number of aspects of performance of the MILC lattice QCD code running on these clusters.


title: Defying Dimensions Mod 6

abstract: We show that a certain representation of the matrix-product can be computed with $n^{o(1)}$ multiplications. We also show, that siumilar representations of matrices can be compressed enormously.


title: Tools and Techniques for Managing Clusters for SciDAC Lattice QCD at Fermilab

abstract: Fermilab operates several clusters for lattice gauge computing. Minimal manpower is available to manage these clusters. We have written a number of tools and developed techniques to cope with this task. We describe our tools which use the IPMI facilities of our systems for hardware management tasks such as remote power control, remote system resets, and health monitoring. We discuss our techniques involving network booting for installation and upgrades of the operating system on these computers, and for reloading BIOS and other firmware. Finally, we discuss our tools for parallel command processing and their use in monitoring and administrating the PBS batch queue system used on our clusters.


title: Transformations of Logic Programs with Goals as Arguments

abstract: We consider a simple extension of logic programming where variables may range over goals and goals may be arguments of predicates. In this language we can write logic programs which use goals as data. We give practical evidence that, by exploiting this capability when transforming programs, we can improve program efficiency. We propose a set of program transformation rules which extend the familiar unfolding and folding rules and allow us to manipulate clauses with goals which occur as arguments of predicates. In order to prove the correctness of these transformation rules, we formally define the operational semantics of our extended logic programming language. This semantics is a simple variant of LD-resolution. When suitable conditions are satisfied this semantics agrees with LD-resolution and, thus, the programs written in our extended language can be run by ordinary Prolog systems. Our transformation rules are shown to preserve the operational semantics and termination.


title: Testing Bipartiteness of Geometric Intersection Graphs

abstract: We show how to test the bipartiteness of an intersection graph of n line segments or simple polygons in the plane, or of balls in R^d, in time O(n log n). More generally we find subquadratic algorithms for connectivity and bipartiteness testing of intersection graphs of a broad class of geometric objects. For unit balls in R^d, connectivity testing has equivalent randomized complexity to construction of Euclidean minimum spanning trees, and hence is unlikely to be solved as efficiently as bipartiteness testing. For line segments or planar disks, testing k-colorability of intersection graphs for k>2 is NP-complete.


title: Architecture of monitoring elements for the network element modeling in a Grid infrastructure

abstract: Several tools exist that collect host-to-host connectivity measurements. To improve the usability of such measurements, they should be mapped into a framework consisting of complex subsystems, and the infrastructure that connects them. We introduce one such framework, and analyze the architectural implications on the network structure. In our framework, a complex subsystem consists of several computing facilities and the infrastructure that connects them: we call it a -monitoring domain-. The task of measuring the connectivity between -monitoring domains- is considered distinct from the activity of -storage- and -computing- elements. Therefore we introduce a new element in our topology: we call it -theodolite- element, since its function is similar to that of a transponder. Using these basic concepts, we analyze the architectural implications on the network structure: in a nutshell, if we want that -theodolites- serve as a reference, than the contribution to the relevant network metrics due to the -monitoring domain- infrastructure must be negligible with respect to contributions of the inter-domain infrastructure. In addition all -theodolites- of a -monitoring domain- must give an image of the inter-domain infrastructure that is consistent with that experienced by network applications. We conclude giving a running SQL example of how information about -monitoring domains- and -theodolites- could be organized, and we outline the application of such framework in the GLUE schema activity for the network element


title: Information Compression by Multiple Alignment, Unification and Search as a Unifying Principle in Computing and Cognition

abstract: This article presents an overview of the idea that "information compression by multiple alignment, unification and search" (ICMAUS) may serve as a unifying principle in computing (including mathematics and logic) and in such aspects of human cognition as the analysis and production of natural language, fuzzy pattern recognition and best-match information retrieval, concept hierarchies with inheritance of attributes, probabilistic reasoning, and unsupervised inductive learning. The ICMAUS concepts are described together with an outline of the SP61 software model in which the ICMAUS concepts are currently realised. A range of examples is presented, illustrated with output from the SP61 model.


title: Improving the Security and Performance of the BaBar Detector Controls System

abstract: It starts out innocently enough - users want to monitor Online data and so run their own copies of the detector control GUIs in their offices and at home. But over time, the number of processes making requests for values to display on GUIs, webpages and stripcharts can grow, and affect the performance of an Input/Output Controller (IOC) such that it is unable to respond to requests from requests critical to data-taking. At worst, an IOC can hang, its CPU having been allocated 100% to responding to network requests. For the BaBar Online Detector Control System, we were able to eliminate this problem and make great gains in security by moving all of the IOCs to a non-routed, virtual LAN and by enlisting a workstation with two network interface cards to act as the interface between the virtual LAN and the public BaBar network. On the interface machine, we run the Experimental Physics Industrial Control System (EPICS) Channel Access (CA) gateway software (originating from Advanced Photon Source). This software accepts as inputs, all the channels which are loaded into the EPICS databases on all the IOCs. It polls them to update its copy of the values. It answers requests from applications by sending them the currently cached value. We adopted the requirement that data-taking would be independent of the gateway, so that, in the event of a gateway failure, data-taking would be uninterrupted. In this way, we avoided introducing any new risk elements to data-taking. Security rules already in use by the IOC were propagated to the gateway's own security rules and the security of the IOCs themselves was improved by removing them from the public BaBar network.


title: Deterministic Sampling and Range Counting in Geometric Data Streams

abstract: We present memory-efficient deterministic algorithms for constructing epsilon-nets and epsilon-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic samples provide guaranteed bounds on their approximation factors. We show how our deterministic samples can be used to answer approximate online iceberg geometric queries on data streams. We use these techniques to approximate several robust statistics of geometric data streams, including Tukey depth, simplicial depth, regression depth, the Thiel-Sen estimator, and the least median of squares. Our algorithms use only a polylogarithmic amount of memory, provided the desired approximation factors are inverse-polylogarithmic. We also include a lower bound for non-iceberg geometric queries.


title: Issues in Communication Game

abstract: As interaction between autonomous agents, communication can be analyzed in game-theoretic terms. Meaning game is proposed to formalize the core of intended communication in which the sender sends a message and the receiver attempts to infer its meaning intended by the sender. Basic issues involved in the game of natural language communication are discussed, such as salience, grammaticality, common sense, and common belief, together with some demonstration of the feasibility of game-theoretic account of language.


title: The ray attack, an inefficient trial to break RSA cryptosystems

abstract: The basic properties of RSA cryptosystems and some classical attacks on them are described. Derived from geometric properties of the Euler functions, the Euler function rays, a new ansatz to attack RSA cryptosystems is presented. A resulting, albeit inefficient, algorithm is given. It essentially consists of a loop with starting value determined by the Euler function ray and with step width given by a function $\omega_e(n)$ being a multiple of the order $\mathrm{ord}_n(e)$, where $e$ denotes the public key exponent and $n$ the RSA modulus. For $n=pq$ and an estimate $r<\sqrt{pq}$ for the smaller prime factor $p$, the running time is given by $T(e,n,r) = O((r-p)\ln e \ln n \ln r).$


title: Parsing and Generation with Tabulation and Compilation

abstract: The standard tabulation techniques for logic programming presuppose fixed order of computation. Some data-driven control should be introduced in order to deal with diverse contexts. The present paper describes a data-driven method of constraint transformation with a sort of compilation which subsumes accessibility check and last-call optimization, which characterize standard natural-language parsing techniques, semantic-head-driven generation, etc.


title: Automatic Classification using Self-Organising Neural Networks in Astrophysical Experiments

abstract: Self-Organising Maps (SOMs) are effective tools in classification problems, and in recent years the even more powerful Dynamic Growing Neural Networks, a variant of SOMs, have been developed. Automatic Classification (also called clustering) is an important and difficult problem in many Astrophysical experiments, for instance, Gamma Ray Burst classification, or gamma-hadron separation. After a brief introduction to classification problem, we discuss Self-Organising Maps in section 2. Section 3 discusses with various models of growing neural networks and finally in section 4 we discuss the research perspectives in growing neural networks for efficient classification in astrophysical problems.


title: Data Management and Mining in Astrophysical Databases

abstract: We analyse the issues involved in the management and mining of astrophysical data. The traditional approach to data management in the astrophysical field is not able to keep up with the increasing size of the data gathered by modern detectors. An essential role in the astrophysical research will be assumed by automatic tools for information extraction from large datasets, i.e. data mining techniques, such as clustering and classification algorithms. This asks for an approach to data management based on data warehousing, emphasizing the efficiency and simplicity of data access; efficiency is obtained using multidimensional access methods and simplicity is achieved by properly handling metadata. Clustering and classification techniques, on large datasets, pose additional requirements: computational and memory scalability with respect to the data size, interpretability and objectivity of clustering or classification results. In this study we address some possible solutions.


title: Excellence in Computer Simulation

abstract: Excellent computer simulations are done for a purpose. The most valid purposes are to explore uncharted territory, to resolve a well-posed scientific or technical question, or to make a design choice. Stand-alone modeling can serve the first purpose. The other two goals need a full integration of the modeling effort into a scientific or engineering program. Some excellent work, much of it related to the Department of Energy Laboratories, is reviewed. Some less happy stories are recounted. In the past, some of the most impressive work has involved complexity and chaos. Prediction in a complex world requires a first principles understanding based upon the intersection of theory, experiment and simulation.


title: Range Mode and Range Median Queries on Lists and Trees

abstract: We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of labels on the path from u to v.


title: Adaptive Domain Model: Dealing With Multiple Attributes of Self-Managing Distributed Object Systems

abstract: Self-managing software has emerged as modern systems have become more complex. Some of the distributed object systems may contain thousands of objects deployed on tens or even hundreds hosts. Development and support of such systems often costs a lot. To solve this issue the systems, which are capable supporting multiple self-managing attributes, should be created. In the paper, the Adaptive domain concept is introduced as an extension to the basic domain concept to support a generic adaptation environment for building distributed object systems with multiple self-managing attributes.


title: Small-World File-Sharing Communities

abstract: Web caches, content distribution networks, peer-to-peer file sharing networks, distributed file systems, and data grids all have in common that they involve a community of users who generate requests for shared data. In each case, overall system performance can be improved significantly if we can first identify and then exploit interesting structure within a community's access patterns. To this end, we propose a novel perspective on file sharing based on the study of the relationships that form among users based on the files in which they are interested. We propose a new structure that captures common user interests in data--the data-sharing graph-- and justify its utility with studies on three data-distribution systems: a high-energy physics collaboration, the Web, and the Kazaa peer-to-peer network. We find small-world patterns in the data-sharing graphs of all three communities. We analyze these graphs and propose some probable causes for these emergent small-world patterns. The significance of small-world patterns is twofold: it provides a rigorous support to intuition and, perhaps most importantly, it suggests ways to design mechanisms that exploit these naturally emerging patterns.


title: Supporting Dynamic Ad hoc Collaboration Capabilities

abstract: Modern HENP experiments such as CMS and Atlas involve as many as 2000 collaborators around the world. Collaborations this large will be unable to meet often enough to support working closely together. Many of the tools currently available for collaboration focus on heavy-weight applications such as videoconferencing tools. While these are important, there is a more basic need for tools that support connecting physicists to work together on an ad hoc or continuous basis. Tools that support the day-to-day connectivity and underlying needs of a group of collaborators are important for providing light-weight, non-intrusive, and flexible ways to work collaboratively. Some example tools include messaging, file-sharing, and shared plot viewers. An important component of the environment is a scalable underlying communication framework. In this paper we will describe our current progress on building a dynamic and ad hoc collaboration environment and our vision for its evolution into a HENP collaboration environment.


title: Manifold Learning with Geodesic Minimal Spanning Trees

abstract: In the manifold learning problem one seeks to discover a smooth low dimensional surface, i.e., a manifold embedded in a higher dimensional linear vector space, based on a set of measured sample points on the surface. In this paper we consider the closely related problem of estimating the manifold's intrinsic dimension and the intrinsic entropy of the sample points. Specifically, we view the sample points as realizations of an unknown multivariate density supported on an unknown smooth manifold. We present a novel geometrical probability approach, called the geodesic-minimal-spanning-tree (GMST), to obtaining asymptotically consistent estimates of the manifold dimension and the R\'{e}nyi $\alpha$-entropy of the sample density on the manifold. The GMST approach is striking in its simplicity and does not require reconstructing the manifold or estimating the multivariate density of the samples. The GMST method simply constructs a minimal spanning tree (MST) sequence using a geodesic edge matrix and uses the overall lengths of the MSTs to simultaneously estimate manifold dimension and entropy. We illustrate the GMST approach for dimension and entropy estimation of a human face dataset.


title: Modeling Business

abstract: Business concepts are studied using a metamodel-based approach, using UML 2.0. The Notation Independent Business concepts metamodel is introduced. The approach offers a mapping between different business modeling notations which could be used for bridging BM tools and boosting the MDA approach.


title: Bridging the gap between modal temporal logics and constraint-based QSR as an ALC(D) spatio-temporalisation with weakly cyclic TBoxes

abstract: The aim of this work is to provide a family of qualitative theories for spatial change in general, and for motion of spatial scenes in particular. To achieve this, we consider a spatio-temporalisation MTALC(D_x), of the well-known ALC(D) family of Description Logics (DLs) with a concrete domainan. In particular, the concrete domain D_x is generated by a qualitative spatial Relation Algebra (RA) x. We show the important result that satisfiability of an MTALC(D_x) concept with respect to a weakly cyclic TBox is decidable in nondeterministic exponential time, by reducing it to the emptiness problem of a weak alternating automaton augmented with spatial constraints, which we show to remain decidable, although the accepting condition of a run involves, additionally to the standard case, consistency of a CSP (Constraint Satisfaction Problem) potentially infinite. The result provides an effective tableaux-like satisfiability procedure which is discussed.


title: High-density and Secure Data Transmission via Linear Combinations

abstract: Suppose that there are $n$ Senders and $n$ Receivers. Our goal is to send long messages from Sender $i$ to Receiver $i$ such that no other receiver can retrieve the message intended for Receiver $i$. The task can easily be completed using $n$ private channels between the pairs. Solutions, using one channel needs either encryption or switching elements for routing the messages to their addressee. The main result of the present work is a description of a network in which The Senders and the Receivers are connected with only $n^{o(1)}$ channels; the encoding and de-coding is nothing else just very fast linear combinations of the message-bits; and there are no switching or routing-elements in the network, just linear combinations are computed, with fixed connections (channels or wires). In the proofs we do not use {\em any} unproven cryptographical or complexity theoretical assumptions.


title: A Note on Objects Built From Bricks without Corners

abstract: We report a small advance on a question raised by Robertson, Schweitzer, and Wagon in [RSW02]. They constructed a genus-13 polyhedron built from bricks without corners, and asked whether every genus-0 such polyhedron must have a corner. A brick is a parallelopiped, and a corner is a brick of degree three or less in the brick graph. We describe a genus-3 polyhedron built from bricks with no corner, narrowing the genus gap.


title: An Extension of the Lovasz Local Lemma, and its Applications to Integer Programming

abstract: The Lovasz Local Lemma due to Erdos and Lovasz is a powerful tool in proving the existence of rare events. We present an extension of this lemma, which works well when the event to be shown to exist is a conjunction of individual events, each of which asserts that a random variable does not deviate much from its mean. As applications, we consider two classes of NP-hard integer programs: minimax and covering integer programs. A key technique, randomized rounding of linear relaxations, was developed by Raghavan and Thompson to derive good approximation algorithms for such problems. We use our extension of the Local Lemma to prove that randomized rounding produces, with non-zero probability, much better feasible solutions than known before, if the constraint matrices of these integer programs are column-sparse (e.g., routing using short paths, problems on hypergraphs with small dimension/degree). This complements certain well-known results from discrepancy theory. We also generalize the method of pessimistic estimators due to Raghavan, to obtain constructive (algorithmic) versions of our results for covering integer programs.


title: The Linguistic DS: Linguisitic Description in MPEG-7

abstract: MPEG-7 (Moving Picture Experts Group Phase 7) is an XML-based international standard on semantic description of multimedia content. This document discusses the Linguistic DS and related tools. The linguistic DS is a tool, based on the GDA tag set (http://i-content.org/GDA/tagset.html), for semantic annotation of linguistic data in or associated with multimedia content. The current document text reflects `Study of FPDAM - MPEG-7 MDS Extensions' issued in March 2003, and not most part of MPEG-7 MDS, for which the readers are referred to the first version of MPEG-7 MDS document available from ISO (http://www.iso.org). Without that reference, however, this document should be mostly intelligible to those who are familiar with XML and linguistic theories. Comments are welcome and will be considered in the standardization process.


title: Flexible Camera Calibration Using a New Analytical Radial Undistortion Formula with Application to Mobile Robot Localization

abstract: Most algorithms in 3D computer vision rely on the pinhole camera model because of its simplicity, whereas virtually all imaging devices introduce certain amount of nonlinear distortion, where the radial distortion is the most severe part. Common approach to radial distortion is by the means of polynomial approximation, which introduces distortion-specific parameters into the camera model and requires estimation of these distortion parameters. The task of estimating radial distortion is to find a radial distortion model that allows easy undistortion as well as satisfactory accuracy. This paper presents a new radial distortion model with an easy analytical undistortion formula, which also belongs to the polynomial approximation category. Experimental results are presented to show that with this radial distortion model, satisfactory accuracy is achieved. An application of the new radial distortion model is non-iterative yellow line alignment with a calibrated camera on ODIS, a robot built in our CSOIS.


title: A New Analytical Radial Distortion Model for Camera Calibration

abstract: Common approach to radial distortion is by the means of polynomial approximation, which introduces distortion-specific parameters into the camera model and requires estimation of these distortion parameters. The task of estimating radial distortion is to find a radial distortion model that allows easy undistortion as well as satisfactory accuracy. This paper presents a new radial distortion model with an easy analytical undistortion formula, which also belongs to the polynomial approximation category. Experimental results are presented to show that with this radial distortion model, satisfactory accuracy is achieved.


title: Rational Radial Distortion Models with Analytical Undistortion Formulae

abstract: The common approach to radial distortion is by the means of polynomial approximation, which introduces distortion-specific parameters into the camera model and requires estimation of these distortion parameters. The task of estimating radial distortion is to find a radial distortion model that allows easy undistortion as well as satisfactory accuracy. This paper presents a new class of rational radial distortion models with easy analytical undistortion formulae. Experimental results are presented to show that with this class of rational radial distortion models, satisfactory and comparable accuracy is achieved.


title: Integrating cardinal direction relations and other orientation relations in Qualitative Spatial Reasoning

abstract: We propose a calculus integrating two calculi well-known in Qualitative Spatial Reasoning (QSR): Frank's projection-based cardinal direction calculus, and a coarser version of Freksa's relative orientation calculus. An original constraint propagation procedure is presented, which implements the interaction between the two integrated calculi. The importance of taking into account the interaction is shown with a real example providing an inconsistent knowledge base, whose inconsistency (a) cannot be detected by reasoning separately about each of the two components of the knowledge, just because, taken separately, each is consistent, but (b) is detected by the proposed algorithm, thanks to the interaction knowledge propagated from each of the two compnents to the other.


title: Limit groups and groups acting freely on $\bbR^n$-trees

abstract: We give a simple proof of the finite presentation of Sela's limit groups by using free actions on $\bbR^n$-trees. We first prove that Sela's limit groups do have a free action on an $\bbR^n$-tree. We then prove that a finitely generated group having a free action on an $\bbR^n$-tree can be obtained from free abelian groups and surface groups by a finite sequence of free products and amalgamations over cyclic groups. As a corollary, such a group is finitely presented, has a finite classifying space, its abelian subgroups are finitely generated and contains only finitely many conjugacy classes of non-cyclic maximal abelian subgroups.


title: A ternary Relation Algebra of directed lines

abstract: We define a ternary Relation Algebra (RA) of relative position relations on two-dimensional directed lines (d-lines for short). A d-line has two degrees of freedom (DFs): a rotational DF (RDF), and a translational DF (TDF). The representation of the RDF of a d-line will be handled by an RA of 2D orientations, CYC_t, known in the literature. A second algebra, TA_t, which will handle the TDF of a d-line, will be defined. The two algebras, CYC_t and TA_t, will constitute, respectively, the translational and the rotational components of the RA, PA_t, of relative position relations on d-lines: the PA_t atoms will consist of those pairs <t,r> of a TA_t atom and a CYC_t atom that are compatible. We present in detail the RA PA_t, with its converse table, its rotation table and its composition tables. We show that a (polynomial) constraint propagation algorithm, known in the literature, is complete for a subset of PA_t relations including almost all of the atomic relations. We will discuss the application scope of the RA, which includes incidence geometry, GIS (Geographic Information Systems), shape representation, localisation in (multi-)robot navigation, and the representation of motion prepositions in NLP (Natural Language Processing). We then compare the RA to existing ones, such as an algebra for reasoning about rectangles parallel to the axes of an (orthogonal) coordinate system, a ``spatial Odyssey'' of Allen's interval algebra, and an algebra for reasoning about 2D segments.


title: An Analytical Piecewise Radial Distortion Model for Precision Camera Calibration

abstract: The common approach to radial distortion is by the means of polynomial approximation, which introduces distortion-specific parameters into the camera model and requires estimation of these distortion parameters. The task of estimating radial distortion is to find a radial distortion model that allows easy undistortion as well as satisfactory accuracy. This paper presents a new piecewise radial distortion model with easy analytical undistortion formula. The motivation for seeking a piecewise radial distortion model is that, when a camera is resulted in a low quality during manufacturing, the nonlinear radial distortion can be complex. Using low order polynomials to approximate the radial distortion might not be precise enough. On the other hand, higher order polynomials suffer from the inverse problem. With the new piecewise radial distortion function, more flexibility is obtained and the radial undistortion can be performed analytically. Experimental results are presented to show that with this new piecewise radial distortion model, better performance is achieved than that using the single function. Furthermore, a comparable performance with the conventional polynomial model using 2 coefficients can also be accomplished.


title: Gridscape: A Tool for the Creation of Interactive and Dynamic Grid Testbed Web Portals

abstract: The notion of grid computing has gained an increasing popularity recently as a realistic solution to many of our large-scale data storage and processing needs. It enables the sharing, selection and aggregation of resources geographically distributed across collaborative organisations. Now more and more people are beginning to embrace grid computing and thus are seeing the need to set up their own grids and grid testbeds. With this comes the need to have some means to enable them to view and monitor the status of the resources in these testbeds (eg. Web based Grid portal). Generally developers invest a substantial amount of time and effort developing custom monitoring software. To overcome this limitation, this paper proposes Gridscape ? a tool that enables the rapid creation of interactive and dynamic testbed portals (without any programming effort). Gridscape primarily aims to provide a solution for those users who need to be able to create a grid testbed portal but don?t necessarily have the time or resources to build a system of their own from scratch.


title: Hamevol1.0: a C++ code for differential equations based on Runge-Kutta algorithm. An application to matter enhanced neutrino oscillation

abstract: We present a C++ implementation of a fifth order semi-implicit Runge-Kutta algorithm for solving Ordinary Differential Equations. This algorithm can be used for studying many different problems and in particular it can be applied for computing the evolution of any system whose Hamiltonian is known. We consider in particular the problem of calculating the neutrino oscillation probabilities in presence of matter interactions. The time performance and the accuracy of this implementation is competitive with respect to the other analytical and numerical techniques used in literature. The algorithm design and the salient features of the code are presented and discussed and some explicit examples of code application are given.


title: Contributions to the Development and Improvement of a Regulatory and Pre-Regulatory Digitally System for the Tools within Flexible Fabrication Systems

abstract: The paper reports the obtained results for the projection and realization of a digitally system aiming to assist the equipment for a regulatory and pre-regulatory tools and holding tools within the flexible fabrication systems (FFS). Moreover, based on the present results, the same methodology can be applied for assisting tools from the point of view of their integrity and to wear compensation in the FFS framework.


title: Learning Analogies and Semantic Relations

abstract: We present an algorithm for learning from unlabeled text, based on the Vector Space Model (VSM) of information retrieval, that can solve verbal analogy questions of the kind found in the Scholastic Aptitude Test (SAT). A verbal analogy has the form A:B::C:D, meaning "A is to B as C is to D"; for example, mason:stone::carpenter:wood. SAT analogy questions provide a word pair, A:B, and the problem is to select the most analogous word pair, C:D, from a set of five choices. The VSM algorithm correctly answers 47% of a collection of 374 college-level analogy questions (random guessing would yield 20% correct). We motivate this research by relating it to work in cognitive science and linguistics, and by applying it to a difficult problem in natural language processing, determining semantic relations in noun-modifier pairs. The problem is to classify a noun-modifier pair, such as "laser printer", according to the semantic relation between the noun (printer) and the modifier (laser). We use a supervised nearest-neighbour algorithm that assigns a class to a given noun-modifier pair by finding the most analogous noun-modifier pair in the training data. With 30 classes of semantic relations, on a collection of 600 labeled noun-modifier pairs, the learning algorithm attains an F value of 26.5% (random guessing: 3.3%). With 5 classes of semantic relations, the F value is 43.2% (random: 20%). The performance is state-of-the-art for these challenging problems.


title: From Statistical Knowledge Bases to Degrees of Belief

abstract: An intelligent agent will often be uncertain about various properties of its environment, and when acting in that environment it will frequently need to quantify its uncertainty. For example, if the agent wishes to employ the expected-utility paradigm of decision theory to guide its actions, it will need to assign degrees of belief (subjective probabilities) to various assertions. Of course, these degrees of belief should not be arbitrary, but rather should be based on the information available to the agent. This paper describes one approach for inducing degrees of belief from very rich knowledge bases, that can include information about particular individuals, statistical correlations, physical laws, and default rules. We call our approach the random-worlds method. The method is based on the principle of indifference: it treats all of the worlds the agent considers possible as being equally likely. It is able to integrate qualitative default reasoning with quantitative probabilistic reasoning by providing a language in which both types of information can be easily expressed. Our results show that a number of desiderata that arise in direct inference (reasoning from statistical information to conclusions about individuals) and default reasoning follow directly {from} the semantics of random worlds. For example, random worlds captures important patterns of reasoning such as specificity, inheritance, indifference to irrelevant information, and default assumptions of independence. Furthermore, the expressive power of the language used and the intuitive semantics of random worlds allow the method to deal with problems that are beyond the scope of many other non-deductive reasoning systems.


title: Secrecy in Multiagent Systems

abstract: We introduce a general framework for reasoning about secrecy and privacy requirements in multiagent systems. Our definitions extend earlier definitions of secrecy and nondeducibility given by Shannon and Sutherland. Roughly speaking, one agent maintains secrecy with respect to another if the second agent cannot rule out any possibilities for the behavior or state of the first agent. We show that the framework can handle probability and nondeterminism in a clean way, is useful for reasoning about asynchronous systems as well as synchronous systems, and suggests generalizations of secrecy that may be useful for dealing with issues such as resource-bounded reasoning. We also show that a number of well-known attempts to characterize the absence of information flow are special cases of our definitions of secrecy.


title: Efficient Instrumentation for Performance Profiling

abstract: Performance profiling consists of tracing a software system during execution and then analyzing the obtained traces. However, traces themselves affect the performance of the system distorting its execution. Therefore, there is a need to minimize the effect of the tracing on the underlying system's performance. To achieve this, the trace set needs to be optimized according to the performance profiling problem being solved. Our position is that such minimization can be achieved only by adding the software trace design and implementation to the overall software development process. In such a process, the performance analyst supplies the knowledge of performance measurement requirements, while the software developer supplies the knowledge of the software. Both of these are needed for an optimal trace placement.


title: Group Authentication Using The Naccache-Stern Public-Key Cryptosystem

abstract: A group authentication protocol authenticates pre-defined groups of individuals such that: - No individual is identified - No knowledge of which groups can be successfully authenticated is known to the verifier - No sensitive data is exposed The paper presents a group authentication protocol based on splitting the private keys of the Naccache-Stern public-key cryptosystem in such a way that the Boolean expression defining the authenticable groups is implicit in the split.