title: Integrating existing cone-shaped and projection-based cardinal direction relations and a TCSP-like decidable generalisation

abstract: We consider the integration of existing cone-shaped and projection-based calculi of cardinal direction relations, well-known in QSR. The more general, integrating language we consider is based on convex constraints of the qualitative form $r(x,y)$, $r$ being a cone-shaped or projection-based cardinal direction atomic relation, or of the quantitative form $(\alpha ,\beta)(x,y)$, with $\alpha ,\beta\in [0,2\pi)$ and $(\beta -\alpha)\in [0,\pi ]$: the meaning of the quantitative constraint, in particular, is that point $x$ belongs to the (convex) cone-shaped area rooted at $y$, and bounded by angles $\alpha$ and $\beta$. The general form of a constraint is a disjunction of the form $[r_1\vee...\vee r_{n_1}\vee (\alpha_1,\beta_1)\vee...\vee (\alpha _{n_2},\beta_{n_2})](x,y)$, with $r_i(x,y)$, $i=1... n_1$, and $(\alpha _i,\beta_i)(x,y)$, $i=1... n_2$, being convex constraints as described above: the meaning of such a general constraint is that, for some $i=1... n_1$, $r_i(x,y)$ holds, or, for some $i=1... n_2$, $(\alpha_i,\beta_i)(x,y)$ holds. A conjunction of such general constraints is a $\tcsp$-like CSP, which we will refer to as an $\scsp$ (Spatial Constraint Satisfaction Problem). An effective solution search algorithm for an $\scsp$ will be described, which uses (1) constraint propagation, based on a composition operation to be defined, as the filtering method during the search, and (2) the Simplex algorithm, guaranteeing completeness, at the leaves of the search tree. The approach is particularly suited for large-scale high-level vision, such as, e.g., satellite-like surveillance of a geographic area.


title: A Situation Calculus-based Approach To Model Ubiquitous Information Services

abstract: This paper presents an augmented situation calculus-based approach to model autonomous computing paradigm in ubiquitous information services. To make it practical for commercial development and easier to support autonomous paradigm imposed by ubiquitous information services, we made improvements based on Reiter's standard situation calculus. First we explore the inherent relationship between fluents and evolution: since not all fluents contribute to systems' evolution and some fluents can be derived from some others, we define those fluents that are sufficient and necessary to determine evolutional potential as decisive fluents, and then we prove that their successor states wrt to deterministic complex actions satisfy Markov property. Then, within the calculus framework we build, we introduce validity theory to model the autonomous services with application-specific validity requirements, including: validity fluents to axiomatize validity requirements, heuristic multiple alternative service choices ranging from complete acceptance, partial acceptance, to complete rejection, and validity-ensured policy to comprise such alternative service choices into organic, autonomously-computable services. Our approach is demonstrated by a ubiquitous calendaring service, ACS, throughout the paper.


title: Weak Bezout inequality for D-modules

abstract: Let $\{w_{i,j}\}_{1\leq i\leq n, 1\leq j\leq s} \subset L_m=F(X_1,...,X_m)[{\partial \over \partial X_1},..., {\partial \over \partial X_m}]$ be linear partial differential operators of orders with respect to ${\partial \over \partial X_1},..., {\partial \over \partial X_m}$ at most $d$. We prove an upper bound n(4m^2d\min\{n,s\})^{4^{m-t-1}(2(m-t))} on the leading coefficient of the Hilbert-Kolchin polynomial of the left $L_m$-module $<\{w_{1,j}, ..., w_{n,j}\}_{1\leq j \leq s} > \subset L_m^n$ having the differential type $t$ (also being equal to the degree of the Hilbert-Kolchin polynomial). The main technical tool is the complexity bound on solving systems of linear equations over {\it algebras of fractions} of the form $$L_m(F[X_1,..., X_m, {\partial \over \partial X_1},..., {\partial \over \partial X_k}])^{-1}.$$


title: Copyright and Creativity: Authors and Photographers

abstract: The history of the occupations "author" and "photographer" provides an insightful perspective on copyright and creativity. The concept of the romantic author, associated with personal creative genius, gained prominence in the eighteenth century. However, in the U.S. in 1900 only about three thousand persons professed their occupation to be "author." Self-professed "photographers" were then about ten times as numerous as authors. Being a photographer was associated with manufacturing and depended only on mastering technical skills and making a living. Being an author, in contrast, was an elite status associated with science and literature. Across the twentieth century, the number of writers and authors grew much more rapidly than the number of photographers. The relative success of writers and authors in creating jobs seems to have depended not on differences in copyright or possibilities for self-production, but on greater occupational innovation. Creativity in organizing daily work is an important form of creativity.


title: The concept of strong and weak virtual reality

abstract: We approach the virtual reality phenomenon by studying its relationship to set theory, and we investigate the case where this is done using the wellfoundedness property of sets. Our hypothesis is that non-wellfounded sets (hypersets) give rise to a different quality of virtual reality than do familiar wellfounded sets. We initially provide an alternative approach to virtual reality based on Sommerhoff's idea of first and second order self-awareness; both categories of self-awareness are considered as necessary conditions for consciousness in terms of higher cognitive functions. We then introduce a representation of first and second order self-awareness through sets, and assume that these sets, which we call events, originally form a collection of wellfounded sets. Strong virtual reality characterizes virtual reality environments which have the limited capacity to create only events associated with wellfounded sets. In contrast, the more general concept of weak virtual reality characterizes collections of virtual reality mediated events altogether forming an entirety larger than any collection of wellfounded sets. By giving reference to Aczel's hyperset theory we indicate that this definition is not empty, because hypersets encompass wellfounded sets already. Moreover, we argue that weak virtual reality could be realized in human history through continued progress in computer technology. Finally, we reformulate our characterization into a more general framework, and use Baltag's Structural Theory of Sets (STS) to show that within this general hyperset theory Sommerhoff's first and second order self-awareness as well as both concepts of virtual reality admit a consistent mathematical representation.


title: On Structuring Proof Search for First Order Linear Logic

abstract: Full first order linear logic can be presented as an abstract logic programming language in Miller's system Forum, which yields a sensible operational interpretation in the 'proof search as computation' paradigm. However, Forum still has to deal with syntactic details that would normally be ignored by a reasonable operational semantics. In this respect, Forum improves on Gentzen systems for linear logic by restricting the language and the form of inference rules. We further improve on Forum by restricting the class of formulae allowed, in a system we call G-Forum, which is still equivalent to full first order linear logic. The only formulae allowed in G-Forum have the same shape as Forum sequents: the restriction does not diminish expressiveness and makes G-Forum amenable to proof theoretic analysis. G-Forum consists of two (big) inference rules, for which we show a cut elimination procedure. This does not need to appeal to finer detail in formulae and sequents than is provided by G-Forum, thus successfully testing the internal symmetries of our system.


title: Hybrid LQG-Neural Controller for Inverted Pendulum System

abstract: The paper presents a hybrid system controller, incorporating a neural and an LQG controller. The neural controller has been optimized by genetic algorithms directly on the inverted pendulum system. The failure free optimization process stipulated a relatively small region of the asymptotic stability of the neural controller, which is concentrated around the regulation point. The presented hybrid controller combines benefits of a genetically optimized neural controller and an LQG controller in a single system controller. High quality of the regulation process is achieved through utilization of the neural controller, while stability of the system during transient processes and a wide range of operation are assured through application of the LQG controller. The hybrid controller has been validated by applying it to a simulation model of an inherently unstable system of inverted pendulum.


title: Improving spam filtering by combining Naive Bayes with simple k-nearest neighbor searches

abstract: Using naive Bayes for email classification has become very popular within the last few months. They are quite easy to implement and very efficient. In this paper we want to present empirical results of email classification using a combination of naive Bayes and k-nearest neighbor searches. Using this technique we show that the accuracy of a Bayes filter can be improved slightly for a high number of features and significantly for a small number of features.


title: A Cartography for 2x2 Symmetric Games

abstract: A bidimensional representation of the space of 2x2 Symmetric Games in the strategic representation is proposed. This representation provides a tool for the classification of 2x2 symmetric games, quantification of the fraction of them having a certain feature, and predictions of changes in the characteristics of a game when a change in done on the payoff matrix that defines it.


title: Benchmarking and Implementation of Probability-Based Simulations on Programmable Graphics Cards

abstract: The latest Graphics Processing Units (GPUs) are reported to reach up to 200 billion floating point operations per second (200 Gflops) and to have price performance of 0.1 cents per M flop. These facts raise great interest in the plausibility of extending the GPUs' use to non-graphics applications, in particular numerical simulations on structured grids (lattice). We review previous work on using GPUs for non-graphics applications, implement probability-based simulations on the GPU, namely the Ising and percolation models, implement vector operation benchmarks for the GPU, and finally compare the CPU's and GPU's performance. A general conclusion from the results obtained is that moving computations from the CPU to the GPU is feasible, yielding good time and price performance, for certain lattice computations. Preliminary results also show that it is feasible to use them in parallel


title: Counting complexity classes for numeric computations II: algebraic and semialgebraic sets

abstract: We define counting classes #P_R and #P_C in the Blum-Shub-Smale setting of computations over the real or complex numbers, respectively. The problems of counting the number of solutions of systems of polynomial inequalities over R, or of systems of polynomial equalities over C, respectively, turn out to be natural complete problems in these classes. We investigate to what extent the new counting classes capture the complexity of computing basic topological invariants of semialgebraic sets (over R) and algebraic sets (over C). We prove that the problem of computing the (modified) Euler characteristic of semialgebraic sets is FP_R^{#P_R}-complete, and that the problem of computing the geometric degree of complex algebraic sets is FP_C^{#P_C}-complete. We also define new counting complexity classes in the classical Turing model via taking Boolean parts of the classes above, and show that the problems to compute the Euler characteristic and the geometric degree of (semi)algebraic sets given by integer polynomials are complete in these classes. We complement the results in the Turing model by proving, for all k in N, the FPSPACE-hardness of the problem of computing the k-th Betti number of the zet of real zeros of a given integer polynomial. This holds with respect to the singular homology as well as for the Borel-Moore homology.


title: Embedding Web-based Statistical Translation Models in Cross-Language Information Retrieval

abstract: Although more and more language pairs are covered by machine translation services, there are still many pairs that lack translation resources. Cross-language information retrieval (CLIR) is an application which needs translation functionality of a relatively low level of sophistication since current models for information retrieval (IR) are still based on a bag-of-words. The Web provides a vast resource for the automatic construction of parallel corpora which can be used to train statistical translation models automatically. The resulting translation models can be embedded in several ways in a retrieval model. In this paper, we will investigate the problem of automatically mining parallel texts from the Web and different ways of integrating the translation models within the retrieval process. Our experiments on standard test collections for CLIR show that the Web-based translation models can surpass commercial MT systems in CLIR tasks. These results open the perspective of constructing a fully automatic query translation device for CLIR at a very low cost.


title: Failure-Free Genetic Algorithm Optimization of a System Controller Using SAFE/LEARNING Controllers in Tandem

abstract: The paper presents a method for failure free genetic algorithm optimization of a system controller. Genetic algorithms present a powerful tool that facilitates producing near-optimal system controllers. Applied to such methods of computational intelligence as neural networks or fuzzy logic, these methods are capable of combining the non-linear mapping capabilities of the latter with learning the system behavior directly, that is, without a prior model. At the same time, genetic algorithms routinely produce solutions that lead to the failure of the controlled system. Such solutions are generally unacceptable for applications where safe operation must be guaranteed. We present here a method of design, which allows failure-free application of genetic algorithms through utilization of SAFE and LEARNING controllers in tandem, where the SAFE controller recovers the system from dangerous states while the LEARNING controller learns its behavior. The method has been validated by applying it to an inherently unstable system of inverted pendulum.


title: Designing of a Community-based Translation Center

abstract: Interfaces that support multi-lingual content can reach a broader community. We wish to extend the reach of CITIDEL, a digital library for computing education materials, to support multiple languages. By doing so, we hope that it will increase the number of users, and in turn the number of resources. This paper discusses three approaches to translation (automated translation, developer-based, and community-based), and a brief evaluation of these approaches. It proposes a design for an online community translation center where volunteers help translate interface components and educational materials available in CITIDEL.


title: Constraint Optimization and Statistical Mechanics

abstract: In these lectures I will present an introduction to the results that have been recently obtained in constraint optimization of random problems using statistical mechanics techniques. After presenting the general results, in order to simplify the presentation I will describe in details only the problems related to the coloring of a random graph.


title: Methods to Model-Check Parallel Systems Software

abstract: We report on an effort to develop methodologies for formal verification of parts of the Multi-Purpose Daemon (MPD) parallel process management system. MPD is a distributed collection of communicating processes. While the individual components of the collection execute simple algorithms, their interaction leads to unexpected errors that are difficult to uncover by conventional means. Two verification approaches are discussed here: the standard model checking approach using the software model checker SPIN and the nonstandard use of a general-purpose first-order resolution-style theorem prover OTTER to conduct the traditional state space exploration. We compare modeling methodology and analyze performance and scalability of the two methods with respect to verification of MPD.


title: Fuzziness versus probability again

abstract: A construction of a fuzzy logic controller based on an analogy between fuzzy conditional rule of inference and marginal probability in terms of the conditional probability function has been proposed.


title: Logical Characterizations of Heap Abstractions

abstract: Shape analysis concerns the problem of determining "shape invariants" for programs that perform destructive updating on dynamically allocated storage. In recent work, we have shown how shape analysis can be performed, using an abstract interpretation based on 3-valued first-order logic. In that work, concrete stores are finite 2-valued logical structures, and the sets of stores that can possibly arise during execution are represented (conservatively) using a certain family of finite 3-valued logical structures. In this paper, we show how 3-valued structures that arise in shape analysis can be characterized using formulas in first-order logic with transitive closure. We also define a non-standard ("supervaluational") semantics for 3-valued first-order logic that is more precise than a conventional 3-valued semantics, and demonstrate that the supervaluational semantics can be effectively implemented using existing theorem provers.


title: Soft lambda-calculus: a language for polynomial time computation

abstract: Soft linear logic ([Lafont02]) is a subsystem of linear logic characterizing the class PTIME. We introduce Soft lambda-calculus as a calculus typable in the intuitionistic and affine variant of this logic. We prove that the (untyped) terms of this calculus are reducible in polynomial time. We then extend the type system of Soft logic with recursive types. This allows us to consider non-standard types for representing lists. Using these datatypes we examine the concrete expressivity of Soft lambda-calculus with the example of the insertion sort algorithm.


title: Taking the Initiative with Extempore: Exploring Out-of-Turn Interactions with Websites

abstract: We present the first study to explore the use of out-of-turn interaction in websites. Out-of-turn interaction is a technique which empowers the user to supply unsolicited information while browsing. This approach helps flexibly bridge any mental mismatch between the user and the website, in a manner fundamentally different from faceted browsing and site-specific search tools. We built a user interface (Extempore) which accepts out-of-turn input via voice or text; and employed it in a US congressional website, to determine if users utilize out-of-turn interaction for information-finding tasks, and their rationale for doing so. The results indicate that users are adept at discerning when out-of-turn interaction is necessary in a particular task, and actively interleaved it with browsing. However, users found cascading information across information-finding subtasks challenging. Therefore, this work not only improves our understanding of out-of-turn interaction, but also suggests further opportunities to enrich browsing experiences for users.


title: An Exploratory Study of Mobile Computing Use by Knowledge Workers

abstract: This paper describes some preliminary results from a 20-week study on the use of Compaq iPAQ Personal Digital Assistants (PDAs) by 10 senior developers, analysts, technical managers, and senior organisational managers. The goal of the study was to identify what applications were used, how and where they were used, the problems and issues that arose, and how use of the iPAQs changed over the study period. The paper highlights some interesting uses of the iPAQs, and identifies some of the characteristics of successful mobile applications.


title: Mapping Subsets of Scholarly Information

abstract: We illustrate the use of machine learning techniques to analyze, structure, maintain, and evolve a large online corpus of academic literature. An emerging field of research can be identified as part of an existing corpus, permitting the implementation of a more coherent community structure for its practitioners.


title: Verification of recursive parallel systems

abstract: In this paper we consider the problem of proving properties of infinite behaviour of formalisms suitable to describe (infinite state) systems with recursion and parallelism. As a formal setting, we consider the framework of Process Rewriting Systems (PRSs). For a meaningfull fragment of PRSs, allowing to accommodate both Pushdown Automata and Petri Nets, we state decidability results for a class of properties about infinite derivations (infinite term rewritings). The given results can be exploited for the automatic verification of some classes of linear time properties of infinite state systems described by PRSs. In order to exemplify the assessed results, we introduce a meaningful automaton based formalism which allows to express both recursion and multi--treading.


title: Modeling Object Oriented Constraint Programs in Z

abstract: Object oriented constraint programs (OOCPs) emerge as a leading evolution of constraint programming and artificial intelligence, first applied to a range of industrial applications called configuration problems. The rich variety of technical approaches to solving configuration problems (CLP(FD), CC(FD), DCSP, Terminological systems, constraint programs with set variables ...) is a source of difficulty. No universally accepted formal language exists for communicating about OOCPs, which makes the comparison of systems difficult. We present here a Z based specification of OOCPs which avoids the falltrap of hidden object semantics. The object system is part of the specification, and captures all of the most advanced notions from the object oriented modeling standard UML. The paper illustrates these issues and the conciseness and precision of Z by the specification of a working OOCP that solves an historical AI problem : parsing a context free grammar. Being written in Z, an OOCP specification also supports formal proofs. The whole builds the foundation of an adaptative and evolving framework for communicating about constrained object models and programs.


title: ICT-based planning and the missing educational link

abstract: The past century ended with an unexpected explosion of Information and Communication Technologies (ICT), both in planning/managing public policies, and in exchanging knowledge. However, the extent to which ICT-based tools increase the level of public knowledge, or help decision makers is still uncertain. Although indirectly, the overload of unfiltered Web-based information seems able to hamper the knowledge growth of people, particularly in some developing communities, whereas Decision Support Systems (DSS) and Geographical Information Systems (GIS) prove to be ineffective if managed by unskilled planning bodies. Given such warns, this paper outlines how the different social and cultural awareness of local communities can affect the outcomes of ICT-based tools. It further explores the impacts of ICT-based tools on community development and spatial planning, emphasizing the role of proper literacy and education for effective management.


title: GridEmail: A Case for Economically Regulated Internet-based Interpersonal Communications

abstract: Email has emerged as a dominant form of electronic communication between people. Spam is a major problem for email users, with estimates of up to 56% of email falling into that category. Control of Spam is being attempted with technical and legislative methods. In this paper we look at email and spam from a supply-demand perspective. We propose Gridemail, an email system based on an economy of communicating parties, where participants? motivations are represented as pricing policies and profiles. This system is expected to help people regulate their personal communications to suit their conditions, and help in removing unwanted messages.


title: Inferring Termination Conditions for Logic Programs using Backwards Analysis

abstract: This paper focuses on the inference of modes for which a logic program is guaranteed to terminate. This generalises traditional termination analysis where an analyser tries to verify termination for a specified mode. Our contribution is a methodology in which components of traditional termination analysis are combined with backwards analysis to obtain an analyser for termination inference. We identify a condition on the components of the analyser which guarantees that termination inference will infer all modes which can be checked to terminate. The application of this methodology to enhance a traditional termination analyser to perform also termination inference is demonstrated.


title: Evolution: Google vs. DRIS

abstract: This paper gives an absolute new search system that builds the information retrieval infrastructure for Internet. Now most search engine companies are mainly concerned with how to make profit from company users by advertisement and ranking prominence, but never consider what its real customers will feel. Few web search engines can sell billions dollars just at the cost of inconvenience of most Internet users, but not its high quality of search service. When we have to bear the bothersome advertisements in the awful results and have no choices, Internet as the kind of public good will surely be undermined. If current Internet can't fully ensure our right to know, it may need some sound improvements or a revolution.


title: Soft Constraint Programming to Analysing Security Protocols

abstract: Security protocols stipulate how the remote principals of a computer network should interact in order to obtain specific security goals. The crucial goals of confidentiality and authentication may be achieved in various forms, each of different strength. Using soft (rather than crisp) constraints, we develop a uniform formal notion for the two goals. They are no longer formalised as mere yes/no properties as in the existing literature, but gain an extra parameter, the security level. For example, different messages can enjoy different levels of confidentiality, or a principal can achieve different levels of authentication with different principals. The goals are formalised within a general framework for protocol analysis that is amenable to mechanisation by model checking. Following the application of the framework to analysing the asymmetric Needham-Schroeder protocol, we have recently discovered a new attack on that protocol as a form of retaliation by principals who have been attacked previously. Having commented on that attack, we then demonstrate the framework on a bigger, largely deployed protocol consisting of three phases, Kerberos.


title: Speedup of Logic Programs by Binarization and Partial Deduction

abstract: Binary logic programs can be obtained from ordinary logic programs by a binarizing transformation. In most cases, binary programs obtained this way are less efficient than the original programs. (Demoen, 1992) showed an interesting example of a logic program whose computational behaviour was improved when it was transformed to a binary program and then specialized by partial deduction. The class of B-stratifiable logic programs is defined. It is shown that for every B-stratifiable logic program, binarization and subsequent partial deduction produce a binary program which does not contain variables for continuations introduced by binarization. Such programs usually have a better computational behaviour than the original ones. Both binarization and partial deduction can be easily automated. A comparison with other related approaches to program transformation is given.


title: An Open Ended Tree

abstract: An open ended list is a well known data structure in Prolog programs. It is frequently used to represent a value changing over time, while this value is referred to from several places in the data structure of the application. A weak point in this technique is that the time complexity is linear in the number of updates to the value represented by the open ended list. In this programming pearl we present a variant of the open ended list, namely an open ended tree, with an update and access time complexity logarithmic in the number of updates to the value.


title: Minimal founded semantics for disjunctive logic programs and deductive databases

abstract: In this paper, we propose a variant of stable model semantics for disjunctive logic programming and deductive databases. The semantics, called minimal founded, generalizes stable model semantics for normal (i.e. non disjunctive) programs but differs from disjunctive stable model semantics (the extension of stable model semantics for disjunctive programs). Compared with disjunctive stable model semantics, minimal founded semantics seems to be more intuitive, it gives meaning to programs which are meaningless under stable model semantics and is no harder to compute. More specifically, minimal founded semantics differs from stable model semantics only for disjunctive programs having constraint rules or rules working as constraints. We study the expressive power of the semantics and show that for general disjunctive datalog programs it has the same power as disjunctive stable model semantics.


title: Strong Equivalence Made Easy: Nested Expressions and Weight Constraints

abstract: Logic programs P and Q are strongly equivalent if, given any program R, programs P union R and Q union R are equivalent (that is, have the same answer sets). Strong equivalence is convenient for the study of equivalent transformations of logic programs: one can prove that a local change is correct without considering the whole program. Lifschitz, Pearce and Valverde showed that Heyting's logic of here-and-there can be used to characterize strong equivalence for logic programs with nested expressions (which subsume the better-known extended disjunctive programs). This note considers a simpler, more direct characterization of strong equivalence for such programs, and shows that it can also be applied without modification to the weight constraint programs of Niemela and Simons. Thus, this characterization of strong equivalence is convenient for the study of equivalent transformations of logic programs written in the input languages of answer set programming systems dlv and smodels. The note concludes with a brief discussion of results that can be used to automate reasoning about strong equivalence, including a novel encoding that reduces the problem of deciding the strong equivalence of a pair of weight constraint programs to that of deciding the inconsistency of a weight constraint program.


title: CSIEC (Computer Simulator in Educational Communication): An Intelligent Web-Based Teaching System for Foreign Language Learning

abstract: In this paper we present an innovative intelligent web-based computer-aided instruction system for foreign language learning: CSIEC (Computer Simulator in Educational Communication). This system can not only grammatically understand the sentences in English given from the users via Internet, but also reasonably and individually speak with the users. At first the related works in this research field are analyzed. Then we introduce the system goals and the system framework, i.e., the natural language understanding mechanism (NLML, NLOMJ and NLDB) and the communicational response (CR). Finally we give the syntactic and semantic content of this instruction system, i.e. some important notations of English grammar used in it and their relations with the NLOMJ.


title: Distributed WWW Programming using (Ciao-)Prolog and the PiLLoW library

abstract: We discuss from a practical point of view a number of issues involved in writing distributed Internet and WWW applications using LP/CLP systems. We describe PiLLoW, a public-domain Internet and WWW programming library for LP/CLP systems that we have designed in order to simplify the process of writing such applications. PiLLoW provides facilities for accessing documents and code on the WWW; parsing, manipulating and generating HTML and XML structured documents and data; producing HTML forms; writing form handlers and CGI-scripts; and processing HTML/XML templates. An important contribution of PiLLoW is to model HTML/XML code (and, thus, the content of WWW pages) as terms. The PiLLoW library has been developed in the context of the Ciao Prolog system, but it has been adapted to a number of popular LP/CLP systems, supporting most of its functionality. We also describe the use of concurrency and a high-level model of client-server interaction, Ciao Prolog's active modules, in the context of WWW programming. We propose a solution for client-side downloading and execution of Prolog code, using generic browsers. Finally, we also provide an overview of related work on the topic.


title: Learning in a Compiler for MINSAT Algorithms

abstract: This paper describes learning in a compiler for algorithms solving classes of the logic minimization problem MINSAT, where the underlying propositional formula is in conjunctive normal form (CNF) and where costs are associated with the True/False values of the variables. Each class consists of all instances that may be derived from a given propositional formula and costs for True/False values by fixing or deleting variables, and by deleting clauses. The learning step begins once the compiler has constructed a solution algorithm for a given class. The step applies that algorithm to comparatively few instances of the class, analyses the performance of the algorithm on these instances, and modifies the underlying propositional formula, with the goal that the algorithm will perform much better on all instances of the class.


title: Using sensors in the web crawling process

abstract: This paper offers a short description of an Internet information field monitoring system, which places a special module-sensor on the side of the Web-server to detect changes in information resources and subsequently reindexes only the resources signalized by the corresponding sensor. Concise results of simulation research and an implementation attempt of the given "sensors" concept are provided.


title: Sharing secret color images using cellular automata with memory

abstract: A {k,n}-threshold scheme based on two-dimensional memory cellular automata is proposed to share images in a secret way. This method allows to encode an image into n shared images so that only qualified subsets of k or more shares can recover the secret image, but any k-1 or fewer of them gain no information about the original image. The main characteristics of this new scheme are: each shared image has the same size that the original one, and the recovered image is exactly the same than the secret image; i.e., there is no loss of resolution.


title: Analysis of Implementation Hierocrypt-3 algorithm (and its comparison to Camellia algorithm) using ALTERA devices

abstract: Alghoritms: HIEROCRYPT-3, CAMELLIA and ANUBIS, GRAND CRU, NOEKEON, NUSH, Q, RC6, SAFER++128, SC2000, SHACAL were requested for the submission of block ciphers (high level block cipher) to NESSIE (New European Schemes for Signatures, Integrity, and Encryption) project. The main purpose of this project was to put forward a portfolio of strong cryptographic primitives of various types. The NESSIE project was a three year long project and has been divided into two phases. The first was finished in June 2001r. CAMELLIA, RC6, SAFER++128 and SHACAL were accepted for the second phase of the evaluation process. HIEROCRYPT-3 had key schedule problems, and there were attacks for up to 3,5 rounds out of 6, at least hardware implementations of this cipher were extremely slow [12]. HIEROCRYPT-3 was not selected to Phase II. CAMELLIA was selected as an algorithm suggested for future standard. In the paper we present the hardware implementations these two algorithms with 128-bit blocks and 128-bit keys, using ALTERA devices and their comparisons.


title: What Causes a System to Satisfy a Specification?

abstract: Even when a system is proven to be correct with respect to a specification, there is still a question of how complete the specification is, and whether it really covers all the behaviors of the system. Coverage metrics attempt to check which parts of a system are actually relevant for the verification process to succeed. Recent work on coverage in model checking suggests several coverage metrics and algorithms for finding parts of the system that are not covered by the specification. The work has already proven to be effective in practice, detecting design errors that escape early verification efforts in industrial settings. In this paper, we relate a formal definition of causality given by Halpern and Pearl [2001] to coverage. We show that it gives significant insight into unresolved issues regarding the definition of coverage and leads to potentially useful extensions of coverage. In particular, we introduce the notion of responsibility, which assigns to components of a system a quantitative measure of their relevance to the satisfaction of the specification.


title: Characterizing and Reasoning about Probabilistic and Non-Probabilistic Expectation

abstract: Expectation is a central notion in probability theory. The notion of expectation also makes sense for other notions of uncertainty. We introduce a propositional logic for reasoning about expectation, where the semantics depends on the underlying representation of uncertainty. We give sound and complete axiomatizations for the logic in the case that the underlying representation is (a) probability, (b) sets of probability measures, (c) belief functions, and (d) possibility measures. We show that this logic is more expressive than the corresponding logic for reasoning about likelihood in the case of sets of probability measures, but equi-expressive in the case of probability, belief, and possibility. Finally, we show that satisfiability for these logics is NP-complete, no harder than satisfiability for propositional logic.


title: Responsibility and blame: a structural-model approach

abstract: Causality is typically treated an all-or-nothing concept; either A is a cause of B or it is not. We extend the definition of causality introduced by Halpern and Pearl [2001] to take into account the degree of responsibility of A for B. For example, if someone wins an election 11--0, then each person who votes for him is less responsible for the victory than if he had won 6--5. We then define a notion of degree of blame, which takes into account an agent's epistemic state. Roughly speaking, the degree of blame of A for B is the expected degree of responsibility of A for B, taken over the epistemic state of an agent.


title: Uniform test of algorithmic randomness over a general space

abstract: The algorithmic theory of randomness is well developed when the underlying space is the set of finite or infinite sequences and the underlying probability distribution is the uniform distribution or a computable distribution. These restrictions seem artificial. Some progress has been made to extend the theory to arbitrary Bernoulli distributions (by Martin-Loef), and to arbitrary distributions (by Levin). We recall the main ideas and problems of Levin's theory, and report further progress in the same framework. - We allow non-compact spaces (like the space of continuous functions, underlying the Brownian motion). - The uniform test (deficiency of randomness) d_P(x) (depending both on the outcome x and the measure P should be defined in a general and natural way. - We see which of the old results survive: existence of universal tests, conservation of randomness, expression of tests in terms of description complexity, existence of a universal measure, expression of mutual information as "deficiency of independence. - The negative of the new randomness test is shown to be a generalization of complexity in continuous spaces; we show that the addition theorem survives. The paper's main contribution is introducing an appropriate framework for studying these questions and related ones (like statistics for a general family of distributions).


title: Diagnostic reasoning with A-Prolog

abstract: In this paper we suggest an architecture for a software agent which operates a physical device and is capable of making observations and of testing and repairing the device's components. We present simplified definitions of the notions of symptom, candidate diagnosis, and diagnosis which are based on the theory of action language ${\cal AL}$. The definitions allow one to give a simple account of the agent's behavior in which many of the agent's tasks are reduced to computing stable models of logic programs.


title: Greedy Algorithms in Datalog

abstract: In the design of algorithms, the greedy paradigm provides a powerful tool for solving efficiently classical computational problems, within the framework of procedural languages. However, expressing these algorithms within the declarative framework of logic-based languages has proven a difficult research challenge. In this paper, we extend the framework of Datalog-like languages to obtain simple declarative formulations for such problems, and propose effective implementation techniques to ensure computational complexities comparable to those of procedural formulations. These advances are achieved through the use of the "choice" construct, extended with preference annotations to effect the selection of alternative stable-models and nondeterministic fixpoints. We show that, with suitable storage structures, the differential fixpoint computation of our programs matches the complexity of procedural algorithms in classical search and optimization problems.


title: Declarative Semantics for Active Rules

abstract: In this paper we analyze declarative deterministic and non-deterministic semantics for active rules. In particular we consider several (partial) stable model semantics, previously defined for deductive rules, such as well-founded, max deterministic, unique total stable model, total stable model, and maximal stable model semantics. The semantics of an active program AP is given by first rewriting it into a deductive program P, then computing a model M defining the declarative semantics of P and, finally, applying `consistent' updates contained in M to the source database. The framework we propose permits a natural integration of deductive and active rules and can also be applied to queries with function symbols or to queries over infinite databases.


title: On A Theory of Probabilistic Deductive Databases

abstract: We propose a framework for modeling uncertainty where both belief and doubt can be given independent, first-class status. We adopt probability theory as the mathematical formalism for manipulating uncertainty. An agent can express the uncertainty in her knowledge about a piece of information in the form of a confidence level, consisting of a pair of intervals of probability, one for each of her belief and doubt. The space of confidence levels naturally leads to the notion of a trilattice, similar in spirit to Fitting's bilattices. Intuitively, thep oints in such a trilattice can be ordered according to truth, information, or precision. We develop a framework for probabilistic deductive databases by associating confidence levels with the facts and rules of a classical deductive database. While the trilattice structure offers a variety of choices for defining the semantics of probabilistic deductive databases, our choice of semantics is based on the truth-ordering, which we find to be closest to the classical framework for deductive databases. In addition to proposing a declarative semantics based on valuations and an equivalent semantics based on fixpoint theory, we also propose a proof procedure and prove it sound and complete. We show that while classical Datalog query programs have a polynomial time data complexity, certain query programs in the probabilistic deductive database framework do not even terminate on some input databases. We identify a large natural class of query programs of practical interest in our framework, and show that programs in this class possess polynomial time data complexity, i.e., not only do they terminate on every input database, they are guaranteed to do so in a number of steps polynomial in the input database size.


title: Clustering by compression

abstract: We present a new method for clustering based on compression. The method doesn't use subject-specific features or background knowledge, and works as follows: First, we determine a universal similarity distance, the normalized compression distance or NCD, computed from the lengths of compressed data files (singly and in pairwise concatenation). Second, we apply a hierarchical clustering method. The NCD is universal in that it is not restricted to a specific application area, and works across application area boundaries. A theoretical precursor, the normalized information distance, co-developed by one of the authors, is provably optimal but uses the non-computable notion of Kolmogorov complexity. We propose precise notions of similarity metric, normal compressor, and show that the NCD based on a normal compressor is a similarity metric that approximates universality. To extract a hierarchy of clusters from the distance matrix, we determine a dendrogram (binary tree) by a new quartet method and a fast heuristic to implement it. The method is implemented and available as public software, and is robust under choice of different compressors. To substantiate our claims of universality and robustness, we report evidence of successful application in areas as diverse as genomics, virology, languages, literature, music, handwritten digits, astronomy, and combinations of objects from completely different domains, using statistical, dictionary, and block sorting compressors. In genomics we presented new evidence for major questions in Mammalian evolution, based on whole-mitochondrial genomic analysis: the Eutherian orders and the Marsupionta hypothesis against the Theria hypothesis.

categories: cs.CV cond-mat.stat-mech cs.AI physics.data-an q-bio.GN q-bio.QM


title: Weight Constraints as Nested Expressions

abstract: We compare two recent extensions of the answer set (stable model) semantics of logic programs. One of them, due to Lifschitz, Tang and Turner, allows the bodies and heads of rules to contain nested expressions. The other, due to Niemela and Simons, uses weight constraints. We show that there is a simple, modular translation from the language of weight constraints into the language of nested expressions that preserves the program's answer sets. Nested expressions can be eliminated from the result of this translation in favor of additional atoms. The translation makes it possible to compute answer sets for some programs with weight constraints using satisfiability solvers, and to prove the strong equivalence of programs with weight constraints using the logic of here-and there.


title: On the Abductive or Deductive Nature of Database Schema Validation and Update Processing Problems

abstract: We show that database schema validation and update processing problems such as view updating, materialized view maintenance, integrity constraint checking, integrity constraint maintenance or condition monitoring can be classified as problems of either abductive or deductive nature, according to the reasoning paradigm that inherently suites them. This is done by performing abductive and deductive reasoning on the event rules [Oli91], a set of rules that define the difference between consecutive database states In this way, we show that it is possible to provide methods able to deal with all these problems as a whole. We also show how some existing general deductive and abductive procedures may be used to reason on the event rules. In this way, we show that these procedures can deal with all database schema validation and update processing problems considered in this paper.


title: Mapping weblog communities

abstract: Websites of a particular class form increasingly complex networks, and new tools are needed to map and understand them. A way of visualizing this complex network is by mapping it. A map highlights which members of the community have similar interests, and reveals the underlying social network. In this paper, we will map a network of websites using Kohonen's self-organizing map (SOM), a neural-net like method generally used for clustering and visualization of complex data sets. The set of websites considered has been the Blogalia weblog hosting site (based at http://www.blogalia.com/), a thriving community of around 200 members, created in January 2002. In this paper we show how SOM discovers interesting community features, its relation with other community-discovering algorithms, and the way it highlights the set of communities formed over the network.


title: Representation Dependence in Probabilistic Inference

abstract: Non-deductive reasoning systems are often {\em representation dependent}: representing the same situation in two different ways may cause such a system to return two different answers. Some have viewed this as a significant problem. For example, the principle of maximum entropy has been subjected to much criticism due to its representation dependence. There has, however, been almost no work investigating representation dependence. In this paper, we formalize this notion and show that it is not a problem specific to maximum entropy. In fact, we show that any representation-independent probabilistic inference procedure that ignores irrelevant information is essentially entailment, in a precise sense. Moreover, we show that representation independence is incompatible with even a weak default assumption of independence. We then show that invariance under a restricted class of representation changes can form a reasonable compromise between representation independence and other desiderata, and provide a construction of a family of inference procedures that provides such restricted representation independence, using relative entropy.


title: Using virtual processors for SPMD parallel programs

abstract: In this paper I describe some results on the use of virtual processors technology for parallelize some SPMD computational programs. The tested technology is the INTEL Hyper Threading on real processors, and the programs are MATLAB scripts for floating points computation. The conclusions of the work concern on the utility and limits of the used approach. The main result is that using virtual processors is a good technique for improving parallel programs not only for memory-based computations, but in the case of massive disk-storage operations too.


title: A Flexible Pragmatics-driven Language Generator for Animated Agents

abstract: This paper describes the NECA MNLG; a fully implemented Multimodal Natural Language Generation module. The MNLG is deployed as part of the NECA system which generates dialogues between animated agents. The generation module supports the seamless integration of full grammar rules, templates and canned text. The generator takes input which allows for the specification of syntactic, semantic and pragmatic constraints on the output.


title: Towards Automated Generation of Scripted Dialogue: Some Time-Honoured Strategies

abstract: The main aim of this paper is to introduce automated generation of scripted dialogue as a worthwhile topic of investigation. In particular the fact that scripted dialogue involves two layers of communication, i.e., uni-directional communication between the author and the audience of a scripted dialogue and bi-directional pretended communication between the characters featuring in the dialogue, is argued to raise some interesting issues. Our hope is that the combined study of the two layers will forge links between research in text generation and dialogue processing. The paper presents a first attempt at creating such links by studying three types of strategies for the automated generation of scripted dialogue. The strategies are derived from examples of human-authored and naturally occurring dialogue.


title: Dialogue as Discourse: Controlling Global Properties of Scripted Dialogue

abstract: This paper explains why scripted dialogue shares some crucial properties with discourse. In particular, when scripted dialogues are generated by a Natural Language Generation system, the generator can apply revision strategies that cannot normally be used when the dialogue results from an interaction between autonomous agents (i.e., when the dialogue is not scripted). The paper explains that the relevant revision operators are best applied at the level of a dialogue plan and discusses how the generator may decide when to apply a given revision operator.


title: On the Expressibility of Stable Logic Programming

abstract: (We apologize for pidgin LaTeX) Schlipf \cite{sch91} proved that Stable Logic Programming (SLP) solves all $\mathit{NP}$ decision problems. We extend Schlipf's result to prove that SLP solves all search problems in the class $\mathit{NP}$. Moreover, we do this in a uniform way as defined in \cite{mt99}. Specifically, we show that there is a single $\mathrm{DATALOG}^{\neg}$ program $P_{\mathit{Trg}}$ such that given any Turing machine $M$, any polynomial $p$ with non-negative integer coefficients and any input $\sigma$ of size $n$ over a fixed alphabet $\Sigma$, there is an extensional database $\mathit{edb}_{M,p,\sigma}$ such that there is a one-to-one correspondence between the stable models of $\mathit{edb}_{M,p,\sigma} \cup P_{\mathit{Trg}}$ and the accepting computations of the machine $M$ that reach the final state in at most $p(n)$ steps. Moreover, $\mathit{edb}_{M,p,\sigma}$ can be computed in polynomial time from $p$, $\sigma$ and the description of $M$ and the decoding of such accepting computations from its corresponding stable model of $\mathit{edb}_{M,p,\sigma} \cup P_{\mathit{Trg}}$ can be computed in linear time. A similar statement holds for Default Logic with respect to $\Sigma_2^\mathrm{P}$-search problems\footnote{The proof of this result involves additional technical complications and will be a subject of another publication.}.


title: Partitioning schemes for quicksort and quickselect

abstract: We introduce several modifications of the partitioning schemes used in Hoare's quicksort and quickselect algorithms, including ternary schemes which identify keys less or greater than the pivot. We give estimates for the numbers of swaps made by each scheme. Our computational experiments indicate that ternary schemes allow quickselect to identify all keys equal to the selected key at little additional cost.


title: Randomized selection with quintary partitions

abstract: We show that several versions of Floyd and Rivest's algorithm Select for finding the $k$th smallest of $n$ elements require at most $n+\min\{k,n-k\}+o(n)$ comparisons on average and with high probability. This rectifies the analysis of Floyd and Rivest, and extends it to the case of nondistinct elements. Our computational results confirm that Select may be the best algorithm in practice.


title: The Geometric Thickness of Low Degree Graphs

abstract: We prove that the geometric thickness of graphs whose maximum degree is no more than four is two. All of our algorithms run in O(n) time, where n is the number of vertices in the graph. In our proofs, we present an embedding algorithm for graphs with maximum degree three that uses an n x n grid and a more complex algorithm for embedding a graph with maximum degree four. We also show a variation using orthogonal edges for maximum degree four graphs that also uses an n x n grid. The results have implications in graph theory, graph drawing, and VLSI design.


title: Abduction in Well-Founded Semantics and Generalized Stable Models

abstract: Abductive logic programming offers a formalism to declaratively express and solve problems in areas such as diagnosis, planning, belief revision and hypothetical reasoning. Tabled logic programming offers a computational mechanism that provides a level of declarativity superior to that of Prolog, and which has supported successful applications in fields such as parsing, program analysis, and model checking. In this paper we show how to use tabled logic programming to evaluate queries to abductive frameworks with integrity constraints when these frameworks contain both default and explicit negation. The result is the ability to compute abduction over well-founded semantics with explicit negation and answer sets. Our approach consists of a transformation and an evaluation method. The transformation adjoins to each objective literal $O$ in a program, an objective literal $not(O)$ along with rules that ensure that $not(O)$ will be true if and only if $O$ is false. We call the resulting program a {\em dual} program. The evaluation method, \wfsmeth, then operates on the dual program. \wfsmeth{} is sound and complete for evaluating queries to abductive frameworks whose entailment method is based on either the well-founded semantics with explicit negation, or on answer sets. Further, \wfsmeth{} is asymptotically as efficient as any known method for either class of problems. In addition, when abduction is not desired, \wfsmeth{} operating on a dual program provides a novel tabling method for evaluating queries to ground extended programs whose complexity and termination properties are similar to those of the best tabling methods for the well-founded semantics. A publicly available meta-interpreter has been developed for \wfsmeth{} using the XSB system.


title: Acquiring Lexical Paraphrases from a Single Corpus

abstract: This paper studies the potential of identifying lexical paraphrases within a single corpus, focusing on the extraction of verb paraphrases. Most previous approaches detect individual paraphrase instances within a pair (or set) of comparable corpora, each of them containing roughly the same information, and rely on the substantial level of correspondence of such corpora. We present a novel method that successfully detects isolated paraphrase instances within a single corpus without relying on any a-priori structure and information. A comparison suggests that an instance-based approach may be combined with a vector based approach in order to assess better the paraphrase likelihood for many verb pairs.


title: Polyhierarchical Classifications Induced by Criteria Polyhierarchies, and Taxonomy Algebra

abstract: A new approach to the construction of general persistent polyhierarchical classifications is proposed. It is based on implicit description of category polyhierarchy by a generating polyhierarchy of classification criteria. Similarly to existing approaches, the classification categories are defined by logical functions encoded by attributive expressions. However, the generating hierarchy explicitly predefines domains of criteria applicability, and the semantics of relations between categories is invariant to changes in the universe composition, extending variety of criteria, and increasing their cardinalities. The generating polyhierarchy is an independent, compact, portable, and re-usable information structure serving as a template classification. It can be associated with one or more particular sets of objects, included in more general classifications as a standard component, or used as a prototype for more comprehensive classifications. The approach dramatically simplifies development and unplanned modifications of persistent hierarchical classifications compared with tree, DAG, and faceted schemes. It can be efficiently implemented in common DBMS, while considerably reducing amount of computer resources required for storage, maintenance, and use of complex polyhierarchies.


title: Part-of-Speech Tagging with Minimal Lexicalization

abstract: We use a Dynamic Bayesian Network to represent compactly a variety of sublexical and contextual features relevant to Part-of-Speech (PoS) tagging. The outcome is a flexible tagger (LegoTag) with state-of-the-art performance (3.6% error on a benchmark corpus). We explore the effect of eliminating redundancy and radically reducing the size of feature vocabularies. We find that a small but linguistically motivated set of suffixes results in improved cross-corpora generalization. We also show that a minimal lexicon limited to function words is sufficient to ensure reasonable performance.


title: Initial Experiences Re-Exporting Duplicate and Similarity Computation with an OAI-PMH aggregator

abstract: The proliferation of the Open Archive Initiative Protocol for Metadata Harvesting (OAI-PMH) has resulted in the creation of a large number of service providers, all harvesting from either data providers or aggregators. If data were available regarding the similarity of metadata records, service providers could track redundant records across harvests from multiple sources as well as provide additional end-user services. Due to the large number of metadata formats and the diverse mapping strategies employed by data providers, similarity calculation requirements necessitate the use of information retrieval strategies. We describe an OAI-PMH aggregator implementation that uses the optional ``<about>'' container to re-export the results of similarity calculations. Metadata records (3751) were harvested from a NASA data provider and similarities for the records were computed. The results were useful for detecting duplicates, similarities and metadata errors.


title: A Comparison of Cryptography Courses

abstract: The author taught two courses on cryptography, one at Duke University aimed at non-mathematics majors and one at Rose-Hulman Institute of Technology aimed at mathematics and computer science majors. Both tried to incorporate technical and societal aspects of cryptography, with varying emphases. This paper will discuss the strengths and weaknesses of both courses and compare the differences in the author's approach.


title: Randomized selection with tripartitioning

abstract: We show that several versions of Floyd and Rivest's algorithm Select [Comm.\ ACM {\bf 18} (1975) 173] for finding the $k$th smallest of $n$ elements require at most $n+\min\{k,n-k\}+o(n)$ comparisons on average, even when equal elements occur. This parallels our recent analysis of another variant due to Floyd and Rivest [Comm. ACM {\bf 18} (1975) 165--172]. Our computational results suggest that both variants perform well in practice, and may compete with other selection methods, such as Hoare's Find or quickselect with median-of-3 pivots.


title: Cyborg Systems as Platforms for Computer-Vision Algorithm-Development for Astrobiology

abstract: Employing the allegorical imagery from the film "The Matrix", we motivate and discuss our `Cyborg Astrobiologist' research program. In this research program, we are using a wearable computer and video camcorder in order to test and train a computer-vision system to be a field-geologist and field-astrobiologist.


title: About Unitary Rating Score Constructing

abstract: It is offered to pool test points of different subjects and different aspects of the same subject together in order to get the unitary rating score, by the way of nonlinear transformation of indicator points in accordance with Zipf's distribution. It is proposed to use the well-studied distribution of Intellectuality Quotient IQ as the reference distribution for latent variable "progress in studies".


title: Cluster computing performances using virtual processors and mathematical software

abstract: In this paper I describe some results on the use of virtual processors technology for parallelize some SPMD computational programs in a cluster environment. The tested technology is the INTEL Hyper Threading on real processors, and the programs are MATLAB 6.5 Release 13 scripts for floating points computation. By the use of this technology, I tested that a cluster can run with benefit a number of concurrent processes double the amount of physical processors. The conclusions of the work concern on the utility and limits of the used approach. The main result is that using virtual processors is a good technique for improving parallel programs not only for memory-based computations, but in the case of massive disk-storage operations too.


title: Design of a Community-based Translation Center

abstract: Interfaces that support multi-lingual content can reach a broader community. We wish to extend the reach of CITIDEL, a digital library for computing education materials, to support multiple languages. By doing so, we hope that it will increase the number of users, and in turn the number of resources. This paper discusses three approaches to translation (automated translation, developer-based, and community-based), and a brief evaluation of these approaches. It proposes a design for an online community translation center where volunteers help translate interface components and educational materials available in CITIDEL.


title: Algorithm xxx: Modified Bessel functions of imaginary order and positive argument

abstract: Fortran 77 programs for the computation of modified Bessel functions of purely imaginary order are presented. The codes compute the functions $K_{ia}(x)$, $L_{ia}(x)$ and their derivatives for real $a$ and positive $x$; these functions are independent solutions of the differential equation $x^2 w'' +x w' +(a^2 -x^2)w=0$. The code also computes exponentially scaled functions. The range of computation is $(x,a)\in (0,1500]\times [-1500,1500]$ when scaled functions are considered and it is larger than $(0,500]\times [-400,400]$ for standard IEEE double precision arithmetic. The relative accuracy is better than $10^{-13}$ in the range $(0,200]\times [-200,200]$ and close to $10^{-12}$ in $(0,1500]\times [-1500,1500]$.


title: Unifying Computing and Cognition: The SP Theory and its Applications

abstract: This book develops the conjecture that all kinds of information processing in computers and in brains may usefully be understood as "information compression by multiple alignment, unification and search". This "SP theory", which has been under development since 1987, provides a unified view of such things as the workings of a universal Turing machine, the nature of 'knowledge', the interpretation and production of natural language, pattern recognition and best-match information retrieval, several kinds of probabilistic reasoning, planning and problem solving, unsupervised learning, and a range of concepts in mathematics and logic. The theory also provides a basis for the design of an 'SP' computer with several potential advantages compared with traditional digital computers.


title: On the Cost of Participating in a Peer-to-Peer Network

abstract: In this paper, we model the cost incurred by each peer participating in a peer-to-peer network. Such a cost model allows to gauge potential disincentives for peers to collaborate, and provides a measure of the ``total cost'' of a network, which is a possible benchmark to distinguish between proposals. We characterize the cost imposed on a node as a function of the experienced load and the node connectivity, and show how our model applies to a few proposed routing geometries for distributed hash tables (DHTs). We further outline a number of open questions this research has raised.


title: Heuristic average-case analysis of the backtrack resolution of random 3-Satisfiability instances

abstract: An analysis of the average-case complexity of solving random 3-Satisfiability (SAT) instances with backtrack algorithms is presented. We first interpret previous rigorous works in a unifying framework based on the statistical physics notions of dynamical trajectories, phase diagram and growth process. It is argued that, under the action of the Davis--Putnam--Loveland--Logemann (DPLL) algorithm, 3-SAT instances are turned into 2+p-SAT instances whose characteristic parameters (ratio alpha of clauses per variable, fraction p of 3-clauses) can be followed during the operation, and define resolution trajectories. Depending on the location of trajectories in the phase diagram of the 2+p-SAT model, easy (polynomial) or hard (exponential) resolutions are generated. Three regimes are identified, depending on the ratio alpha of the 3-SAT instance to be solved. Lower sat phase: for small ratios, DPLL almost surely finds a solution in a time growing linearly with the number N of variables. Upper sat phase: for intermediate ratios, instances are almost surely satisfiable but finding a solution requires exponential time (2 ^ (N omega) with omega>0) with high probability. Unsat phase: for large ratios, there is almost always no solution and proofs of refutation are exponential. An analysis of the growth of the search tree in both upper sat and unsat regimes is presented, and allows us to estimate omega as a function of alpha. This analysis is based on an exact relationship between the average size of the search tree and the powers of the evolution operator encoding the elementary steps of the search heuristic.


title: Algebraic Elimination of epsilon-transitions

abstract: We present here algebraic formulas associating a k-automaton to a k-epsilon-automaton. The existence depends on the definition of the star of matrices and of elements in the semiring k. For this reason, we present the theorem which allows the transformation of k-epsilon-automata into k-automata. The two automata have the same behaviour.


title: Verification of Process Rewrite Systems in normal form

abstract: We consider the problem of model--checking for Process Rewrite Systems (PRSs) in normal form. In a PRS in normal form every rewrite rule either only deals with procedure calls and procedure termination, possibly with value return, (this kind of rules allows to capture Pushdown Processes), or only deals with dynamic activation of processes and synchronization (this kind of rules allows to capture Petri Nets). The model-checking problem for PRSs and action-based linear temporal logic (ALTL) is undecidable. However, decidability of model--checking for PRSs and some interesting fragment of ALTL remains an open question. In this paper we state decidability results concerning generalized acceptance properties about infinite derivations (infinite term rewritings) in PRSs in normal form. As a consequence, we obtain decidability of the model-checking (restricted to infinite runs) for PRSs in normal form and a meaningful fragment of ALTL.


title: Nested Intervals with Farey Fractions

abstract: Relational Databases are universally conceived as an advance over their predecessors Network and Hierarchical models. Superior in every querying respect, they turned out to be surprisingly incomplete when modeling transitive dependencies. Almost every couple of months a question how to model a tree in the database surfaces at comp.database.theory newsgroup. This article completes a series of articles exploring Nested Intervals Model. Previous articles introduced tree encoding with Binary Rational Numbers. However, binary encoding grows exponentially, both in breadth and in depth. In this article, we'll leverage Farey fractions in order to overcome this problem. We'll also demonstrate that our implementation scales to a tree with 1M nodes.


title: Query Answering in Peer-to-Peer Data Exchange Systems

abstract: The problem of answering queries posed to a peer who is a member of a peer-to-peer data exchange system is studied. The answers have to be consistent wrt to both the local semantic constraints and the data exchange constraints with other peers; and must also respect certain trust relationships between peers. A semantics for peer consistent answers under exchange constraints and trust relationships is introduced and some techniques for obtaining those answers are presented.


title: Generalized Strong Preservation by Abstract Interpretation

abstract: Standard abstract model checking relies on abstract Kripke structures which approximate concrete models by gluing together indistinguishable states, namely by a partition of the concrete state space. Strong preservation for a specification language L encodes the equivalence of concrete and abstract model checking of formulas in L. We show how abstract interpretation can be used to design abstract models that are more general than abstract Kripke structures. Accordingly, strong preservation is generalized to abstract interpretation-based models and precisely related to the concept of completeness in abstract interpretation. The problem of minimally refining an abstract model in order to make it strongly preserving for some language L can be formulated as a minimal domain refinement in abstract interpretation in order to get completeness w.r.t. the logical/temporal operators of L. It turns out that this refined strongly preserving abstract model always exists and can be characterized as a greatest fixed point. As a consequence, some well-known behavioural equivalences, like bisimulation, simulation and stuttering, and their corresponding partition refinement algorithms can be elegantly characterized in abstract interpretation as completeness properties and refinements.


title: Better Foreground Segmentation Through Graph Cuts

abstract: For many tracking and surveillance applications, background subtraction provides an effective means of segmenting objects moving in front of a static background. Researchers have traditionally used combinations of morphological operations to remove the noise inherent in the background-subtracted result. Such techniques can effectively isolate foreground objects, but tend to lose fidelity around the borders of the segmentation, especially for noisy input. This paper explores the use of a minimum graph cut algorithm to segment the foreground, resulting in qualitatively and quantitiatively cleaner segmentations. Experiments on both artificial and real data show that the graph-based method reduces the error around segmented foreground objects. A MATLAB code implementation is available at http://www.cs.smith.edu/~nhowe/research/code/#fgseg


title: Factor Temporal Prognosis of Tick-Borne Encephalitis Foci Functioning on the South of Russian Far East

abstract: A method of temporal factor prognosis of TE (tick-borne encephalitis) infection has been developed. The high precision of the prognosis results for a number of geographical regions of Primorsky Krai has been achieved. The method can be applied not only to epidemiological research but also to others.


title: Using biased coins as oracles

abstract: While it is well known that a Turing machine equipped with the ability to flip a fair coin cannot compute more that a standard Turing machine, we show that this is not true for a biased coin. Indeed, any oracle set $X$ may be coded as a probability $p_{X}$ such that if a Turing machine is given a coin which lands heads with probability $p_{X}$ it can compute any function recursive in $X$ with arbitrarily high probability. We also show how the assumption of a non-recursive bias can be weakened by using a sequence of increasingly accurate recursive biases or by choosing the bias at random from a distribution with a non-recursive mean. We conclude by briefly mentioning some implications regarding the physical realisability of such methods.


title: Presynaptic modulation as fast synaptic switching: state-dependent modulation of task performance

abstract: Neuromodulatory receptors in presynaptic position have the ability to suppress synaptic transmission for seconds to minutes when fully engaged. This effectively alters the synaptic strength of a connection. Much work on neuromodulation has rested on the assumption that these effects are uniform at every neuron. However, there is considerable evidence to suggest that presynaptic regulation may be in effect synapse-specific. This would define a second "weight modulation" matrix, which reflects presynaptic receptor efficacy at a given site. Here we explore functional consequences of this hypothesis. By analyzing and comparing the weight matrices of networks trained on different aspects of a task, we identify the potential for a low complexity "modulation matrix", which allows to switch between differently trained subtasks while retaining general performance characteristics for the task. This means that a given network can adapt itself to different task demands by regulating its release of neuromodulators. Specifically, we suggest that (a) a network can provide optimized responses for related classification tasks without the need to train entirely separate networks and (b) a network can blend a "memory mode" which aims at reproducing memorized patterns and a "novelty mode" which aims to facilitate classification of new patterns. We relate this work to the known effects of neuromodulators on brain-state dependent processing.


title: A correct, precise and efficient integration of set-sharing, freeness and linearity for the analysis of finite and rational tree languages

abstract: It is well-known that freeness and linearity information positively interact with aliasing information, allowing both the precision and the efficiency of the sharing analysis of logic programs to be improved. In this paper we present a novel combination of set-sharing with freeness and linearity information, which is characterized by an improved abstract unification operator. We provide a new abstraction function and prove the correctness of the analysis for both the finite tree and the rational tree cases. Moreover, we show that the same notion of redundant information as identified in (Bagnara et al. 2002; Zaffanella et al. 2002) also applies to this abstract domain combination: this allows for the implementation of an abstract unification operator running in polynomial time and achieving the same precision on all the considered observable properties.


title: Enhanced sharing analysis techniques: a comprehensive evaluation

abstract: Sharing, an abstract domain developed by D. Jacobs and A. Langen for the analysis of logic programs, derives useful aliasing information. It is well-known that a commonly used core of techniques, such as the integration of Sharing with freeness and linearity information, can significantly improve the precision of the analysis. However, a number of other proposals for refined domain combinations have been circulating for years. One feature that is common to these proposals is that they do not seem to have undergone a thorough experimental evaluation even with respect to the expected precision gains. In this paper we experimentally evaluate: helping Sharing with the definitely ground variables found using Pos, the domain of positive Boolean formulas; the incorporation of explicit structural information; a full implementation of the reduced product of Sharing and Pos; the issue of reordering the bindings in the computation of the abstract mgu; an original proposal for the addition of a new mode recording the set of variables that are deemed to be ground or free; a refined way of using linearity to improve the analysis; the recovery of hidden information in the combination of Sharing with freeness information. Finally, we discuss the issue of whether tracking compoundness allows the computation of more sharing information.


title: Surface Triangulation -- The Metric Approach

abstract: We embark in a program of studying the problem of better approximating surfaces by triangulations(triangular meshes) by considering the approximating triangulations as finite metric spaces and the target smooth surface as their Haussdorff-Gromov limit. This allows us to define in a more natural way the relevant elements, constants and invariants s.a. principal directions and principal values, Gaussian and Mean curvature, etc. By a "natural way" we mean an intrinsic, discrete, metric definitions as opposed to approximating or paraphrasing the differentiable notions. In this way we hope to circumvent computational errors and, indeed, conceptual ones, that are often inherent to the classical, "numerical" approach. In this first study we consider the problem of determining the Gaussian curvature of a polyhedral surface, by using the {\em embedding curvature} in the sense of Wald (and Menger). We present two modalities of employing these definitions for the computation of Gaussian curvature.


title: A system for reflection in C++

abstract: Object-oriented programming languages such as Java and Objective C have become popular for implementing agent-based and other object-based simulations since objects in those languages can {\em reflect} (i.e. make runtime queries of an object's structure). This allows, for example, a fairly trivial {\em serialisation} routine (conversion of an object into a binary representation that can be stored or passed over a network) to be written. However C++ does not offer this ability, as type information is thrown away at compile time. Yet C++ is often a preferred development environment, whether for performance reasons or for its expressive features such as operator overloading. In this paper, we present the {\em Classdesc} system which brings many of the benefits of object reflection to C++.


title: Running C++ models undet the Swarm environment

abstract: Objective-C is still the language of choice if users want to run their simulation efficiently under the Swarm environment since the Swarm environment itself was written in Objective-C. The language is a fast, object-oriented and easy to learn. However, the language is less well known than, less expressive than, and lacks support for many important features of C++ (eg. OpenMP for high performance computing application). In this paper, we present a methodology and software tools that we have developed for auto generating an Objective-C object template (and all the necessary interfacing functions) from a given C++ model, utilising the Classdesc's object description technology, so that the C++ model can both be run and accessed under the Objective-C and C++ environments. We also present a methodology for modifying an existing Swarm application to make part of the model (eg. the heatbug's step method) run under the C++ environment.


title: EcoLab: Agent Based Modeling for C++ programmers

abstract: \EcoLab{} is an agent based modeling system for C++ programmers, strongly influenced by the design of Swarm. This paper is just a brief outline of \EcoLab's features, more details can be found in other published articles, documentation and source code from the \EcoLab{} website.


title: ClassdescMP: Easy MPI programming in C++

abstract: ClassdescMP is a distributed memory parallel programming system for use with C++ and MPI. It uses the Classdesc reflection system to ease the task of building complicated messages to be sent between processes. It doesn't hide the underlying MPI API, so it is an augmentation of MPI capabilities. Users can still call standard MPI function calls if needed for performance reasons.


title: Automated Resolution of Noisy Bibliographic References

abstract: We describe a system used by the NASA Astrophysics Data System to identify bibliographic references obtained from scanned article pages by OCR methods with records in a bibliographic database. We analyze the process generating the noisy references and conclude that the three-step procedure of correcting the OCR results, parsing the corrected string and matching it against the database provides unsatisfactory results. Instead, we propose a method that allows a controlled merging of correction, parsing and matching, inspired by dependency grammars. We also report on the effectiveness of various heuristics that we have employed to improve recall.


title: Dynamic Linking of Smart Digital Objects Based on User Navigation Patterns

abstract: We discuss a methodology to dynamically generate links among digital objects by means of an unsupervised learning mechanism which analyzes user link traversal patterns. We performed an experiment with a test bed of 150 complex data objects, referred to as buckets. Each bucket manages its own content, provides methods to interact with users and individually maintains a set of links to other buckets. We demonstrate that buckets were capable of dynamically adjusting their links to other buckets according to user link selections, thereby generating a meaningful network of bucket relations. Our results indicate such adaptive networks of linked buckets approximate the collective link preferences of a community of user


title: Pseudorandom number generation by $p$-adic ergodic transformations

abstract: The paper study counter-dependent pseudorandom generators; the latter are generators such that their state transition function (and output function) is being modified dynamically while working: For such a generator the recurrence sequence of states satisfies a congruence $x_{i+1}\equiv f_i(x_i)\pmod{2^n}$, while its output sequence is of the form $z_{i}=F_i(u_i)$. The paper introduces techniques and constructions that enable one to compose generators that output uniformly distributed sequences of a maximum period length and with high linear and 2-adic spans. The corresponding stream chipher is provably strong against a known plaintext attack (up to a plausible conjecture). Both state transition function and output function could be key-dependent, so the only information available to a cryptanalyst is that these functions belong to some (exponentially large) class. These functions are compositions of standard machine instructions (such as addition, multiplication, bitwise logical operations, etc.) The compositions should satisfy rather loose conditions; so the corresponding generators are flexible enough and could be easily implemented as computer programs.


title: Mobile Re-Finding of Web Information Using a Voice Interface

abstract: Mobile access to information is a considerable problem for many users, especially to information found on the Web. In this paper, we explore how a voice-controlled service, accessible by telephone, could support mobile users' needs for refinding specific information previously found on the Web. We outline challenges in creating such a service and describe architectural and user interfaces issues discovered in an exploratory prototype we built called WebContext. We also present the results of a study, motivated by our experience with WebContext, to explore what people remember about information that they are trying to refind and how they express information refinding requests in a collaborative conversation. As part of the study, we examine how end-usercreated Web page annotations can be used to help support mobile information re-finding. We observed the use of URLs, page titles, and descriptions of page contents to help identify waypoints in the search process. Furthermore, we observed that the annotations were utilized extensively, indicating that explicitly added context by the user can play an important role in re-finding.


title: Deciding Disjunctive Linear Arithmetic with SAT

abstract: Disjunctive Linear Arithmetic (DLA) is a major decidable theory that is supported by almost all existing theorem provers. The theory consists of Boolean combinations of predicates of the form $\Sigma_{j=1}^{n}a_j\cdot x_j \le b$, where the coefficients $a_j$, the bound $b$ and the variables $x_1 >... x_n$ are of type Real ($\mathbb{R}$). We show a reduction to propositional logic from disjunctive linear arithmetic based on Fourier-Motzkin elimination. While the complexity of this procedure is not better than competing techniques, it has practical advantages in solving verification problems. It also promotes the option of deciding a combination of theories by reducing them to this logic. Results from experiments show that this method has a strong advantage over existing techniques when there are many disjunctions in the formula.


title: Semantic Optimization of Preference Queries

abstract: The notion of preference is becoming more and more ubiquitous in present-day information systems. Preferences are primarily used to filter and personalize the information reaching the users of such systems. In database systems, preferences are usually captured as preference relations that are used to build preference queries. In our approach, preference queries are relational algebra or SQL queries that contain occurrences of the winnow operator ("find the most preferred tuples in a given relation"). We present here a number of semantic optimization techniques applicable to preference queries. The techniques make use of integrity constraints, and make it possible to remove redundant occurrences of the winnow operator and to apply a more efficient algorithm for the computation of winnow. We also study the propagation of integrity constraints in the result of the winnow. We have identified necessary and sufficient conditions for the applicability of our techniques, and formulated those conditions as constraint satisfiability problems.


title: Baptista-type chaotic cryptosystems: Problems and countermeasures

abstract: In 1998, M. S. Baptista proposed a chaotic cryptosystem, which has attracted much attention from the chaotic cryptography community: some of its modifications and also attacks have been reported in recent years. In [Phys. Lett. A 307 (2003) 22], we suggested a method to enhance the security of Baptista-type cryptosystem, which can successfully resist all proposed attacks. However, the enhanced Baptista-type cryptosystem has a nontrivial defect, which produces errors in the decrypted data with a generally small but nonzero probability, and the consequent error propagation exists. In this Letter, we analyze this defect and discuss how to rectify it. In addition, we point out some newly-found problems existing in all Baptista-type cryptosystems and consequently propose corresponding countermeasures.


title: Improved randomized selection

abstract: We show that several versions of Floyd and Rivest's improved algorithm Select for finding the $k$th smallest of $n$ elements require at most $n+\min\{k,n-k\}+O(n^{1/2}\ln^{1/2}n)$ comparisons on average and with high probability. This rectifies the analysis of Floyd and Rivest, and extends it to the case of nondistinct elements. Encouraging computational results on large median-finding problems are reported.


title: MammoGrid: Large-Scale Distributed Mammogram Analysis

abstract: Breast cancer as a medical condition and mammograms as images exhibit many dimensions of variability across the population. Similarly, the way diagnostic systems are used and maintained by clinicians varies between imaging centres and breast screening programmes, and so does the appearance of the mammograms generated. A distributed database that reflects the spread of pathologies across the population is an invaluable tool for the epidemiologist and the understanding of the variation in image acquisition protocols is essential to a radiologist in a screening programme. Exploiting emerging grid technology, the aim of the MammoGrid [1] project is to develop a Europe-wide database of mammograms that will be used to investigate a set of important healthcare applications and to explore the potential of the grid to support effective co-working between healthcare professionals.


title: An Integrated Approach for Extraction of Objects from XML and Transformation to Heterogeneous Object Oriented Databases

abstract: CERN's (European Organization for Nuclear Research) WISDOM project uses XML for the replication of data between different data repositories in a heterogeneous operating system environment. For exchanging data from Web-resident databases, the data needs to be transformed into XML and back to the database format. Many different approaches are employed to do this transformation. This paper addresses issues that make this job more efficient and robust than existing approaches. It incorporates the World Wide Web Consortium (W3C) XML Schema specification in the database-XML relationship. Incorporation of the XML Schema exhibits significant improvements in XML content usage and reduces the limitations of DTD-based database XML services. Secondly the paper explores the possibility of database independent transformation of data between XML and different databases. It proposes a standard XML format that every serialized object should follow. This makes it possible to use objects of heterogeneous database seamlessly using XML.


title: A Use-Case Driven Approach in Requirements Engineering : The Mammogrid Project

abstract: We report on the application of the use-case modeling technique to identify and specify the user requirements of the MammoGrid project in an incremental and controlled iterative approach. Modeling has been carried out in close collaboration with clinicians and radiologists with no prior experience of use cases. The study reveals the advantages and limitations of applying this technique to requirements specification in the domains of breast cancer screening and mammography research, with implications for medical imaging more generally. In addition, this research has shown a return on investment in use-case modeling in shorter gaps between phases of the requirements engineering process. The qualitative result of this analysis leads us to propose that a use-case modeling approach may result in reducing the cycle of the requirements engineering process for medical imaging.


title: Resolving Clinicians Queries Across a Grids Infrastructure

abstract: The past decade has witnessed order of magnitude increases in computing power, data storage capacity and network speed, giving birth to applications which may handle large data volumes of increased complexity, distributed over the Internet. Grids computing promises to resolve many of the difficulties in facilitating medical image analysis to allow radiologists to collaborate without having to co-locate. The EU-funded MammoGrid project aims to investigate the feasibility of developing a Grid-enabled European database of mammograms and provide an information infrastructure which federates multiple mammogram databases. This will enable clinicians to develop new common, collaborative and co-operative approaches to the analysis of mammographic data. This paper focuses on one of the key requirements for large-scale distributed mammogram analysis: resolving queries across a grid-connected federation of images.


title: Encapsulation for Practical Simplification Procedures

abstract: ACL2 was used to prove properties of two simplification procedures. The procedures differ in complexity but solve the same programming problem that arises in the context of a resolution/paramodulation theorem proving system. Term rewriting is at the core of the two procedures, but details of the rewriting procedure itself are irrelevant. The ACL2 encapsulate construct was used to assert the existence of the rewriting function and to state some of its properties. Termination, irreducibility, and soundness properties were established for each procedure. The availability of the encapsulation mechanism in ACL2 is considered essential to rapid and efficient verification of this kind of algorithm.


title: Accurately modeling the Internet topology

abstract: Based on measurements of the Internet topology data, we found out that there are two mechanisms which are necessary for the correct modeling of the Internet topology at the Autonomous Systems (AS) level: the Interactive Growth of new nodes and new internal links, and a nonlinear preferential attachment, where the preference probability is described by a positive-feedback mechanism. Based on the above mechanisms, we introduce the Positive-Feedback Preference (PFP) model which accurately reproduces many topological properties of the AS-level Internet, including: degree distribution, rich-club connectivity, the maximum degree, shortest path length, short cycles, disassortative mixing and betweenness centrality. The PFP model is a phenomenological model which provides a novel insight into the evolutionary dynamics of real complex networks.


title: A Knowledge-Theoretic Analysis of Uniform Distributed Coordination and Failure Detectors

abstract: It is shown that, in a precise sense, if there is no bound on the number of faulty processes in a system with unreliable but fair communication, Uniform Distributed Coordination (UDC) can be attained if and only if a system has perfect failure detectors. This result is generalized to the case where there is a bound t on the number of faulty processes. It is shown that a certain type of generalized failure detector is necessary and sufficient for achieving UDC in a context with at most t faulty processes. Reasoning about processes' knowledge as to which other processes are faulty plays a key role in the analysis.


title: Corollaries on the fixpoint completion: studying the stable semantics by means of the Clark completion

abstract: The fixpoint completion fix(P) of a normal logic program P is a program transformation such that the stable models of P are exactly the models of the Clark completion of fix(P). This is well-known and was studied by Dung and Kanchanasut (1989). The correspondence, however, goes much further: The Gelfond-Lifschitz operator of P coincides with the immediate consequence operator of fix(P), as shown by Wendt (2002), and even carries over to standard operators used for characterizing the well-founded and the Kripke-Kleene semantics. We will apply this knowledge to the study of the stable semantics, and this will allow us to almost effortlessly derive new results concerning fixed-point and metric-based semantics, and neural-symbolic integration.


title: Self-Organising Networks for Classification: developing Applications to Science Analysis for Astroparticle Physics

abstract: Physics analysis in astroparticle experiments requires the capability of recognizing new phenomena; in order to establish what is new, it is important to develop tools for automatic classification, able to compare the final result with data from different detectors. A typical example is the problem of Gamma Ray Burst detection, classification, and possible association to known sources: for this task physicists will need in the next years tools to associate data from optical databases, from satellite experiments (EGRET, GLAST), and from Cherenkov telescopes (MAGIC, HESS, CANGAROO, VERITAS).