title: Neural realisation of the SP theory: cell assemblies revisited

abstract: This paper describes how the elements of the SP theory (Wolff, 2003a) may be realised with neural structures and processes. To the extent that this is successful, the insights that have been achieved in the SP theory - the integration and simplification of a range of phenomena in perception and cognition - may be incorporated in a neural view of brain function. These proposals may be seen as a development of Hebb's (1949) concept of a 'cell assembly'. By contrast with that concept and variants of it, the version described in this paper proposes that any one neuron can belong in one assembly and only one assembly. A distinctive feature of the present proposals is that any neuron or cluster of neurons within a cell assembly may serve as a proxy or reference for another cell assembly or class of cell assemblies. This device provides solutions to many of the problems associated with cell assemblies, it allows information to be stored in a compressed form, and it provides a robust mechanism by which assemblies may be connected to form hierarchies, grammars and other kinds of knowledge structure. Drawing on insights derived from the SP theory, the paper also describes how unsupervised learning may be achieved with neural structures and processes. This theory of learning overcomes weaknesses in the Hebbian concept of learning and it is, at the same time, compatible with the observations that Hebb's theory was designed to explain.


title: Boundary knot method for Laplace and biharmonic problems

abstract: The boundary knot method (BKM) [1] is a meshless boundary-type radial basis function (RBF) collocation scheme, where the nonsingular general solution is used instead of fundamental solution to evaluate the homogeneous solution, while the dual reciprocity method (DRM) is employed to approximation of particular solution. Despite the fact that there are not nonsingular RBF general solutions available for Laplace and biharmonic problems, this study shows that the method can be successfully applied to these problems. The high-order general and fundamental solutions of Burger and Winkler equations are also first presented here.


title: Euclidean algorithms are Gaussian

abstract: This study provides new results about the probabilistic behaviour of a class of Euclidean algorithms: the asymptotic distribution of a whole class of cost-parameters associated to these algorithms is normal. For the cost corresponding to the number of steps Hensley already has proved a Local Limit Theorem; we give a new proof, and extend his result to other euclidean algorithms and to a large class of digit costs, obtaining a faster, optimal, rate of convergence. The paper is based on the dynamical systems methodology, and the main tool is the transfer operator. In particular, we use recent results of Dolgopyat.


title: An Alternative to RDF-Based Languages for the Representation and Processing of Ontologies in the Semantic Web

abstract: This paper describes an approach to the representation and processing of ontologies in the Semantic Web, based on the ICMAUS theory of computation and AI. This approach has strengths that complement those of languages based on the Resource Description Framework (RDF) such as RDF Schema and DAML+OIL. The main benefits of the ICMAUS approach are simplicity and comprehensibility in the representation of ontologies, an ability to cope with errors and uncertainties in knowledge, and a versatile reasoning system with capabilities in the kinds of probabilistic reasoning that seem to be required in the Semantic Web.


title: Implementing an Agent Trade Server

abstract: An experimental server for stock trading autonomous agents is presented and made available, together with an agent shell for swift development. The server, written in Java, was implemented as proof-of-concept for an agent trade server for a real financial exchange.


title: Application of interactive parallel visualization for commodity-based clusters using visualization APIs

abstract: We present an efficient and inexpensive to develop application for interactive high-performance parallel visualization. We extend popular APIs such as Open Inventor and VTK to support commodity-based cluster visualization. Our implementation follows a standard master/slave concept: the general idea is to have a ``Master'' node, which will intercept a sequential graphical user interface (GUI) and broadcast it to the ``Slave'' nodes. The interactions between the nodes are implemented using MPI. The parallel remote rendering uses Chromium. This paper is mainly the report of our implementation experiences. We present in detail the proposed model and key aspects of its implementation. Also, we present performance measurements, we benchmark and quantitatively demonstrate the dependence of the visualization speed on the data size and the network bandwidth, and we identify the singularities and draw conclusions on Chromium's sort-first rendering architecture. The most original part of this work is the combined use of Open Inventor and Chromium.


title: Augernome & XtremWeb: Monte Carlos computation on a global computing platform

abstract: In this paper, we present XtremWeb, a Global Computing platform used to generate monte carlos showers in Auger, an HEP experiment to study the highest energy cosmic rays at Mallargue-Mendoza, Argentina. XtremWeb main goal, as a Global Computing platform, is to compute distributed applications using idle time of widely interconnected machines. It is especially dedicated to -but not limited to- multi-parameters applications such as monte carlos computations; its security mechanisms ensuring not only hosts integrity but also results certification and its fault tolerant features, encouraged us to test it and, finally, to deploy it as to support our CPU needs to simulate showers. We first introduce Auger computing needs and how Global Computing could help. We then detail XtremWeb architecture and goals. The fourth and last part presents the profits we have gained to choose this platform. We conclude on what could be done next.


title: Sound search in a denotational semantics for first order logic

abstract: In this paper we adapt the definitions and results from Apt and Vermeulen on `First order logic as a constraint programming language' (in: Proceedings of LPAR2001, Baaz and Voronkov (eds.), Springer LNAI 2514) to include important ideas about search and choice into the system. We give motivating examples. Then we set up denotational semantics for first order logic as follows: the semantic universe includes states that consist of two components: a substitution, which can be seen as the computed answer; and a constraint satisfaction problem, which can be seen as the residue of the original problem, yet to be handled by constraint programming. The interaction between these components is regulated by an operator called: infer. In this paper we regard infer as an operator on sets of states to enable us to analyze ideas about search among states and choice between states. The precise adaptations of definitions and results are able to deal with the examples and we show that, given several reasonable conditions, the new definitions ensure soundness of the system with respect to the standard interpretation of first order logic. In this way the `reasonable conditions' can be read as conditions for sound search. We indicate briefly how to investigate efficiency of search in future research.


title: Web Access to Cultural Heritage for the Disabled

abstract: Physical disabled access is something that most cultural institutions such as museums consider very seriously. Indeed, there are normally legal requirements to do so. However, online disabled access is still a relatively novel and developing field. Many cultural organizations have not yet considered the issues in depth and web developers are not necessarily experts either. The interface for websites is normally tested with major browsers, but not with specialist software like text to audio converters for the blind or against the relevant accessibility and validation standards. We consider the current state of the art in this area, especially with respect to aspects of particular importance to the access of cultural heritage.


title: A logic for reasoning about upper probabilities

abstract: We present a propositional logic %which can be used to reason about the uncertainty of events, where the uncertainty is modeled by a set of probability measures assigning an interval of probability to each event. We give a sound and complete axiomatization for the logic, and show that the satisfiability problem is NP-complete, no harder than satisfiability for propositional logic.


title: Modeling Belief in Dynamic Systems, Part I: Foundations

abstract: Belief change is a fundamental problem in AI: Agents constantly have to update their beliefs to accommodate new observations. In recent years, there has been much work on axiomatic characterizations of belief change. We claim that a better understanding of belief change can be gained from examining appropriate semantic models. In this paper we propose a general framework in which to model belief change. We begin by defining belief in terms of knowledge and plausibility: an agent believes p if he knows that p is more plausible than its negation. We then consider some properties defining the interaction between knowledge and plausibility, and show how these properties affect the properties of belief. In particular, we show that by assuming two of the most natural properties, belief becomes a KD45 operator. Finally, we add time to the picture. This gives us a framework in which we can talk about knowledge, plausibility (and hence belief), and time, which extends the framework of Halpern and Fagin for modeling knowledge in multi-agent systems. We then examine the problem of ``minimal change''. This notion can be captured by using prior plausibilities, an analogue to prior probabilities, which can be updated by ``conditioning''. We show by example that conditioning on a plausibility measure can capture many scenarios of interest. In a companion paper, we show how the two best-studied scenarios of belief change, belief revisionand belief update, fit into our framework.


title: Modeling Belief in Dynamic Systems, Part II: Revisions and Update

abstract: The study of belief change has been an active area in philosophy and AI. In recent years two special cases of belief change, belief revision and belief update, have been studied in detail. In a companion paper, we introduce a new framework to model belief change. This framework combines temporal and epistemic modalities with a notion of plausibility, allowing us to examine the change of beliefs over time. In this paper, we show how belief revision and belief update can be captured in our framework. This allows us to compare the assumptions made by each method, and to better understand the principles underlying them. In particular, it shows that Katsuno and Mendelzon's notion of belief update depends on several strong assumptions that may limit its applicability in artificial intelligence. Finally, our analysis allow us to identify a notion of minimal change that underlies a broad range of belief change operations including revision and update.


title: Camera Calibration: a USU Implementation

abstract: The task of camera calibration is to estimate the intrinsic and extrinsic parameters of a camera model. Though there are some restricted techniques to infer the 3-D information about the scene from uncalibrated cameras, effective camera calibration procedures will open up the possibility of using a wide range of existing algorithms for 3-D reconstruction and recognition. The applications of camera calibration include vision-based metrology, robust visual platooning and visual docking of mobile robots where the depth information is important.


title: Search and Navigation in Relational Databases

abstract: We present a new application for keyword search within relational databases, which uses a novel algorithm to solve the join discovery problem by finding Memex-like trails through the graph of foreign key dependencies. It differs from previous efforts in the algorithms used, in the presentation mechanism and in the use of primary-key only database queries at query-time to maintain a fast response for users. We present examples using the DBLP data set.


title: Two- versus three-dimensional connectivity testing of first-order queries to semi-algebraic sets

abstract: This paper addresses the question whether one can determine the connectivity of a semi-algebraic set in three dimensions by testing the connectivity of a finite number of two-dimensional ``samples'' of the set, where these samples are defined by first-order queries. The question is answered negatively for two classes of first-order queries: cartesian-product-free, and positive one-pass.


title: Quantifying and Visualizing Attribute Interactions

abstract: Interactions are patterns between several attributes in data that cannot be inferred from any subset of these attributes. While mutual information is a well-established approach to evaluating the interactions between two attributes, we surveyed its generalizations as to quantify interactions between several attributes. We have chosen McGill's interaction information, which has been independently rediscovered a number of times under various names in various disciplines, because of its many intuitively appealing properties. We apply interaction information to visually present the most important interactions of the data. Visualization of interactions has provided insight into the structure of data on a number of domains, identifying redundant attributes and opportunities for constructing new features, discovering unexpected regularities in data, and have helped during construction of predictive models; we illustrate the methods on numerous examples. A machine learning method that disregards interactions may get caught in two traps: myopia is caused by learning algorithms assuming independence in spite of interactions, whereas fragmentation arises from assuming an interaction in spite of independence.


title: A Family of Simplified Geometric Distortion Models for Camera Calibration

abstract: The commonly used radial distortion model for camera calibration is in fact an assumption or a restriction. In practice, camera distortion could happen in a general geometrical manner that is not limited to the radial sense. This paper proposes a simplified geometrical distortion modeling method by using two different radial distortion functions in the two image axes. A family of simplified geometric distortion models is proposed, which are either simple polynomials or the rational functions of polynomials. Analytical geometric undistortion is possible using two of the distortion functions discussed in this paper and their performance can be improved by applying a piecewise fitting idea. Our experimental results show that the geometrical distortion models always perform better than their radial distortion counterparts. Furthermore, the proposed geometric modeling method is more appropriate for cameras whose distortion is not perfectly radially symmetric around the center of distortion.


title: DPG: A Cache-Efficient Accelerator for Sorting and for Join Operators

abstract: We present a new algorithm for fast record retrieval, distribute-probe-gather, or DPG. DPG has important applications both in sorting and in joins. Current main memory sorting algorithms split their work into three phases: extraction of key-pointer pairs; sorting of the key-pointer pairs; and copying of the original records into the destination array according the sorted key-pointer pairs. The copying in the last phase dominates today's sorting time. Hence, the use of DPG in the third phase provides an accelerator for existing sorting algorithms. DPG also provides two new join methods for foreign key joins: DPG-move join and DPG-sort join. The resulting join methods with DPG are faster because DPG join is cache-efficient and at the same time DPG join avoids the need for sorting or for hashing. The ideas presented for foreign key join can also be extended to faster record pair retrieval for spatial and temporal databases.


title: Disabled Access for Museum Websites

abstract: Physical disabled access is something that most museums consider very seriously. Indeed, there are normally legal requirements to do so. However, online disabled access is still a relatively novel field. Most museums have not yet considered the issues in depth. The Human-Computer Interface for their websites is normally tested with major browsers, but not with specialist browsers or against the relevant accessibility and validation standards. We consider the current state of the art in this area and mention an accessibility survey of some museum websites.


title: Higher-Dimensional Packing with Order Constraints

abstract: We present a first exact study on higher-dimensional packing problems with order constraints. Problems of this type occur naturally in applications such as logistics or computer architecture and can be interpreted as higher-dimensional generalizations of scheduling problems. Using graph-theoretic structures to describe feasible solutions, we develop a novel exact branch-and-bound algorithm. This extends previous work by Fekete and Schepers; a key tool is a new order-theoretic characterization of feasible extensions of a partial order to a given complementarity graph that is tailor-made for use in a branch-and-bound environment. The usefulness of our approach is validated by computational results.


title: On Applying Or-Parallelism and Tabling to Logic Programs

abstract: The past years have seen widening efforts at increasing Prolog's declarativeness and expressiveness. Tabling has proved to be a viable technique to efficiently overcome SLD's susceptibility to infinite loops and redundant subcomputations. Our research demonstrates that implicit or-parallelism is a natural fit for logic programs with tabling. To substantiate this belief, we have designed and implemented an or-parallel tabling engine -- OPTYap -- and we used a shared-memory parallel machine to evaluate its performance. To the best of our knowledge, OPTYap is the first implementation of a parallel tabling engine for logic programming systems. OPTYap builds on Yap's efficient sequential Prolog engine. Its execution model is based on the SLG-WAM for tabling, and on the environment copying for or-parallelism. Preliminary results indicate that the mechanisms proposed to parallelize search in the context of SLD resolution can indeed be effectively and naturally generalized to parallelize tabled computations, and that the resulting systems can achieve good performance on shared-memory parallel machines. More importantly, it emphasizes our belief that through applying or-parallelism and tabling to logic programs the range of applications for Logic Programming can be increased.


title: A Grid Based Architecture for High-Performance NLP

abstract: We describe the design and early implementation of an extensible, component-based software architecture for natural language engineering applications which interfaces with high performance distributed computing services. The architecture leverages existing linguistic resource description and discovery mechanisms based on metadata descriptions, combining these in a compatible fashion with other software definition abstractions. Within this architecture, application design is highly flexible, allowing disparate components to be combined to suit the overall application functionality, and formally described independently of processing concerns. An application specification language provides abstraction from the programming environment and allows ease of interface with high performance computational grids via a broker.


title: The Generalized Riemann or Henstock Integral Underpinning Multivariate Data Analysis: Application to Faint Structure Finding in Price Processes

abstract: Practical data analysis involves many implicit or explicit assumptions about the good behavior of the data, and excludes consideration of various potentially pathological or limit cases. In this work, we present a new general theory of data, and of data processing, to bypass some of these assumptions. The new framework presented is focused on integration, and has direct applicability to expectation, distance, correlation, and aggregation. In a case study, we seek to reveal faint structure in financial data. Our new foundation for data encoding and handling offers increased justification for our conclusions.


title: On the probabilistic approach to the random satisfiability problem

abstract: In this note I will review some of the recent results that have been obtained in the probabilistic approach to the random satisfiability problem. At the present moment the results are only heuristic. In the case of the random 3-satisfiability problem a phase transition from the satisfiable to the unsatisfiable phase is found at $\alpha=4.267$. There are other values of $\alpha$ that separates different regimes and they will be described in details. In this context the properties of the survey decimation algorithm will also be discussed.


title: Short Cycles Connectivity

abstract: Short cycles connectivity is a generalization of ordinary connectivity. Instead by a path (sequence of edges), two vertices have to be connected by a sequence of short cycles, in which two adjacent cycles have at least one common vertex. If all adjacent cycles in the sequence share at least one edge, we talk about edge short cycles connectivity. It is shown that the short cycles connectivity is an equivalence relation on the set of vertices, while the edge short cycles connectivity components determine an equivalence relation on the set of edges. Efficient algorithms for determining equivalence classes are presented. Short cycles connectivity can be extended to directed graphs (cyclic and transitive connectivity). For further generalization we can also consider connectivity by small cliques or other families of graphs.


title: Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations

abstract: We show that constant-depth Frege systems with counting axioms modulo $m$ polynomially simulate Nullstellensatz refutations modulo $m$. Central to this is a new definition of reducibility from formulas to systems of polynomials with the property that, for most previously studied translations of formulas to systems of polynomials, a formula reduces to its translation. When combined with a previous result of the authors, this establishes the first size separation between Nullstellensatz and polynomial calculus refutations. We also obtain new, small refutations for certain CNFs by constant-depth Frege systems with counting axioms.


title: A Robust and Computational Characterisation of Peer-to-Peer Database Systems

abstract: In this paper we give a robust logical and computational characterisation of peer-to-peer database systems. We first define a pre- cise model-theoretic semantics of a peer-to-peer system, which allows for local inconsistency handling. We then characterise the general computa- tional properties for the problem of answering queries to such a peer-to- peer system. Finally, we devise tight complexity bounds and distributed procedures for the problem of answering queries in few relevant special cases.


title: On the expressive power of semijoin queries

abstract: The semijoin algebra is the variant of the relational algebra obtained by replacing the join operator by the semijoin operator. We provide an Ehrenfeucht-Fraiss\'{e} game, characterizing the discerning power of the semijoin algebra. This game gives a method for showing that queries are not expressible in the semijoin algebra.


title: Rethinking OpenPGP PKI and OpenPGP Public Keyserver

abstract: OpenPGP, an IETF Proposed Standard based on PGP application, has its own Public Key Infrastructure (PKI) architecture which is different from the one based on X.509, another standard from ITU. This paper describes the OpenPGP PKI; the historical perspective as well as its current use. The current OpenPGP PKI issues include the capability of a PGP keyserver and its performance. PGP keyservers have been developed and operated by volunteers since the 1990s. The keyservers distribute, merge, and expire the OpenPGP public keys. Major keyserver managers from several countries have built the globally distributed network of PGP keyservers. However, the current PGP Public Keyserver (pksd) has some limitations. It does not support fully the OpenPGP format so that it is neither expandable nor flexible, without any cluster technology. Finally we introduce the project on the next generation OpenPGP public keyserver called the OpenPKSD, lead by Hironobu Suzuki, one of the authors, and funded by Japanese Information-technology Promotion Agency(IPA).


title: Collaborative Creation of Digital Content in Indian Languages

abstract: The world is passing through a major revolution called the information revolution, in which information and knowledge is becoming available to people in unprecedented amounts wherever and whenever they need it. Those societies which fail to take advantage of the new technology will be left behind, just like in the industrial revolution. The information revolution is based on two major technologies: computers and communication. These technologies have to be delivered in a COST EFFECTIVE manner, and in LANGUAGES accessible to people. One way to deliver them in cost effective manner is to make suitable technology choices, and to allow people to access through shared resources. This could be done throuch street corner shops (for computer usage, e-mail etc.), schools, community centres and local library centres.


title: Information Revolution

abstract: The world is passing through a major revolution called the information revolution, in which information and knowledge is becoming available to people in unprecedented amounts wherever and whenever they need it. Those societies which fail to take advantage of the new technology will be left behind, just like in the industrial revolution. The information revolution is based on two major technologies: computers and communication. These technologies have to be delivered in a COST EFFECTIVE manner, and in LANGUAGES accessible to people. One way to deliver them in cost effective manner is to make suitable technology choices (discussed later), and to allow people to access through shared resources. This could be done throuch street corner shops (for computer usage, e-mail etc.), schools, community centers and local library centres.


title: Anusaaraka: Overcoming the Language Barrier in India

abstract: The anusaaraka system makes text in one Indian language accessible in another Indian language. In the anusaaraka approach, the load is so divided between man and computer that the language load is taken by the machine, and the interpretation of the text is left to the man. The machine presents an image of the source text in a language close to the target language.In the image, some constructions of the source language (which do not have equivalents) spill over to the output. Some special notation is also devised. The user after some training learns to read and understand the output. Because the Indian languages are close, the learning time of the output language is short, and is expected to be around 2 weeks. The output can also be post-edited by a trained user to make it grammatically correct in the target language. Style can also be changed, if necessary. Thus, in this scenario, it can function as a human assisted translation system. Currently, anusaarakas are being built from Telugu, Kannada, Marathi, Bengali and Punjabi to Hindi. They can be built for all Indian languages in the near future. Everybody must pitch in to build such systems connecting all Indian languages, using the free software model.


title: Language Access: An Information Based Approach

abstract: The anusaaraka system (a kind of machine translation system) makes text in one Indian language accessible through another Indian language. The machine presents an image of the source text in a language close to the target language. In the image, some constructions of the source language (which do not have equivalents in the target language) spill over to the output. Some special notation is also devised. Anusaarakas have been built from five pairs of languages: Telugu,Kannada, Marathi, Bengali and Punjabi to Hindi. They are available for use through Email servers. Anusaarkas follows the principle of substitutibility and reversibility of strings produced. This implies preservation of information while going from a source language to a target language. For narrow subject areas, specialized modules can be built by putting subject domain knowledge into the system, which produce good quality grammatical output. However, it should be remembered, that such modules will work only in narrow areas, and will sometimes go wrong. In such a situation, anusaaraka output will still remain useful.


title: LERIL : Collaborative Effort for Creating Lexical Resources

abstract: The paper reports on efforts taken to create lexical resources pertaining to Indian languages, using the collaborative model. The lexical resources being developed are: (1) Transfer lexicon and grammar from English to several Indian languages. (2) Dependencey tree bank of annotated corpora for several Indian languages. The dependency trees are based on the Paninian model. (3) Bilingual dictionary of 'core meanings'.


title: A Bernstein-Bezier Sufficient Condition for Invertibility of Polynomial Mapping Functions

abstract: We propose a sufficient condition for invertibility of a polynomial mapping function defined on a cube or simplex. This condition is applicable to finite element analysis using curved meshes. The sufficient condition is based on an analysis of the Bernstein-B\'ezier form of the columns of the derivative.


title: Extending Dublin Core Metadata to Support the Description and Discovery of Language Resources

abstract: As language data and associated technologies proliferate and as the language resources community expands, it is becoming increasingly difficult to locate and reuse existing resources. Are there any lexical resources for such-and-such a language? What tool works with transcripts in this particular format? What is a good format to use for linguistic data of this type? Questions like these dominate many mailing lists, since web search engines are an unreliable way to find language resources. This paper reports on a new digital infrastructure for discovering language resources being developed by the Open Language Archives Community (OLAC). At the core of OLAC is its metadata format, which is designed to facilitate description and discovery of all kinds of language resources, including data, tools, or advice. The paper describes OLAC metadata, its relationship to Dublin Core metadata, and its dissemination using the metadata harvesting protocol of the Open Archives Initiative.


title: On the complexity of curve fitting algorithms

abstract: We study a popular algorithm for fitting polynomial curves to scattered data based on the least squares with gradient weights. We show that sometimes this algorithm admits a substantial reduction of complexity, and, furthermore, find precise conditions under which this is possible. It turns out that this is, indeed, possible when one fits circles but not ellipses or hyperbolas.


title: Relational Grid Monitoring Architecture (R-GMA)

abstract: We describe R-GMA (Relational Grid Monitoring Architecture) which has been developed within the European DataGrid Project as a Grid Information and Monitoring System. Is is based on the GMA from GGF, which is a simple Consumer-Producer model. The special strength of this implementation comes from the power of the relational model. We offer a global view of the information as if each Virtual Organisation had one large relational database. We provide a number of different Producer types with different characteristics; for example some support streaming of information. We also provide combined Consumer/Producers, which are able to combine information and republish it. At the heart of the system is the mediator, which for any query is able to find and connect to the best Producers for the job. We have developed components to allow a measure of inter-working between MDS and R-GMA. We have used it both for information about the grid (primarily to find out about what services are available at any one time) and for application monitoring. R-GMA has been deployed in various testbeds; we describe some preliminary results and experiences of this deployment.


title: Controlled hierarchical filtering: Model of neocortical sensory processing

abstract: A model of sensory information processing is presented. The model assumes that learning of internal (hidden) generative models, which can predict the future and evaluate the precision of that prediction, is of central importance for information extraction. Furthermore, the model makes a bridge to goal-oriented systems and builds upon the structural similarity between the architecture of a robust controller and that of the hippocampal entorhinal loop. This generative control architecture is mapped to the neocortex and to the hippocampal entorhinal loop. Implicit memory phenomena; priming and prototype learning are emerging features of the model. Mathematical theorems ensure stability and attractive learning properties of the architecture. Connections to reinforcement learning are also established: both the control network, and the network with a hidden model converge to (near) optimal policy under suitable conditions. Falsifying predictions, including the role of the feedback connections between neocortical areas are made.


title: Improvements to time bracketed authentication

abstract: We describe a collection of techniques whereby audiovisual or other recordings of significant events can be made in a way that hinders falsification, pre-dating, or post-dating by interested parties, even by the makers and operators of the recording equipment. A central feature of these techniques is the interplay between private information, which by its nature is untrustworthy and susceptible to suppression or manipulation by interested parties, and public information, which is too widely known to be manipulated by anyone. While authenticated recordings may be infeasible to falsify, they can be abused in other ways, such as being used for blackmail or harassment; but susceptibility to these abuses can be reduced by encryption and secret sharing.


title: A Comparison of Secret Sharing Schemes Based on Latin Squares and RSA

abstract: In recent years there has been a great deal of work done on secret sharing scehemes. Secret Sharing Schemes allow for the division of keys so that an authorised set of users may access information. In this paper we wish to present a critical comparison of two of these schemes based on Latin Squares, [Cooper et., al.] and RSA [Shoup]. These two protocols will be examined in terms of their positive and negative aspects of their secuirty.


title: Finding Traitors in Secure Networks Using Byzantine Agreements

abstract: Secure networks rely upon players to maintain security and reliability. However not every player can be assumed to have total loyalty and one must use methods to uncover traitors in such networks. We use the original concept of the Byzantine Generals Problem by Lamport, and the more formal Byzantine Agreement describe by Linial, to nd traitors in secure networks. By applying general fault-tolerance methods to develop a more formal design of secure networks we are able to uncover traitors amongst a group of players. We also propose methods to integrate this system with insecure channels. This new resiliency can be applied to broadcast and peer-to-peer secure communication systems where agents may be traitors or become unreliable due to faults.


title: On Decidability of Expressive Description Logics with Composition of Roles in Number Restrictions

abstract: Description Logics are knowledge representation formalisms which have been used in a wide range of application domains. Owing to their appealing expressiveness, we consider in this paper extensions of the well-known concept language ALC allowing for number restrictions on complex role expressions. These have been first introduced by Baader and Sattler as ALCN(M) languages, with the adoption of role constructors M subset-of {o,-,And,Or}. In particular, they showed in 1999 that, although ALCN(o) is decidable, the addition of other operators may easily lead to undecidability: in fact, ALCN(o,And) and ALCN(o,-,Or) were proved undecidable. In this work, we further investigate the computational properties of the ALCN family, aiming at narrowing the decidability gap left open by Baader and Sattler's results. In particular, we will show that ALCN(o) extended with inverse roles both in number and in value restrictions becomes undecidable, whereas it can be safely extended with qualified number restrictions without losing decidability.


title: Learning in Multiagent Systems: An Introduction from a Game-Theoretic Perspective

abstract: We introduce the topic of learning in multiagent systems. We first provide a quick introduction to the field of game theory, focusing on the equilibrium concepts of iterated dominance, and Nash equilibrium. We show some of the most relevant findings in the theory of learning in games, including theorems on fictitious play, replicator dynamics, and evolutionary stable strategies. The CLRI theory and n-level learning agents are introduced as attempts to apply some of these findings to the problem of engineering multiagent systems with learning agents. Finally, we summarize some of the remaining challenges in the field of learning in multiagent systems.


title: Artificial Neural Networks for Beginners

abstract: The scope of this teaching package is to make a brief induction to Artificial Neural Networks (ANNs) for people who have no previous knowledge of them. We first make a brief introduction to models of networks, for then describing in general terms ANNs. As an application, we explain the backpropagation algorithm, since it is widely used and many other algorithms are derived from it. The user should know algebra and the handling of functions and vectors. Differential calculus is recommendable, but not necessary. The contents of this package should be understood by people with high school education. It would be useful for people who are just curious about what are ANNs, or for people who want to become familiar with them, so when they study them more fully, they will already have clear notions of ANNs. Also, people who only want to apply the backpropagation algorithm without a detailed and formal explanation of it will find this material useful. This work should not be seen as "Nets for dummies", but of course it is not a treatise. Much of the formality is skipped for the sake of simplicity. Detailed explanations and demonstrations can be found in the referred readings. The included exercises complement the understanding of the theory. The on-line resources are highly recommended for extending this brief induction.


title: Evaluation of text data mining for database curation: lessons learned from the KDD Challenge Cup

abstract: MOTIVATION: The biological literature is a major repository of knowledge. Many biological databases draw much of their content from a careful curation of this literature. However, as the volume of literature increases, the burden of curation increases. Text mining may provide useful tools to assist in the curation process. To date, the lack of standards has made it impossible to determine whether text mining techniques are sufficiently mature to be useful. RESULTS: We report on a Challenge Evaluation task that we created for the Knowledge Discovery and Data Mining (KDD) Challenge Cup. We provided a training corpus of 862 articles consisting of journal articles curated in FlyBase, along with the associated lists of genes and gene products, as well as the relevant data fields from FlyBase. For the test, we provided a corpus of 213 new (`blind') articles; the 18 participating groups provided systems that flagged articles for curation, based on whether the article contained experimental evidence for gene expression products. We report on the the evaluation results and describe the techniques used by the top performing groups. CONTACT: asy@mitre.org KEYWORDS: text mining, evaluation, curation, genomics, data management


title: Coherent Keyphrase Extraction via Web Mining

abstract: Keyphrases are useful for a variety of purposes, including summarizing, indexing, labeling, categorizing, clustering, highlighting, browsing, and searching. The task of automatic keyphrase extraction is to select keyphrases from within the text of a given document. Automatic keyphrase extraction makes it feasible to generate keyphrases for the huge number of documents that do not have manually assigned keyphrases. A limitation of previous keyphrase extraction algorithms is that the selected keyphrases are occasionally incoherent. That is, the majority of the output keyphrases may fit together well, but there may be a minority that appear to be outliers, with no clear semantic relation to the majority or to each other. This paper presents enhancements to the Kea keyphrase extraction algorithm that are designed to increase the coherence of the extracted keyphrases. The approach is to use the degree of statistical association among candidate keyphrases as evidence that they may be semantically related. The statistical association is measured using web mining. Experiments demonstrate that the enhancements improve the quality of the extracted keyphrases. Furthermore, the enhancements are not domain-specific: the algorithm generalizes well when it is trained on one domain (computer science documents) and tested on another (physics documents).


title: Fingerprint based bio-starter and bio-access

abstract: In the paper will be presented a safety and security system based on fingerprint technology. The results suggest a new scenario where the new cars can use a fingerprint sensor integrated in car handle to allow access and in the dashboard as starter button.


title: IS (Iris Security)

abstract: In the paper will be presented a safety system based on iridology. The results suggest a new scenario where the security problem in supervised and unsupervised areas can be treat with the present system and the iris image recognition.


title: The Rich-Club Phenomenon In The Internet Topology

abstract: We show that the Internet topology at the Autonomous System (AS) level has a rich--club phenomenon. The rich nodes, which are a small number of nodes with large numbers of links, are very well connected to each other. The rich--club is a core tier that we measured using the rich--club connectivity and the node--node link distribution. We obtained this core tier without any heuristic assumption between the ASes. The rich--club phenomenon is a simple qualitative way to differentiate between power law topologies and provides a criterion for new network models. To show this, we compared the measured rich--club of the AS graph with networks obtained using the Barab\'asi--Albert (BA) scale--free network model, the Fitness BA model and the Inet--3.0 model.


title: Distributed and Parallel Net Imaging

abstract: A very complex vision system is developed to detect luminosity variations connected with the discovery of new planets in the Universe. The traditional imaging system can not manage a so large load. A private net is implemented to perform an automatic vision and decision architecture. It lets to carry out an on-line discrimination of interesting events by using two levels of triggers. This system can even manage many Tbytes of data per day. The architecture avails itself of a distributed parallel network system based on a maximum of 256 standard workstations with Microsoft Window as OS.


title: Image Analysis in Astronomy for very large vision machine

abstract: It is developed a very complex system (hardware/software) to detect luminosity variations connected with the discovery of new planets outside the Solar System. Traditional imaging approaches are very demanding in terms of computing time; then, the implementation of an automatic vision and decision software architecture is presented. It allows to perform an on-line discrimination of interesting events by using two levels of triggers. A fundamental challenge was to work with very large CCD camera (even 16k*16k pixels) in line with very large telescopes. Then, the architecture can use a distributed parallel network system based on a maximum of 256 standard workstations.


title: A new approach to relevancy in Internet searching - the "Vox Populi Algorithm"

abstract: In this paper we will derive a new algorithm for Internet searching. The main idea of this algorithm is to extend the existing algorithms by a component, which reflects the interests of the users more than existing methods. The "Vox Populi Algorithm" (VPA) creates a feedback from the users to the content of the search index. The information derived from the users query analysis is used to modify the existing crawling algorithms. The VPA controls the distribution of the resources of the crawler. Finally, we also discuss methods of suppressing unwanted content (spam).


title: Open source software and peer review

abstract: We compare the open source model of software development to peer review in academia.


title: Static Data Structure for Discrete Advance Bandwidth Reservations on the Internet

abstract: In this paper we present a discrete data structure for reservations of limited resources. A reservation is defined as a tuple consisting of the time interval of when the resource should be reserved, $I_R$, and the amount of the resource that is reserved, $B_R$, formally $R=\{I_R,B_R\}$. The data structure is similar to a segment tree. The maximum spanning interval of the data structure is fixed and defined in advance. The granularity and thereby the size of the intervals of the leaves is also defined in advance. The data structure is built only once. Neither nodes nor leaves are ever inserted, deleted or moved. Hence, the running time of the operations does not depend on the number of reservations previously made. The running time does not depend on the size of the interval of the reservation either. Let $n$ be the number of leaves in the data structure. In the worst case, the number of touched (i.e. traversed) nodes is in any operation $O(\log n)$, hence the running time of any operation is also $O(\log n)$.


title: Centralized reward system gives rise to fast and efficient work sharing for intelligent Internet agents lacking direct communication

abstract: WWW has a scale-free structure where novel information is often difficult to locate. Moreover, Intelligent agents easily get trapped in this structure. Here a novel method is put forth, which turns these traps into information repositories, supplies: We populated an Internet environment with intelligent news foragers. Foraging has its associated cost whereas foragers are rewarded if they detect not yet discovered novel information. The intelligent news foragers crawl by using the estimated long-term cumulated reward, and also have a finite sized memory: the list of most promising supplies. Foragers form an artificial life community: the most successful ones are allowed to multiply, while unsuccessful ones die out. The specific property of this community is that there is no direct communication amongst foragers but the centralized rewarding system. Still, fast division of work is achieved.


title: Note on Needle in a Haystack

abstract: Introduced below is a quantum database method, not only for retrieval but also for creation. It uses a particular structure of true's and false's in a state vector of n qubits, permitting up to 2**2**n words, vastly more than for classical bits. Several copies are produced so that later they can be destructively observed and a word determined with high probability. Grover's algorithm is proposed below to read out, nondestructively the unknown contents of a given stored state vector using only one state vector.


title: EqRank: A Self-Consistent Equivalence Relation on Graph Vertexes

abstract: A new method of hierarchical clustering of graph vertexes is suggested. In the method, the graph partition is determined with an equivalence relation satisfying a recursive definition stating that vertexes are equivalent if the vertexes they point to (or vertexes pointing to them) are equivalent. Iterative application of the partitioning yields a hierarchical clustering of graph vertexes. The method is applied to the citation graph of hep-th. The outcome is a two-level classification scheme for the subject field presented in hep-th, and indexing of the papers from hep-th in this scheme. A number of tests show that the classification obtained is adequate.


title: Media Affordances of a Mobile Push-To-Talk Communication Service

abstract: This paper presents an exploratory study of college-age students using two-way, push-to-talk cellular radios. We describe the observed and reported use of cellular radio by the participants, the activities and purposes for which they adopted it, and their responses. We then examine these empirical results using mediated communication theory. Cellular radios have a unique combination of affordances relative to other media used by this age group, including instant messaging (IM) and mobile phones; the results of our analysis do suggest explanations for some observed phenomena but also highlight the counter-intuitive nature of other phenomena. For example, although the radios have many important dissimilarities with IM from the viewpoint of mediated communication theory, the observed use patterns resembled those of IM to a surprising degree.


title: El informe NERA analizado

abstract: This is a review of the article "Government Preferences for Promoting Open-Source Software: A Solution in Search of A Problem" by David Evans and Bernard J. Reddy. This report was paid for by Microsoft and put together at its request. Now Microsoft is using it as part of their lobbying campaign in Europe against governments' promotion of Open Source Software. As expected, this article is strongly biased and most of the conclusions are based upon false hypotheses and evidence.


title: Model Checking Linear Logic Specifications

abstract: The overall goal of this paper is to investigate the theoretical foundations of algorithmic verification techniques for first order linear logic specifications. The fragment of linear logic we consider in this paper is based on the linear logic programming language called LO enriched with universally quantified goal formulas. Although LO was originally introduced as a theoretical foundation for extensions of logic programming languages, it can also be viewed as a very general language to specify a wide range of infinite-state concurrent systems. Our approach is based on the relation between backward reachability and provability highlighted in our previous work on propositional LO programs. Following this line of research, we define here a general framework for the bottom-up evaluation of first order linear logic specifications. The evaluation procedure is based on an effective fixpoint operator working on a symbolic representation of infinite collections of first order linear logic formulas. The theory of well quasi-orderings can be used to provide sufficient conditions for the termination of the evaluation of non trivial fragments of first order linear logic.


title: The Structure of Information

abstract: A formal model of the structure of information is presented in five axioms which define identity, containment, and joins of infons. Joins are shown to be commutative, associative, provide inverses of infons, and, potentially, have many identity elements, two of which are multiplicative and additive. Those two types of join are distributive. The other identity elements are for operators on entwined states. Multiplicative joins correspond to adding or removing new bits to a system while additive joins correspond to a change of state. The order or size of an infon is defined. This groundwork is intended to be used to model continuous and discreet information structures through time, especially in closed systems.


title: Indexing Schemes for Similarity Search In Datasets of Short Protein Fragments

abstract: We propose a family of very efficient hierarchical indexing schemes for ungapped, score matrix-based similarity search in large datasets of short (4-12 amino acid) protein fragments. This type of similarity search has importance in both providing a building block to more complex algorithms and for possible use in direct biological investigations where datasets are of the order of 60 million objects. Our scheme is based on the internal geometry of the amino acid alphabet and performs exceptionally well, for example outputting 100 nearest neighbours to any possible fragment of length 10 after scanning on average less than one per cent of the entire dataset.


title: The KR-Benes Network: A Control-Optimal Rearrangeable Permutation Network

abstract: The Benes network has been used as a rearrangeable network for over 40 years, yet the uniform $N(2 \log N-1)$ control complexity of the $N \times N$ Benes is not optimal for many permutations. In this paper, we present a novel $O(\log N)$ depth rearrangeable network called KR-Benes that is {\it permutation-specific control-optimal}. The KR-Benes routes {\it every} permutation with the minimal control complexity {\it specific} to that permutation and its worst-case complexity for arbitrary permutations is bounded by the Benes; thus it replaces the Benes when considering control complexity/latency. We design the KR-Benes by first constructing a restricted $2 \log K +2$ depth rearrangeable network called $K$-Benes for routing $K$-bounded permutations with control $2N \log K$, $0 \leq K \leq N/4$. We then show that the $N \times N$ Benes network itself (with one additional stage) contains every $K$-Benes network as a subgraph and use this property to construct the KR-Benes network. With regard to the control-optimality of the KR-Benes, we show that any optimal network for rearrangeably routing $K$-bounded permutations must have depth $2 \log K + 2$, and therefore the $K$-Benes (and hence the KR-Benes) is optimal.


title: ROC Curves Within the Framework of Neural Network Assembly Memory Model: Some Analytic Results

abstract: On the basis of convolutional (Hamming) version of recent Neural Network Assembly Memory Model (NNAMM) for intact two-layer autoassociative Hopfield network optimal receiver operating characteristics (ROCs) have been derived analytically. A method of taking into account explicitly a priori probabilities of alternative hypotheses on the structure of information initiating memory trace retrieval and modified ROCs (mROCs, a posteriori probabilities of correct recall vs. false alarm probability) are introduced. The comparison of empirical and calculated ROCs (or mROCs) demonstrates that they coincide quantitatively and in this way intensities of cues used in appropriate experiments may be estimated. It has been found that basic ROC properties which are one of experimental findings underpinning dual-process models of recognition memory can be explained within our one-factor NNAMM.


title: Digital Version of Green`s Theorem and its Application to The Coverage Problem in Formal Verification

abstract: We present a novel scheme to the coverage problem, introducing a quantitative way to estimate the interaction between a block and its enviroment.This is achieved by setting a discrete version of Green`s theorem, specially adapted for Model Checking based verification of integrated circuits.This method is best suited for the coverage problem since it enables one to quantify the incompleteness or, on the other hand, the redundancy of a set of rules, describing the model under verification.Moreover this can be done continuously throughout the verification process, thus enabling the user to pinpoint the stages at which incompleteness/redundancy occurs. Although the method is presented locally on a small hardware example, we additionally show its possibility to provide precise coverage estimation also for large scale systems. We compare this method to others by checking it on the same test-cases.


title: What Is Working Memory and Mental Imagery? A Robot that Learns to Perform Mental Computations

abstract: This paper goes back to Turing (1936) and treats his machine as a cognitive model (W,D,B), where W is an "external world" represented by memory device (the tape divided into squares), and (D,B) is a simple robot that consists of the sensory-motor devices, D, and the brain, B. The robot's sensory-motor devices (the "eye", the "hand", and the "organ of speech") allow the robot to simulate the work of any Turing machine. The robot simulates the internal states of a Turing machine by "talking to itself." At the stage of training, the teacher forces the robot (by acting directly on its motor centers) to perform several examples of an algorithm with different input data presented on tape. Two effects are achieved: 1) The robot learns to perform the shown algorithm with any input data using the tape. 2) The robot learns to perform the algorithm "mentally" using an "imaginary tape." The model illustrates the simplest concept of a universal learning neurocomputer, demonstrates universality of associative learning as the mechanism of programming, and provides a simplified, but nontrivial neurobiologically plausible explanation of the phenomena of working memory and mental imagery. The model is implemented as a user-friendly program for Windows called EROBOT. The program is available at www.brain0.com/software.html.


title: Homomorphic public-key cryptosystems over groups and rings

abstract: We propose a new homomorphic public-key cryptosystem over arbitrary nonidentity finite group based on the difficulty of the membership problem for groups of integer matrices. Besides, a homomorphic cryptosystem is designed for the first time over finite commutative rings.


title: Indexing of Tables Referencing Complex Structures

abstract: We introduce indexing of tables referencing complex structures such as digraphs and spatial objects, appearing in genetics and other data intensive analysis. The indexing is achieved by extracting dimension schemas from the referenced structures. The schemas and their dimensionality are determined by proper coloring algorithms and the duality between all such schemas and all such possible proper colorings is established. This duality, in turn, provides us with an extensive library of solutions when addressing indexing questions. It is illustrated how to use the schemas, in connection with additional relational database technologies, to optimize queries conditioned on the structural information being referenced. Comparisons using bitmap indexing in the Oracle 9.2i database, on the one hand, and multidimensional clustering in DB2 8.1.2, on the other hand, are used to illustrate the applicability of the indexing to different technology settings. Finally, we illustrate how the indexing can be used to extract low dimensional schemas from a binary interval tree in order to resolve efficiently interval and stabbing queries.


title: Exploration of RNA Editing and Design of Robust Genetic Algorithms

abstract: This paper presents our computational methodology using Genetic Algorithms (GA) for exploring the nature of RNA editing. These models are constructed using several genetic editing characteristics that are gleaned from the RNA editing system as observed in several organisms. We have expanded the traditional Genetic Algorithm with artificial editing mechanisms as proposed by (Rocha, 1997). The incorporation of editing mechanisms provides a means for artificial agents with genetic descriptions to gain greater phenotypic plasticity, which may be environmentally regulated. Our first implementations of these ideas have shed some light into the evolutionary implications of RNA editing. Based on these understandings, we demonstrate how to select proper RNA editors for designing more robust GAs, and the results will show promising applications to real-world problems. We expect that the framework proposed will both facilitate determining the evolutionary role of RNA editing in biology, and advance the current state of research in Genetic Algorithms.


title: Semi-metric Behavior in Document Networks and its Application to Recommendation Systems

abstract: Recommendation systems for different Document Networks (DN) such as the World Wide Web (WWW) and Digital Libraries, often use distance functions extracted from relationships among documents and keywords. For instance, documents in the WWW are related via a hyperlink network, while documents in bibliographic databases are related by citation and collaboration networks. Furthermore, documents are related to keyterms. The distance functions computed from these relations establish associative networks among items of the DN, referred to as Distance Graphs, which allow recommendation systems to identify relevant associations for individual users. However, modern recommendation systems need to integrate associative data from multiple sources such as different databases, web sites, and even other users. Thus, we are presented with a problem of combining evidence (about associations between items) from different sources characterized by distance functions. In this paper we describe our work on (1) inferring relevant associations from, as well as characterizing, semi-metric distance graphs and (2) combining evidence from different distance graphs in a recommendation system. Regarding (1), we present the idea of semi-metric distance graphs, and introduce ratios to measure semi-metric behavior. We compute these ratios for several DN such as digital libraries and web sites and show that they are useful to identify implicit associations. Regarding (2), we describe an algorithm to combine evidence from distance graphs that uses Evidence Sets, a set structure based on Interval Valued Fuzzy Sets and Dempster-Shafer Theory of Evidence. This algorithm has been developed for a recommendation system named TalkMine.

categories: cs.IR cond-mat.dis-nn cond-mat.stat-mech cs.AI cs.DL cs.HC cs.MA


title: Optimal Covering Tours with Turn Costs

abstract: We give the first algorithmic study of a class of ``covering tour'' problems related to the geometric Traveling Salesman Problem: Find a polygonal tour for a cutter so that it sweeps out a specified region (``pocket''), in order to minimize a cost that depends mainly on the number of em turns. These problems arise naturally in manufacturing applications of computational geometry to automatic tool path generation and automatic inspection systems, as well as arc routing (``postman'') problems with turn penalties. We prove the NP-completeness of minimum-turn milling and give efficient approximation algorithms for several natural versions of the problem, including a polynomial-time approximation scheme based on a novel adaptation of the m-guillotine method.


title: Reliable and Efficient Inference of Bayesian Networks from Sparse Data by Statistical Learning Theory

abstract: To learn (statistical) dependencies among random variables requires exponentially large sample size in the number of observed random variables if any arbitrary joint probability distribution can occur. We consider the case that sparse data strongly suggest that the probabilities can be described by a simple Bayesian network, i.e., by a graph with small in-degree \Delta. Then this simple law will also explain further data with high confidence. This is shown by calculating bounds on the VC dimension of the set of those probability measures that correspond to simple graphs. This allows to select networks by structural risk minimization and gives reliability bounds on the error of the estimated joint measure without (in contrast to a previous paper) any prior assumptions on the set of possible joint measures. The complexity for searching the optimal Bayesian networks of in-degree \Delta increases only polynomially in the number of random varibales for constant \Delta and the optimal joint measure associated with a given graph can be found by convex optimization.


title: Using Simulated Annealing to Calculate the Trembles of Trembling Hand Perfection

abstract: Within the literature on non-cooperative game theory, there have been a number of attempts to propose logorithms which will compute Nash equilibria. Rather than derive a new algorithm, this paper shows that the family of algorithms known as Markov chain Monte Carlo (MCMC) can be used to calculate Nash equilibria. MCMC is a type of Monte Carlo simulation that relies on Markov chains to ensure its regularity conditions. MCMC has been widely used throughout the statistics and optimization literature, where variants of this algorithm are known as simulated annealing. This paper shows that there is interesting connection between the trembles that underlie the functioning of this algorithm and the type of Nash refinement known as trembling hand perfection.


title: Enumerating planar locally finite Cayley graphs

abstract: We characterize the set of planar locally finite Cayley graphs, and give a finite representation of these graphs by a special kind of finite state automata called labeling schemes. As a result, we are able to enumerate and describe all planar locally finite Cayley graphs of a given degree. This analysis allows us to solve the problem of decision of the locally finite planarity for a word-problem-decidable presentation. Keywords: vertex-transitive, Cayley graph, planar graph, tiling, labeling scheme


title: Using Propagation for Solving Complex Arithmetic Constraints

abstract: Solving a system of nonlinear inequalities is an important problem for which conventional numerical analysis has no satisfactory method. With a box-consistency algorithm one can compute a cover for the solution set to arbitrarily close approximation. Because of difficulties in the use of propagation for complex arithmetic expressions, box consistency is computed with interval arithmetic. In this paper we present theorems that support a simple modification of propagation that allows complex arithmetic expressions to be handled efficiently. The version of box consistency that is obtained in this way is stronger than when interval arithmetic is used.


title: Building a Test Collection for Speech-Driven Web Retrieval

abstract: This paper describes a test collection (benchmark data) for retrieval systems driven by spoken queries. This collection was produced in the subtask of the NTCIR-3 Web retrieval task, which was performed in a TREC-style evaluation workshop. The search topics and document collection for the Web retrieval task were used to produce spoken queries and language models for speech recognition, respectively. We used this collection to evaluate the performance of our retrieval system. Experimental results showed that (a) the use of target documents for language modeling and (b) enhancement of the vocabulary size in speech recognition were effective in improving the system performance.


title: Threshold values of Random K-SAT from the cavity method

abstract: Using the cavity equations of \cite{mezard:parisi:zecchina:02,mezard:zecchina:02}, we derive the various threshold values for the number of clauses per variable of the random $K$-satisfiability problem, generalizing the previous results to $K \ge 4$. We also give an analytic solution of the equations, and some closed expressions for these thresholds, in an expansion around large $K$. The stability of the solution is also computed. For any $K$, the satisfiability threshold is found to be in the stable region of the solution, which adds further credit to the conjecture that this computation gives the exact satisfiability threshold.


title: A Cross-media Retrieval System for Lecture Videos

abstract: We propose a cross-media lecture-on-demand system, in which users can selectively view specific segments of lecture videos by submitting text queries. Users can easily formulate queries by using the textbook associated with a target lecture, even if they cannot come up with effective keywords. Our system extracts the audio track from a target lecture video, generates a transcription by large vocabulary continuous speech recognition, and produces a text index. Experimental results showed that by adapting speech recognition to the topic of the lecture, the recognition accuracy increased and the retrieval accuracy was comparable with that obtained by human transcription.


title: Proposed Specification of a Distributed XML-Query Network

abstract: W3C's XML-Query language offers a powerful instrument for information retrieval on XML repositories. This article describes an implementation of this retrieval in a real world's scenario. Distributed XML-Query processing reduces load on every single attending node to an acceptable level. The network allows every participant to control their computing load themselves. Furthermore XML-repositories may stay at the rights holder, so every Data-Provider can decide, whether to process critical queries or not. If Data-Providers keep redundant information, this distributed network improves reliability of information with duplicates removed.


title: Efficient Algorithms for Citation Network Analysis

abstract: In the paper very efficient, linear in number of arcs, algorithms for determining Hummon and Doreian's arc weights SPLC and SPNP in citation network are proposed, and some theoretical properties of these weights are presented. The nonacyclicity problem in citation networks is discussed. An approach to identify on the basis of arc weights an important small subnetwork is proposed and illustrated on the citation networks of SOM (self organizing maps) literature and US patents.


title: Results on the quantitative mu-calculus qMu

abstract: The mu-calculus is a powerful tool for specifying and verifying transition systems, including those with both demonic and angelic choice; its quantitative generalisation qMu extends that to probabilistic choice. We show that for a finite-state system the logical interpretation of qMu, via fixed-points in a domain of real-valued functions into [0,1], is equivalent to an operational interpretation given as a turn-based gambling game between two players. The logical interpretation provides direct access to axioms, laws and meta-theorems. The operational, game- based interpretation aids the intuition and continues in the more general context to provide a surprisingly practical specification tool. A corollary of our proofs is an extension of Everett's singly-nested games result in the finite turn-based case: we prove well-definedness of the minimax value, and existence of fixed memoriless strategies, for all qMu games/formulae, of arbitrary (including alternating) nesting structure.


title: Evidential Force Aggregation

abstract: In this paper we develop an evidential force aggregation method intended for classification of evidential intelligence into recognized force structures. We assume that the intelligence has already been partitioned into clusters and use the classification method individually in each cluster. The classification is based on a measure of fitness between template and fused intelligence that makes it possible to handle intelligence reports with multiple nonspecific and uncertain propositions. With this measure we can aggregate on a level-by-level basis, starting from general intelligence to achieve a complete force structure with recognized units on all hierarchical levels.


title: A thought experiment on Quantum Mechanics and Distributed Failure Detection

abstract: One of the biggest problems in current distributed systems is that presented by one machine attempting to determine the liveness of another in a timely manner. Unfortunately, the symptoms exhibited by a failed machine can also be the result of other causes, e.g., an overloaded machine or network which drops messages, making it impossible to detect a machine failure with cetainty until that machine recovers. This is a well understood problem and one which has led to a large body of research into failure suspectors: since it is not possible to detect a failure, the best one can do is suspect a failure and program accordingly. However, one machine's suspicions may not be the same as another's; therefore, these algorithms spend a considerable effort in ensuring a consistent view among all available machines of who is suspects of being failed. This paper describes a thought experiment on how quantum mechanics may be used to provide a failure detector that is guaranteed to give both accurate and instantaneous information about the liveness of machines, no matter the distances involved.


title: Proceedings of the Fifth International Workshop on Automated Debugging (AADEBUG 2003)

abstract: Over the past decades automated debugging has seen major achievements. However, as debugging is by necessity attached to particular programming paradigms, the results are scattered. To alleviate this problem, the Automated and Algorithmic Debugging workshop (AADEBUG for short) was organised in 1993 in Link"oping (Sweden). As this workshop proved to be successful, subsequent workshops have been organised in 1995 (Saint-Malo, France), 1997 (again in Link"oping, Sweden) and 2000 (Munich, Germany). In 2003, the workshop is organised in Ghent, Belgium, the proceedings of which you are reading right now.


title: cTI: A constraint-based termination inference tool for ISO-Prolog

abstract: We present cTI, the first system for universal left-termination inference of logic programs. Termination inference generalizes termination analysis and checking. Traditionally, a termination analyzer tries to prove that a given class of queries terminates. This class must be provided to the system, for instance by means of user annotations. Moreover, the analysis must be redone every time the class of queries of interest is updated. Termination inference, in contrast, requires neither user annotations nor recomputation. In this approach, terminating classes for all predicates are inferred at once. We describe the architecture of cTI and report an extensive experimental evaluation of the system covering many classical examples from the logic programming termination literature and several Prolog programs of respectable size and complexity.


title: Instrumenting self-modifying code

abstract: Adding small code snippets at key points to existing code fragments is called instrumentation. It is an established technique to debug certain otherwise hard to solve faults, such as memory management issues and data races. Dynamic instrumentation can already be used to analyse code which is loaded or even generated at run time.With the advent of environments such as the Java Virtual Machine with optimizing Just-In-Time compilers, a new obstacle arises: self-modifying code. In order to instrument this kind of code correctly, one must be able to detect modifications and adapt the instrumentation code accordingly, preferably without incurring a high penalty speedwise. In this paper we propose an innovative technique that uses the hardware page protection mechanism of modern processors to detect such modifications. We also show how an instrumentor can adapt the instrumented version depending on the kind of modificiations as well as an experimental evaluation of said techniques.


title: Model-Based Debugging using Multiple Abstract Models

abstract: This paper introduces an automatic debugging framework that relies on model-based reasoning techniques to locate faults in programs. In particular, model-based diagnosis, together with an abstract interpretation based conflict detection mechanism is used to derive diagnoses, which correspond to possible faults in programs. Design information and partial specifications are applied to guide a model revision process, which allows for automatic detection and correction of structural faults.


title: Timestamp Based Execution Control for C and Java Programs

abstract: Many programmers have had to deal with an overwritten variable resulting for example from an aliasing problem. The culprit is obviously the last write-access to that memory location before the manifestation of the bug. The usual technique for removing such bugs starts with the debugger by (1) finding the last write and (2) moving the control point of execution back to that time by re-executing the program from the beginning. We wish to automate this. Step (2) is easy if we can somehow mark the last write found in step (1) and control the execution-point to move it back to this time. In this paper we propose a new concept, position, that is, a point in the program execution trace, as needed for step (2) above. The position enables debuggers to automate the control of program execution to support common debugging activities. We have implemented position in C by modifying GCC and in Java with a bytecode transformer. Measurements show that position can be provided with an acceptable amount of overhead.


title: Towards declarative diagnosis of constraint programs over finite domains

abstract: The paper proposes a theoretical approach of the debugging of constraint programs based on a notion of explanation tree. The proposed approach is an attempt to adapt algorithmic debugging to constraint programming. In this theoretical framework for domain reduction, explanations are proof trees explaining value removals. These proof trees are defined by inductive definitions which express the removals of values as consequences of other value removals. Explanations may be considered as the essence of constraint programming. They are a declarative view of the computation trace. The diagnosis consists in locating an error in an explanation rooted by a symptom.


title: Lower bounds for predecessor searching in the cell probe model

abstract: We consider a fundamental problem in data structures, static predecessor searching: Given a subset S of size n from the universe [m], store S so that queries of the form "What is the predecessor of x in S?" can be answered efficiently. We study this problem in the cell probe model introduced by Yao. Recently, Beame and Fich obtained optimal bounds on the number of probes needed by any deterministic query scheme if the associated storage scheme uses only n^{O(1)} cells of word size (\log m)^{O(1)} bits. We give a new lower bound proof for this problem that matches the bounds of Beame and Fich. Our lower bound proof has the following advantages: it works for randomised query schemes too, while Beame and Fich's proof works for deterministic query schemes only. It also extends to `quantum address-only' query schemes that we define in this paper, and is simpler than Beame and Fich's proof. We prove our lower bound using the round elimination approach of Miltersen, Nisan, Safra and Wigderson. Using tools from information theory, we prove a strong round elimination lemma for communication complexity that enables us to obtain a tight lower bound for the predecessor problem. Our strong round elimination lemma also extends to quantum communication complexity. We also use our round elimination lemma to obtain a rounds versus communication tradeoff for the `greater-than' problem, improving on the tradeoff in Miltersen et al. We believe that our round elimination lemma is of independent interest and should have other applications.


title: Measuring Praise and Criticism: Inference of Semantic Orientation from Association

abstract: The evaluative character of a word is called its semantic orientation. Positive semantic orientation indicates praise (e.g., "honest", "intrepid") and negative semantic orientation indicates criticism (e.g., "disturbing", "superfluous"). Semantic orientation varies in both direction (positive or negative) and degree (mild to strong). An automated system for measuring semantic orientation would have application in text classification, text filtering, tracking opinions in online discussions, analysis of survey responses, and automated chat systems (chatbots). This paper introduces a method for inferring the semantic orientation of a word from its statistical association with a set of positive and negative paradigm words. Two instances of this approach are evaluated, based on two different statistical measures of word association: pointwise mutual information (PMI) and latent semantic analysis (LSA). The method is experimentally tested with 3,596 words (including adjectives, adverbs, nouns, and verbs) that have been manually labeled positive (1,614 words) and negative (1,982 words). The method attains an accuracy of 82.8% on the full test set, but the accuracy rises above 95% when the algorithm is allowed to abstain from classifying mild words.


title: Combining Independent Modules to Solve Multiple-choice Synonym and Analogy Problems

abstract: Existing statistical approaches to natural language problems are very coarse approximations to the true complexity of language processing. As such, no single technique will be best for all problem instances. Many researchers are examining ensemble methods that combine the output of successful, separately developed modules to create more accurate solutions. This paper examines three merging rules for combining probability distributions: the well known mixture rule, the logarithmic rule, and a novel product rule. These rules were applied with state-of-the-art results to two problems commonly used to assess human mastery of lexical semantics -- synonym questions and analogy questions. All three merging rules result in ensembles that are more accurate than any of their component modules. The differences among the three rules are not statistically significant, but it is suggestive that the popular mixture rule is not the best rule for either of the two problems.


title: A Neural Network Assembly Memory Model Based on an Optimal Binary Signal Detection Theory

abstract: A ternary/binary data coding algorithm and conditions under which Hopfield networks implement optimal convolutional or Hamming decoding algorithms has been described. Using the coding/decoding approach (an optimal Binary Signal Detection Theory, BSDT) introduced a Neural Network Assembly Memory Model (NNAMM) is built. The model provides optimal (the best) basic memory performance and demands the use of a new memory unit architecture with two-layer Hopfield network, N-channel time gate, auxiliary reference memory, and two nested feedback loops. NNAMM explicitly describes the dependence on time of a memory trace retrieval, gives a possibility of metamemory simulation, generalized knowledge representation, and distinct description of conscious and unconscious mental processes. A model of smallest inseparable part or an "atom" of consciousness is also defined. The NNAMM's neurobiological backgrounds and its applications to solving some interdisciplinary problems are shortly discussed. BSDT could implement the "best neural code" used in nervous tissues of animals and humans.


title: Postmortem Object Type Identification

abstract: This paper presents a novel technique for the automatic type identification of arbitrary memory objects from a memory dump. Our motivating application is debugging memory corruption problems in optimized, production systems -- a problem domain largely unserved by extant methodologies. We describe our algorithm as applicable to any typed language, and we discuss it with respect to the formidable obstacles posed by C. We describe the heuristics that we have developed to overcome these difficulties and achieve effective type identification on C-based systems. We further describe the implementation of our heuristics on one C-based system -- the Solaris operating system kernel -- and describe the extensions that we have added to the Solaris postmortem debugger to allow for postmortem type identification. We show that our implementation yields a sufficiently high rate of type identification to be useful for debugging memory corruption problems. Finally, we discuss some of the novel automated debugging mechanisms that can be layered upon postmortem type identification.


title: A novel evolutionary formulation of the maximum independent set problem

abstract: We introduce a novel evolutionary formulation of the problem of finding a maximum independent set of a graph. The new formulation is based on the relationship that exists between a graph's independence number and its acyclic orientations. It views such orientations as individuals and evolves them with the aid of evolutionary operators that are very heavily based on the structure of the graph and its acyclic orientations. The resulting heuristic has been tested on some of the Second DIMACS Implementation Challenge benchmark graphs, and has been found to be competitive when compared to several of the other heuristics that have also been tested on those graphs.


title: Two novel evolutionary formulations of the graph coloring problem

abstract: We introduce two novel evolutionary formulations of the problem of coloring the nodes of a graph. The first formulation is based on the relationship that exists between a graph's chromatic number and its acyclic orientations. It views such orientations as individuals and evolves them with the aid of evolutionary operators that are very heavily based on the structure of the graph and its acyclic orientations. The second formulation, unlike the first one, does not tackle one graph at a time, but rather aims at evolving a `program' to color all graphs belonging to a class whose members all have the same number of nodes and other common attributes. The heuristics that result from these formulations have been tested on some of the Second DIMACS Implementation Challenge benchmark graphs, and have been found to be competitive when compared to the several other heuristics that have also been tested on those graphs.


title: A distributed algorithm to find k-dominating sets

abstract: We consider a connected undirected graph $G(n,m)$ with $n$ nodes and $m$ edges. A $k$-dominating set $D$ in $G$ is a set of nodes having the property that every node in $G$ is at most $k$ edges away from at least one node in $D$. Finding a $k$-dominating set of minimum size is NP-hard. We give a new synchronous distributed algorithm to find a $k$-dominating set in $G$ of size no greater than $\lfloor n/(k+1)\rfloor$. Our algorithm requires $O(k\log^*n)$ time and $O(m\log k+n\log k\log^*n)$ messages to run. It has the same time complexity as the best currently known algorithm, but improves on that algorithm's message complexity and is, in addition, conceptually simpler.


title: Fast Verification of Convexity of Piecewise-linear Surfaces

abstract: We show that a realization of a closed connected PL-manifold of dimension n-1 in n-dimensional Euclidean space (n>2) is the boundary of a convex polyhedron (finite or infinite) if and only if the interior of each (n-3)-face has a point, which has a neighborhood lying on the boundary of an n-dimensional convex body. No initial assumptions about the topology or orientability of the input surface are made. The theorem is derived from a refinement and generalization of Van Heijenoort's theorem on locally convex manifolds to spherical spaces. Our convexity criterion for PL-manifolds implies an easy polynomial-time algorithm for checking convexity of a given PL-surface in n-dimensional Euclidean or spherical space, n>2. The algorithm is worst case optimal with respect to both the number of operations and the algebraic degree. The algorithm works under significantly weaker assumptions and is easier to implement than convexity verification algorithms suggested by Mehlhorn et al (1996-1999), and Devillers et al.(1998). A paradigm of approximate convexity is suggested and a simplified algorithm of smaller degree and complexity is suggested for approximate floating point convexity verification.


title: On reducing the complexity of matrix clocks

abstract: Matrix clocks are a generalization of the notion of vector clocks that allows the local representation of causal precedence to reach into an asynchronous distributed computation's past with depth $x$, where $x\ge 1$ is an integer. Maintaining matrix clocks correctly in a system of $n$ nodes requires that everymessage be accompanied by $O(n^x)$ numbers, which reflects an exponential dependency of the complexity of matrix clocks upon the desired depth $x$. We introduce a novel type of matrix clock, one that requires only $nx$ numbers to be attached to each message while maintaining what for many applications may be the most significant portion of the information that the original matrix clock carries. In order to illustrate the new clock's applicability, we demonstrate its use in the monitoring of certain resource-sharing computations.


title: Finding approximate palindromes in strings

abstract: We introduce a novel definition of approximate palindromes in strings, and provide an algorithm to find all maximal approximate palindromes in a string with up to $k$ errors. Our definition is based on the usual edit operations of approximate pattern matching, and the algorithm we give, for a string of size $n$ on a fixed alphabet, runs in $O(k^2 n)$ time. We also discuss two implementation-related improvements to the algorithm, and demonstrate their efficacy in practice by means of both experiments and an average-case analysis.


title: The combinatorics of resource sharing

abstract: We discuss general models of resource-sharing computations, with emphasis on the combinatorial structures and concepts that underlie the various deadlock models that have been proposed, the design of algorithms and deadlock-handling policies, and concurrency issues. These structures are mostly graph-theoretic in nature, or partially ordered sets for the establishment of priorities among processes and acquisition orders on resources. We also discuss graph-coloring concepts as they relate to resource sharing.


title: A uniform approach to constraint-solving for lists, multisets, compact lists, and sets

abstract: Lists, multisets, and sets are well-known data structures whose usefulness is widely recognized in various areas of Computer Science. These data structures have been analyzed from an axiomatic point of view with a parametric approach in (*) where the relevant unification algorithms have been developed. In this paper we extend these results considering more general constraints including not only equality but also membership constraints as well as their negative counterparts. (*) A. Dovier, A. Policriti, and G. Rossi. A uniform axiomatic view of lists, multisets, and sets, and the relevant unification algorithms. Fundamenta Informaticae, 36(2/3):201--234, 1998.


title: The Liar and Related Paradoxes: Fuzzy Truth Value Assignment for Collections of Self-Referential Sentences

abstract: We study self-referential sentences of the type related to the Liar paradox. In particular, we consider the problem of assigning consistent fuzzy truth values to collections of self-referential sentences. We show that the problem can be reduced to the solution of a system of nonlinear equations. Furthermore, we prove that, under mild conditions, such a system always has a solution (i.e. a consistent truth value assignment) and that, for a particular implementation of logical ``and'', ``or'' and ``negation'', the ``mid-point'' solution is always consistent. Next we turn to computational issues and present several truth-value assignment algorithms; we argue that these algorithms can be understood as generalized sequential reasoning. In an Appendix we present a large number of examples of self-referential collections (including the Liar and the Strengthened Liar), we formulate the corresponding truth value equations and solve them analytically and/ or numerically.


title: Causes and Effects in Computer Programs

abstract: Debugging is commonly understood as finding and fixing the cause of a problem. But what does ``cause'' mean? How can we find causes? How can we prove that a cause is a cause--or even ``the'' cause? This paper defines common terms in debugging, highlights the principal techniques, their capabilities and limitations.


title: Goedel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements

abstract: We present the first class of mathematically rigorous, general, fully self-referential, self-improving, optimally efficient problem solvers. Inspired by Kurt Goedel's celebrated self-referential formulas (1931), such a problem solver rewrites any part of its own code as soon as it has found a proof that the rewrite is useful, where the problem-dependent utility function and the hardware and the entire initial code are described by axioms encoded in an initial proof searcher which is also part of the initial code. The searcher systematically and efficiently tests computable proof techniques (programs whose outputs are proofs) until it finds a provably useful, computable self-rewrite. We show that such a self-rewrite is globally optimal - no local maxima! - since the code first had to prove that it is not useful to continue the proof search for alternative self-rewrites. Unlike previous non-self-referential methods based on hardwired proof searchers, ours not only boasts an optimal order of complexity but can optimally reduce any slowdowns hidden by the O()-notation, provided the utility of such speed-ups is provable at all.


title: Control and Debugging of Distributed Programs Using Fiddle

abstract: The main goal of Fiddle, a distributed debugging engine, is to provide a flexible platform for developing debugging tools. Fiddle provides a layered set of interfaces with a minimal set of debugging functionalities, for the inspection and control of distributed and multi-threaded applications. This paper illustrates how Fiddle is used to support integrated testing and debugging. The approach described is based on a tool, called Deipa, that interprets sequences of commands read from an input file, generated by an independent testing tool. Deipa acts as a Fiddle client, in order to enforce specific execution paths in a distributed PVM program. Other Fiddle clients may be used along with Deipa for the fine debugging at process level. Fiddle and Deipa functionalities and architectures are described, and a working example shows a step-by-step application of these tools.


title: Computing Igusa's Local Zeta Functions of Univariate Polynomials, and Linear Feedback Shift Registers

abstract: We give a polynomial time algorithm for computing the Igusa local zeta function $Z(s,f)$ attached to a polynomial $f(x)\in \QTR{Bbb}{Z}[x]$, in one variable, with splitting field $\QTR{Bbb}{Q}$, and a prime number $p$. We also propose a new class of Linear Feedback Shift Registers based on the computation of Igusa's local zeta function.


title: New Lattice Based Cryptographic Constructions

abstract: We introduce the use of Fourier analysis on lattices as an integral part of a lattice based construction. The tools we develop provide an elegant description of certain Gaussian distributions around lattice points. Our results include two cryptographic constructions which are based on the worst-case hardness of the unique shortest vector problem. The main result is a new public key cryptosystem whose security guarantee is considerably stronger than previous results ($O(n^{1.5})$ instead of $O(n^7)$). This provides the first alternative to Ajtai and Dwork's original 1996 cryptosystem. Our second result is a family of collision resistant hash functions which, apart from improving the security in terms of the unique shortest vector problem, is also the first example of an analysis which is not based on Ajtai's iterative step. Surprisingly, both results are derived from one theorem which presents two indistinguishable distributions on the segment $[0,1)$. It seems that this theorem can have further applications and as an example we mention how it can be used to solve an open problem related to quantum computation.


title: Minimal DFAs for Testing Divisibility

abstract: We present and prove a theorem answering the question "how many states does a minimal deterministic finite automaton (DFA) that recognizes the set of base-b numbers divisible by k have?"


title: A Hierarchical Situation Calculus

abstract: A situation calculus is presented that provides a solution to the frame problem for hierarchical situations, that is, situations that have a modular structure in which parts of the situation behave in a relatively independent manner. This situation calculus is given in a relational, functional, and modal logic form. Each form permits both a single level hierarchy or a multiple level hierarchy, giving six versions of the formalism in all, and a number of sub-versions of these. For multiple level hierarchies, it is possible to give equations between parts of the situation to impose additional structure on the problem. This approach is compared to others in the literature.


title: Active Internet Traffic Filtering: Real-time Response to Denial of Service Attacks

abstract: Denial of Service (DoS) attacks are one of the most challenging threats to Internet security. An attacker typically compromises a large number of vulnerable hosts and uses them to flood the victim's site with malicious traffic, clogging its tail circuit and interfering with normal traffic. At present, the network operator of a site under attack has no other resolution but to respond manually by inserting filters in the appropriate edge routers to drop attack traffic. However, as DoS attacks become increasingly sophisticated, manual filter propagation becomes unacceptably slow or even infeasible. In this paper, we present Active Internet Traffic Filtering, a new automatic filter propagation protocol. We argue that this system provides a guaranteed, significant level of protection against DoS attacks in exchange for a reasonable, bounded amount of router resources. We also argue that the proposed system cannot be abused by a malicious node to interfere with normal Internet operation. Finally, we argue that it retains its efficiency in the face of continued Internet growth.