title: A Preliminary Study for the development of an Early Method for the Measurement in Function Points of a Software Product

abstract: The Function Points Analysis (FPA) of A.J. Albrecht is a method to determine the functional size of software products. The International Function Point Users Group, (IFPUG), establishes the FPA like a standard in the software functional size measurement. The IFPUG [3] [4] method follows the Albrecht's method and incorporates in its succesive versions modifications to the rules and hints with the intention of improving it [7]. The required documentation level to apply the method is the functional specification which corresponds to level I in the Rudolph's clasification [8]. This documentation is avalaible with some difficulty for those companies which are dedicated to develop software for third parties when they have to prepare the appropiate budget for this development. Then, we face the need of developing an early method [6] [9] for measuring the functional size of a software product that we will name to abbreviate it Early Method or EFPM (Early Function Point Method). The required documentation to apply the EFPM would be the User Requirements or some analogous documentations. This is a part of a research work now in process in Oviedo University. In this article we only show the following, results: From the measurements of a set of projects using the IFPUG method v. 4.1 we obtain the linear correlation coefficients between the total number of Function Points for each project and the counters of the ILFs number, ILFs+EIFs number and EIs+EOs+EQs number. Using the preliminary results we compute the regression functions. This results we will allow us to determine the factors to be considered in the development of EFPM and to estimate the function points.


title: Perspects in astrophysical databases

abstract: Astrophysics has become a domain extremely rich of scientific data. Data mining tools are needed for information extraction from such large datasets. This asks for an approach to data management emphasizing the efficiency and simplicity of data access; efficiency is obtained using multidimensional access methods and simplicity is achieved by properly handling metadata. Moreover, clustering and classification techniques on large datasets pose additional requirements in terms of computation and memory scalability and interpretability of results. In this study we review some possible solutions.


title: Alchemi: A .NET-based Grid Computing Framework and its Integration into Global Grids

abstract: Computational grids that couple geographically distributed resources are becoming the de-facto computing platform for solving large-scale problems in science, engineering, and commerce. Software to enable grid computing has been primarily written for Unix-class operating systems, thus severely limiting the ability to effectively utilize the computing resources of the vast majority of desktop computers i.e. those running variants of the Microsoft Windows operating system. Addressing Windows-based grid computing is particularly important from the software industry's viewpoint where interest in grids is emerging rapidly. Microsoft's .NET Framework has become near-ubiquitous for implementing commercial distributed systems for Windows-based platforms, positioning it as the ideal platform for grid computing in this context. In this paper we present Alchemi, a .NET-based grid computing framework that provides the runtime machinery and programming environment required to construct desktop grids and develop grid applications. It allows flexible application composition by supporting an object-oriented grid application programming model in addition to a grid job model. Cross-platform support is provided via a web services interface and a flexible execution model supports dedicated and non-dedicated (voluntary) execution by grid nodes.


title: P2P Networks for Content Sharing

abstract: Peer-to-peer (P2P) technologies have been widely used for content sharing, popularly called "file-swapping" networks. This chapter gives a broad overview of content sharing P2P technologies. It starts with the fundamental concept of P2P computing followed by the analysis of network topologies used in peer-to-peer systems. Next, three milestone peer-to-peer technologies: Napster, Gnutella, and Fasttrack are explored in details, and they are finally concluded with the comparison table in the last section.


title: The Munich Rent Advisor: A Success for Logic Programming on the Internet

abstract: Most cities in Germany regularly publish a booklet called the {\em Mietspiegel}. It basically contains a verbal description of an expert system. It allows the calculation of the estimated fair rent for a flat. By hand, one may need a weekend to do so. With our computerized version, the {\em Munich Rent Advisor}, the user just fills in a form in a few minutes and the rent is calculated immediately. We also extended the functionality and applicability of the {\em Mietspiegel} so that the user need not answer all questions on the form. The key to computing with partial information using high-level programming was to use constraint logic programming. We rely on the internet, and more specifically the World Wide Web, to provide this service to a broad user group. More than ten thousand people have used our service in the last three years. This article describes the experiences in implementing and using the {\em Munich Rent Advisor}. Our results suggests that logic programming with constraints can be an important ingredient in intelligent internet systems.


title: Geometrical Complexity of Classification Problems

abstract: Despite encouraging recent progresses in ensemble approaches, classification methods seem to have reached a plateau in development. Further advances depend on a better understanding of geometrical and topological characteristics of point sets in high-dimensional spaces, the preservation of such characteristics under feature transformations and sampling processes, and their interaction with geometrical models used in classifiers. We discuss an attempt to measure such properties from data sets and relate them to classifier accuracies.


title: A Numerical Example on the Principles of Stochastic Discrimination

abstract: Studies on ensemble methods for classification suffer from the difficulty of modeling the complementary strengths of the components. Kleinberg's theory of stochastic discrimination (SD) addresses this rigorously via mathematical notions of enrichment, uniformity, and projectability of an ensemble. We explain these concepts via a very simple numerical example that captures the basic principles of the SD theory and method. We focus on a fundamental symmetry in point set covering that is the key observation leading to the foundation of the theory. We believe a better understanding of the SD method will lead to developments of better tools for analyzing other ensemble methods.


title: Automatically Generating Interfaces for Personalized Interaction with Digital Libraries

abstract: We present an approach to automatically generate interfaces supporting personalized interaction with digital libraries; these interfaces augment the user-DL dialog by empowering the user to (optionally) supply out-of-turn information during an interaction, flatten or restructure the dialog, and enquire about dialog options. Interfaces generated using this approach for CITIDEL are described.


title: A Service-Based Approach for Managing Mammography Data

abstract: Grid-based technologies are emerging as a potential open-source standards-based solution for managing and collabo-rating distributed resources. In view of these new computing solutions, the Mammogrid project is developing a service-based and Grid-aware application which manages a Euro-pean-wide database of mammograms. Medical conditions such as breast cancer, and mammograms as images, are ex-tremely complex with many dimensions of variability across the population. An effective solution for the management of disparate mammogram data sources is a federation of autonomous multi-centre sites which transcends national boundaries. The Mammogrid solution utilizes the Grid tech-nologies to integrate geographically distributed data sets. The Mammogrid application will explore the potential of the Grid to support effective co-working among radiologists through-out the EU. This paper outlines the Mammogrid service-based approach in managing a federation of grid-connected mam-mography databases.


title: Pattern Reification as the Basis for Description-Driven Systems

abstract: One of the main factors driving object-oriented software development for information systems is the requirement for systems to be tolerant to change. To address this issue in designing systems, this paper proposes a pattern-based, object-oriented, description-driven system (DDS) architecture as an extension to the standard UML four-layer meta-model. A DDS architecture is proposed in which aspects of both static and dynamic systems behavior can be captured via descriptive models and meta-models. The proposed architecture embodies four main elements - firstly, the adoption of a multi-layered meta-modeling architecture and reflective meta-level architecture, secondly the identification of four data modeling relationships that can be made explicit such that they can be modified dynamically, thirdly the identification of five design patterns which have emerged from practice and have proved essential in providing reusable building blocks for data management, and fourthly the encoding of the structural properties of the five design patterns by means of one fundamental pattern, the Graph pattern. A practical example of this philosophy, the CRISTAL project, is used to demonstrate the use of description-driven data objects to handle system evolution.


title: A perspective on the Healthgrid initiative

abstract: This paper presents a perspective on the Healthgrid initiative which involves European projects deploying pioneering applications of grid technology in the health sector. In the last couple of years, several grid projects have been funded on health related issues at national and European levels. A crucial issue is to maximize their cross fertilization in the context of an environment where data of medical interest can be stored and made easily available to the different actors in healthcare, physicians, healthcare centres and administrations, and of course the citizens. The Healthgrid initiative, represented by the Healthgrid association (http://www.healthgrid.org), was initiated to bring the necessary long term continuity, to reinforce and promote awareness of the possibilities and advantages linked to the deployment of GRID technologies in health. Technologies to address the specific requirements for medical applications are under development. Results from the DataGrid and other projects are given as examples of early applications.


title: Redundancy and Robustness of the AS-level Internet topology and its models

abstract: A comparison between the topological properties of the measured Internet topology, at the autonomous system level (AS graph), and the equivalent graphs generated by two different power law topology generators is presented. Only one of the synthetic generators reproduces the tier connectivity of the AS graph.


title: Efficient and Scalable Barrier over Quadrics and Myrinet with a New NIC-Based Collective Message Passing Protocol

abstract: Modern interconnects often have programmable processors in the network interface that can be utilized to offload communication processing from host CPU. In this paper, we explore different schemes to support collective operations at the network interface and propose a new collective protocol. With barrier as an initial case study, we have demontrated that much of the communication processing can be greatly simplified with this collective protocol. Accordingly, %with our proposed collective processing scheme, we have designed and implemented efficient and scalable NIC-based barrier operations over two high performance interconnects, Quadrics and Myrinet. Our evaluation shows that, over a Quadrics cluster of 8 nodes with ELan3 Network, the NIC-based barrier operation achieves a barrier latency of only 5.60$\mu$s. This result is a 2.48 factor of improvement over the Elanlib tree-based barrier operation. Over a Myrinet cluster of 8 nodes with LANai-XP NIC cards, a barrier latency of 14.20$\mu$s over 8 nodes is achieved. This is a 2.64 factor of improvement over the host-based barrier algorithm. Furthermore, an analytical model developed for the proposed scheme indicates that a NIC-based barrier operation on a 1024-node cluster can be performed with only 22.13$\mu$s latency over Quadrics and with 38.94$\mu$s latency over Myrinet. These results indicate the potential for developing high performance communication subsystems for next generation clusters.


title: The lattice dimension of a graph

abstract: We describe a polynomial time algorithm for, given an undirected graph G, finding the minimum dimension d such that G may be isometrically embedded into the d-dimensional integer lattice Z^d.


title: Mapping Topics and Topic Bursts in PNAS

abstract: Scientific research is highly dynamic. New areas of science continually evolve;others gain or lose importance, merge or split. Due to the steady increase in the number of scientific publications it is hard to keep an overview of the structure and dynamic development of one's own field of science, much less all scientific domains. However, knowledge of hot topics, emergent research frontiers, or change of focus in certain areas is a critical component of resource allocation decisions in research labs, governmental institutions, and corporations. This paper demonstrates the utilization of Kleinberg's burst detection algorithm, co-word occurrence analysis, and graph layout techniques to generate maps that support the identification of major research topics and trends. The approach was applied to analyze and map the complete set of papers published in the Proceedings of the National Academy of Sciences (PNAS) in the years 1982-2001. Six domain experts examined and commented on the resulting maps in an attempt to reconstruct the evolution of major research areas covered by PNAS.


title: Computational complexity and simulation of rare events of Ising spin glasses

abstract: We discuss the computational complexity of random 2D Ising spin glasses, which represent an interesting class of constraint satisfaction problems for black box optimization. Two extremal cases are considered: (1) the +/- J spin glass, and (2) the Gaussian spin glass. We also study a smooth transition between these two extremal cases. The computational complexity of all studied spin glass systems is found to be dominated by rare events of extremely hard spin glass samples. We show that complexity of all studied spin glass systems is closely related to Frechet extremal value distribution. In a hybrid algorithm that combines the hierarchical Bayesian optimization algorithm (hBOA) with a deterministic bit-flip hill climber, the number of steps performed by both the global searcher (hBOA) and the local searcher follow Frechet distributions. Nonetheless, unlike in methods based purely on local search, the parameters of these distributions confirm good scalability of hBOA with local search. We further argue that standard performance measures for optimization algorithms--such as the average number of evaluations until convergence--can be misleading. Finally, our results indicate that for highly multimodal constraint satisfaction problems, such as Ising spin glasses, recombination-based search can provide qualitatively better results than mutation-based search.


title: Parameter-less hierarchical BOA

abstract: The parameter-less hierarchical Bayesian optimization algorithm (hBOA) enables the use of hBOA without the need for tuning parameters for solving each problem instance. There are three crucial parameters in hBOA: (1) the selection pressure, (2) the window size for restricted tournaments, and (3) the population size. Although both the selection pressure and the window size influence hBOA performance, performance should remain low-order polynomial with standard choices of these two parameters. However, there is no standard population size that would work for all problems of interest and the population size must thus be eliminated in a different way. To eliminate the population size, the parameter-less hBOA adopts the population-sizing technique of the parameter-less genetic algorithm. Based on the existing theory, the parameter-less hBOA should be able to solve nearly decomposable and hierarchical problems in quadratic or subquadratic number of function evaluations without the need for setting any parameters whatsoever. A number of experiments are presented to verify scalability of the parameter-less hBOA.


title: Fitness inheritance in the Bayesian optimization algorithm

abstract: This paper describes how fitness inheritance can be used to estimate fitness for a proportion of newly sampled candidate solutions in the Bayesian optimization algorithm (BOA). The goal of estimating fitness for some candidate solutions is to reduce the number of fitness evaluations for problems where fitness evaluation is expensive. Bayesian networks used in BOA to model promising solutions and generate the new ones are extended to allow not only for modeling and sampling candidate solutions, but also for estimating their fitness. The results indicate that fitness inheritance is a promising concept in BOA, because population-sizing requirements for building appropriate models of promising solutions lead to good fitness estimates even if only a small proportion of candidate solutions is evaluated using the actual fitness function. This can lead to a reduction of the number of actual fitness evaluations by a factor of 30 or more.


title: Recycling Computed Answers in Rewrite Systems for Abduction

abstract: In rule-based systems, goal-oriented computations correspond naturally to the possible ways that an observation may be explained. In some applications, we need to compute explanations for a series of observations with the same domain. The question whether previously computed answers can be recycled arises. A yes answer could result in substantial savings of repeated computations. For systems based on classic logic, the answer is YES. For nonmonotonic systems however, one tends to believe that the answer should be NO, since recycling is a form of adding information. In this paper, we show that computed answers can always be recycled, in a nontrivial way, for the class of rewrite procedures that we proposed earlier for logic programs with negation. We present some experimental results on an encoding of the logistics domain.


title: Kolmogorov complexity and symmetric relational structures

abstract: We study partitions of Fra\"{\i}ss\'{e} limits of classes of finite relational structures where the partitions are encoded by infinite binary sequences which are random in the sense of Kolmogorov, Chaitin and Solomonoff. It is shown that partition by a random sequence of a Fra\"{\i}ss\'{e} limit preserves the limit property of the object.


title: Memory As A Monadic Control Construct In Problem-Solving

abstract: Recent advances in programming languages study and design have established a standard way of grounding computational systems representation in category theory. These formal results led to a better understanding of issues of control and side-effects in functional and imperative languages. This framework can be successfully applied to the investigation of the performance of Artificial Intelligence (AI) inference and cognitive systems. In this paper, we delineate a categorical formalisation of memory as a control structure driving performance in inference systems. Abstracting away control mechanisms from three widely used representations of memory in cognitive systems (scripts, production rules and clusters) we explain how categorical triples capture the interaction between learning and problem-solving.


title: Towards a Model-Based Framework for Integrating Usability and Software Engineering Life Cycles

abstract: In this position paper we propose a process model that provides a development infrastructure in which the usability engineering and software engineering life cycles co-exist in complementary roles. We describe the motivation, hurdles, rationale, arguments, and implementation plan for the need, specification, and the usefulness of such a model.


title: The pre-history of quantum computation

abstract: The main ideas behind developments in the theory and technology of quantum computation were formulated in the late 1970s and early 1980s by two physicists in the West and a mathematician in the former Soviet Union. It is not generally known in the West that the subject has roots in the Russian technical literature. The author hopes to present as impartial a synthesis as possible of the early history of thought on this subject. The role of reversible and irreversible computational processes is examined briefly as it relates to the origins of quantum computing and the so-called Information Paradox in physics.


title: Towards a Mathematical Theory of the Delays of the Asynchronous Circuits

abstract: The inequations of the delays of the asynchronous circuits are written, by making use of pseudo-Boolean differential calculus. We consider these efforts to be a possible starting point in the semi-formalized reconstruction of the digital electrical engineering (which is a non-formalized theory).


title: On the Inertia of the Asynchronous Circuits

abstract: We present the bounded delays, the absolute inertia and the relative inertia.


title: Defining the Delays of the Asynchronous Circuits

abstract: We define the delays of a circuit, as well as the properties of determinism, order, time invariance, constancy, symmetry and the serial connection.


title: Examples of Models of the Asynchronous Circuits


title: Anonymity and Information Hiding in Multiagent Systems

abstract: We provide a framework for reasoning about information-hiding requirements in multiagent systems and for reasoning about anonymity in particular. Our framework employs the modal logic of knowledge within the context of the runs and systems framework, much in the spirit of our earlier work on secrecy [Halpern and O'Neill 2002]. We give several definitions of anonymity with respect to agents, actions, and observers in multiagent systems, and we relate our definitions of anonymity to other definitions of information hiding, such as secrecy. We also give probabilistic definitions of anonymity that are able to quantify an observer s uncertainty about the state of the system. Finally, we relate our definitions of anonymity to other formalizations of anonymity and information hiding, including definitions of anonymity in the process algebra CSP and definitions of information hiding using function views.


title: The UPLNC Compiler: Design and Implementation

abstract: The implementation of the compiler of the UPLNC language is presented with a full source code listing.


title: A General Framework for Bounds for Higher-Dimensional Orthogonal Packing Problems

abstract: Higher-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. In the context of a branch-and-bound framework for solving these packing problems to optimality, it is of crucial importance to have good and easy bounds for an optimal solution. Previous efforts have produced a number of special classes of such bounds. Unfortunately, some of these bounds are somewhat complicated and hard to generalize. We present a new approach for obtaining classes of lower bounds for higher-dimensional packing problems; our bounds improve and simplify several well-known bounds from previous literature. In addition, our approach provides an easy framework for proving correctness of new bounds.


title: The Freeze-Tag Problem: How to Wake Up a Swarm of Robots

abstract: An optimization problem that naturally arises in the study of swarm robotics is the Freeze-Tag Problem (FTP) of how to awaken a set of ``asleep'' robots, by having an awakened robot move to their locations. Once a robot is awake, it can assist in awakening other slumbering robots.The objective is to have all robots awake as early as possible. While the FTP bears some resemblance to problems from areas in combinatorial optimization such as routing, broadcasting, scheduling, and covering, its algorithmic characteristics are surprisingly different. We consider both scenarios on graphs and in geometric environments.In graphs, robots sleep at vertices and there is a length function on the edges. Awake robots travel along edges, with time depending on edge length. For most scenarios, we consider the offline version of the problem, in which each awake robot knows the position of all other robots. We prove that the problem is NP-hard, even for the special case of star graphs. We also establish hardness of approximation, showing that it is NP-hard to obtain an approximation factor better than 5/3, even for graphs of bounded degree.These lower bounds are complemented with several positive algorithmic results, including: (1) We show that the natural greedy strategy on star graphs has a tight worst-case performance of 7/3 and give a polynomial-time approximation scheme (PTAS) for star graphs. (2) We give a simple O(log D)-competitive online algorithm for graphs with maximum degree D and locally bounded edge weights. (3) We give a PTAS, running in nearly linear time, for geometrically embedded instances.


title: Spam filter analysis

abstract: Unsolicited bulk email (aka. spam) is a major problem on the Internet. To counter spam, several techniques, ranging from spam filters to mail protocol extensions like hashcash, have been proposed. In this paper we investigate the effectiveness of several spam filtering techniques and technologies. Our analysis was performed by simulating email traffic under different conditions. We show that genetic algorithm based spam filters perform best at server level and naive Bayesian filters are the most appropriate for filtering at user level.


title: Parameter-less Optimization with the Extended Compact Genetic Algorithm and Iterated Local Search

abstract: This paper presents a parameter-less optimization framework that uses the extended compact genetic algorithm (ECGA) and iterated local search (ILS), but is not restricted to these algorithms. The presented optimization algorithm (ILS+ECGA) comes as an extension of the parameter-less genetic algorithm (GA), where the parameters of a selecto-recombinative GA are eliminated. The approach that we propose is tested on several well known problems. In the absence of domain knowledge, it is shown that ILS+ECGA is a robust and easy-to-use optimization method.


title: Transformation Rules for Locally Stratified Constraint Logic Programs

abstract: We propose a set of transformation rules for constraint logic programs with negation. We assume that every program is locally stratified and, thus, it has a unique perfect model. We give sufficient conditions which ensure that the proposed set of transformation rules preserves the perfect model of the programs. Our rules extend in some respects the rules for logic programs and constraint logic programs already considered in the literature and, in particular, they include a rule for unfolding a clause with respect to a negative literal.


title: An architecture for massive parallelization of the compact genetic algorithm

abstract: This paper presents an architecture which is suitable for a massive parallelization of the compact genetic algorithm. The resulting scheme has three major advantages. First, it has low synchronization costs. Second, it is fault tolerant, and third, it is scalable. The paper argues that the benefits that can be obtained with the proposed approach is potentially higher than those obtained with traditional parallel genetic algorithms. In addition, the ideas suggested in the paper may also be relevant towards parallelizing more complex probabilistic model building genetic algorithms.


title: A philosophical essay on life and its connections with genetic algorithms

abstract: This paper makes a number of connections between life and various facets of genetic and evolutionary algorithms research. Specifically, it addresses the topics of adaptation, multiobjective optimization, decision making, deception, and search operators, among others. It argues that human life, from birth to death, is an adaptive or dynamic optimization problem where people are continuously searching for happiness. More important, the paper speculates that genetic algorithms can be used as a source of inspiration for helping people make decisions in their everyday life.


title: Nested Intervals Tree Encoding with Continued Fractions

abstract: We introduce a new variation of Tree Encoding with Nested Intervals, find connections with Materialized Path, and suggest a method for moving parts of the hierarchy.


title: Continued fractions and RSA with small secret exponent

abstract: Extending the classical Legendre's result, we describe all solutions of the inequality |x - a/b| < c/b^2 in terms of convergents of continued fraction expansion of x. Namely, we show that a/b = (rp_{m+1} +- sp_m) / (rq_{m+1} +- sq_m) for some nonnegative integers m,r,s such that rs < 2c. As an application of this result, we describe a modification of Verheul and van Tilborg variant of Wiener's attack on RSA cryptosystem with small secret exponent.


title: The Complexity of Modified Instances

abstract: In this paper we study the complexity of solving a problem when a solution of a similar instance is known. This problem is relevant whenever instances may change from time to time, and known solutions may not remain valid after the change. We consider two scenarios: in the first one, what is known is only a solution of the problem before the change; in the second case, we assume that some additional information, found during the search for this solution, is also known. In the first setting, the techniques from the theory of NP-completeness suffice to show complexity results. In the second case, negative results can only be proved using the techniques of compilability, and are often related to the size of considered changes.


title: On the Security of the Yi-Tan-Siew Chaos-Based Cipher

abstract: This paper presents a comprehensive analysis on the security of the Yi-Tan-Siew chaotic cipher proposed in [IEEE TCAS-I 49(12):1826-1829 (2002)]. A differential chosen-plaintext attack and a differential chosen-ciphertext attack are suggested to break the sub-key K, under the assumption that the time stamp can be altered by the attacker, which is reasonable in such attacks. Also, some security Problems about the sub-keys $\alpha$ and $\beta$ are clarified, from both theoretical and experimental points of view. Further analysis shows that the security of this cipher is independent of the use of the chaotic tent map, once the sub-key $K$ is removed via the proposed suggested differential chosen-plaintext attack.


title: Lexical Base as a Compressed Language Model of the World (on the material of the Ukrainian language)

abstract: In the article the fact is verified that the list of words selected by formal statistical methods (frequency and functional genre unrestrictedness) is not a conglomerate of non-related words. It creates a system of interrelated items and it can be named "lexical base of language". This selected list of words covers all the spheres of human activities. To verify this statement the invariant synoptical scheme common for ideographic dictionaries of different language was determined.


title: Digital Signal Transmission with Chaotic Encryption: Design and Evaluation of a FPGA Realization

abstract: A discrete-time discrete-value pseudo-chaotic encoder/decoder system is presented. The pseudo-chaotic module is a 3D discrete version of the well-known Lorenz dynamical system. Scaling and biasing transformations as well as natural number arithmetics are employed in order to simplify realizations on a small size Field Programmable Gate Array (FPGA. The encryption ability is improved by using only the least significant byte of one of the pseudo chaotic state variables as the key to encrypt the plain text. The key is periodically perturbed by another chaotic state variable. The statistical properties of the pseudo chaotic cipher are compared with those of other pseudo-random generators available in the literature. As an example of applicability of the technique, a full duplex communication system is designed and constructed using FPGA's as technological framework.


title: Integrating Defeasible Argumentation and Machine Learning Techniques

abstract: The field of machine learning (ML) is concerned with the question of how to construct algorithms that automatically improve with experience. In recent years many successful ML applications have been developed, such as datamining programs, information-filtering systems, etc. Although ML algorithms allow the detection and extraction of interesting patterns of data for several kinds of problems, most of these algorithms are based on quantitative reasoning, as they rely on training data in order to infer so-called target functions. In the last years defeasible argumentation has proven to be a sound setting to formalize common-sense qualitative reasoning. This approach can be combined with other inference techniques, such as those provided by machine learning theory. In this paper we outline different alternatives for combining defeasible argumentation and machine learning techniques. We suggest how different aspects of a generic argument-based framework can be integrated with other ML-based approaches.


title: A Tribute to Alain Colmerauer

abstract: The paper describes the contributions of Alain Colmerauer to the areas of logic programs (LP) and constraint logic programs (CLP).


title: Light types for polynomial time computation in lambda-calculus

abstract: We propose a new type system for lambda-calculus ensuring that well-typed programs can be executed in polynomial time: Dual light affine logic (DLAL). DLAL has a simple type language with a linear and an intuitionistic type arrow, and one modality. It corresponds to a fragment of Light affine logic (LAL). We show that contrarily to LAL, DLAL ensures good properties on lambda-terms: subject reduction is satisfied and a well-typed term admits a polynomial bound on the reduction by any strategy. We establish that as LAL, DLAL allows to represent all polytime functions. Finally we give a type inference procedure for propositional DLAL.


title: Pseudorandom number generation by p-adic ergodic transformations: an addendum

abstract: The paper study counter-dependent pseudorandom number generators based on $m$-variate ($m>1$) ergodic mappings of the space of 2-adic integers $\Z_2$. The sequence of internal states of these generators is defined by the recurrence law $\mathbf x_{i+1}= H^B_i(\mathbf x_i)\bmod{2^n}$, whereas their output sequence is %while its output sequence is of the $\mathbf z_{i}=F^B_i(\mathbf x_i)\mod 2^n$; here $\mathbf x_j, \mathbf z_j$ are $m$-dimensional vectors over $\Z_2$. It is shown how the results obtained for a univariate case could be extended to a multivariate case.


title: A Correlation-Based Distance

abstract: In this short technical report, we define on the sample space R^D a distance between data points which depends on their correlation. We also derive an expression for the center of mass of a set of points with respect to this distance.


title: Evolving a Stigmergic Self-Organized Data-Mining

abstract: Self-organizing complex systems typically are comprised of a large number of frequently similar components or events. Through their process, a pattern at the global-level of a system emerges solely from numerous interactions among the lower-level components of the system. Moreover, the rules specifying interactions among the system's components are executed using only local information, without reference to the global pattern, which, as in many real-world problems is not easily accessible or possible to be found. Stigmergy, a kind of indirect communication and learning by the environment found in social insects is a well know example of self-organization, providing not only vital clues in order to understand how the components can interact to produce a complex pattern, as can pinpoint simple biological non-linear rules and methods to achieve improved artificial intelligent adaptive categorization systems, critical for Data-Mining. On the present work it is our intention to show that a new type of Data-Mining can be designed based on Stigmergic paradigms, taking profit of several natural features of this phenomenon. By hybridizing bio-inspired Swarm Intelligence with Evolutionary Computation we seek for an entire distributed, adaptive, collective and cooperative self-organized Data-Mining. As a real-world, real-time test bed for our proposal, World-Wide-Web Mining will be used. Having that purpose in mind, Web usage Data was collected from the Monash University's Web site (Australia), with over 7 million hits every week. Results are compared to other recent systems, showing that the system presented is by far promising.


title: Epistemic Foundation of Stable Model Semantics

abstract: Stable model semantics has become a very popular approach for the management of negation in logic programming. This approach relies mainly on the closed world assumption to complete the available knowledge and its formulation has its basis in the so-called Gelfond-Lifschitz transformation. The primary goal of this work is to present an alternative and epistemic-based characterization of stable model semantics, to the Gelfond-Lifschitz transformation. In particular, we show that stable model semantics can be defined entirely as an extension of the Kripke-Kleene semantics. Indeed, we show that the closed world assumption can be seen as an additional source of `falsehood' to be added cumulatively to the Kripke-Kleene semantics. Our approach is purely algebraic and can abstract from the particular formalism of choice as it is based on monotone operators (under the knowledge order) over bilattices only.


title: Genetic Algorithms and Quantum Computation

abstract: Recently, researchers have applied genetic algorithms (GAs) to address some problems in quantum computation. Also, there has been some works in the designing of genetic algorithms based on quantum theoretical concepts and techniques. The so called Quantum Evolutionary Programming has two major sub-areas: Quantum Inspired Genetic Algorithms (QIGAs) and Quantum Genetic Algorithms (QGAs). The former adopts qubit chromosomes as representations and employs quantum gates for the search of the best solution. The later tries to solve a key question in this field: what GAs will look like as an implementation on quantum hardware? As we shall see, there is not a complete answer for this question. An important point for QGAs is to build a quantum algorithm that takes advantage of both the GA and quantum computing parallelism as well as true randomness provided by quantum computers. In the first part of this paper we present a survey of the main works in GAs plus quantum computing including also our works in this area. Henceforth, we review some basic concepts in quantum computation and GAs and emphasize their inherent parallelism. Next, we review the application of GAs for learning quantum operators and circuit design. Then, quantum evolutionary programming is considered. Finally, we present our current research in this field and some perspectives.


title: New Visualization of Surfaces in Parallel Coordinates - Eliminating Ambiguity and Some "Over-Plotting"

abstract: $\cal{A}$ point $P \in \Real^n$ is represented in Parallel Coordinates by a polygonal line $\bar{P}$ (see \cite{Insel99a} for a recent survey). Earlier \cite{inselberg85plane}, a surface $\sigma$ was represented as the {\em envelope} of the polygonal lines representing it's points. This is ambiguous in the sense that {\em different} surfaces can provide the {\em same} envelopes. Here the ambiguity is eliminated by considering the surface $\sigma$ as the envelope of it's {\em tangent planes} and in turn, representing each of these planes by $n$-1 points \cite{Insel99a}. This, with some future extension, can yield a new and unambiguous representation, $\bar{\sigma}$, of the surface consisting of $n$-1 planar regions whose properties correspond lead to the {\em recognition} of the surfaces' properties i.e. developable, ruled etc. \cite{hung92smooth}) and {\em classification} criteria. It is further shown that the image (i.e. representation) of an algebraic surface of degree 2 in $\Real^n$ is a region whose boundary is also an algebraic curve of degree 2. This includes some {\em non-convex} surfaces which with the previous ambiguous representation could not be treated. An efficient construction algorithm for the representation of the quadratic surfaces (given either by {\em explicit} or {\em implicit} equation) is provided. The results obtained are suitable for applications, to be presented in a future paper, and in particular for the approximation of complex surfaces based on their {\em planar} images. An additional benefit is the elimination of the ``over-plotting'' problem i.e. the ``bunching'' of polygonal lines which often obscure part of the parallel-coordinate display.


title: Algebraic Curves in Parallel Coordinates - Avoiding the "Over-Plotting" Problem

abstract: ${\cal U}$ntil now the representation (i.e. plotting) of curve in Parallel Coordinates is constructed from the point $\leftrightarrow$ line duality. The result is a ``line-curve'' which is seen as the envelope of it's tangents. Usually this gives an unclear image and is at the heart of the ``over-plotting'' problem; a barrier in the effective use of Parallel Coordinates. This problem is overcome by a transformation which provides directly the ``point-curve'' representation of a curve. Earlier this was applied to conics and their generalizations. Here the representation, also called dual, is extended to all planar algebraic curves. Specifically, it is shown that the dual of an algebraic curve of degree $n$ is an algebraic of degree at most $n(n - 1)$ in the absence of singular points. The result that conics map into conics follows as an easy special case. An algorithm, based on algebraic geometry using resultants and homogeneous polynomials, is obtained which constructs the dual image of the curve. This approach has potential generalizations to multi-dimensional algebraic surfaces and their approximation. The ``trade-off'' price then for obtaining {\em planar} representation of multidimensional algebraic curves and hyper-surfaces is the higher degree of the image's boundary which is also an algebraic curve in $\|$-coords.


title: The role of behavior modifiers in representation development

abstract: We address the problem of the development of representations and their relationship to the environment. We study a software agent which develops in a network a representation of its simple environment which captures and integrates the relationships between agent and environment through a closure mechanism. The inclusion of a variable behavior modifier allows better representation development. This can be confirmed with an internal description of the closure mechanism, and with an external description of the properties of the representation network.


title: End-User Effects of Microreboots in Three-Tiered Internet Systems

abstract: Microreboots restart fine-grained components of software systems "with a clean slate," and only take a fraction of the time needed for full system reboot. Microreboots provide an application-generic recovery technique for Internet services, which can be supported entirely in middleware and requires no changes to the applications or any a priori knowledge of application semantics. This paper investigates the effect of microreboots on end-users of an eBay-like online auction application; we find that microreboots are nearly as effective as full reboots, but are significantly less disruptive in terms of downtime and lost work. In our experiments, microreboots reduced the number of failed user requests by 65% and the perceived downtime by 78% compared to a server process restart. We also show how to replace user-visible transient failures with transparent call-retry, at the cost of a slight increase in end-user-visible latency during recovery. Due to their low cost, microreboots can be used aggressively, even when their necessity is less than certain, hence adding to the reduced recovery time a reduction in the fault detection time, which further improves availability.


title: Polynomial-time computing over quadratic maps I: sampling in real algebraic sets

abstract: Given a quadratic map Q : K^n -> K^k defined over a computable subring D of a real closed field K, and a polynomial p(Y_1,...,Y_k) of degree d, we consider the zero set Z=Z(p(Q(X)),K^n) of the polynomial p(Q(X_1,...,X_n)). We present a procedure that computes, in (dn)^O(k) arithmetic operations in D, a set S of (real univariate representations of) sampling points in K^n that intersects nontrivially each connected component of Z. As soon as k=o(n), this is faster than the standard methods that all have exponential dependence on n in the complexity. In particular, our procedure is polynomial-time for constant k. In contrast, the best previously known procedure (due to A.Barvinok) is only capable of deciding in n^O(k^2) operations the nonemptiness (rather than constructing sampling points) of the set Z in the case of p(Y)=sum_i Y_i^2 and homogeneous Q. A by-product of our procedure is a bound (dn)^O(k) on the number of connected components of Z. The procedure consists of exact symbolic computations in D and outputs vectors of algebraic numbers. It involves extending K by infinitesimals and subsequent limit computation by a novel procedure that utilizes knowledge of an explicit isomorphism between real algebraic sets.


title: Demolishing Searle's Chinese Room

abstract: Searle's Chinese Room argument is refuted by showing that he has actually given two different versions of the room, which fail for different reasons. Hence, Searle does not achieve his stated goal of showing ``that a system could have input and output capabilities that duplicated those of a native Chinese speaker and still not understand Chinese''.


title: Polymorphic lemmas and definitions in Lambda Prolog and Twelf

abstract: Lambda Prolog is known to be well-suited for expressing and implementing logics and inference systems. We show that lemmas and definitions in such logics can be implemented with a great economy of expression. We encode a higher-order logic using an encoding that maps both terms and types of the object logic (higher-order logic) to terms of the metalanguage (Lambda Prolog). We discuss both the Terzo and Teyjus implementations of Lambda Prolog. We also encode the same logic in Twelf and compare the features of these two metalanguages for our purposes.


title: Specialization of Functional Logic Programs Based on Needed Narrowing

abstract: Many functional logic languages are based on narrowing, a unification-based goal-solving mechanism which subsumes the reduction mechanism of functional languages and the resolution principle of logic languages. Needed narrowing is an optimal evaluation strategy which constitutes the basis of modern (narrowing-based) lazy functional logic languages. In this work, we present the fundamentals of partial evaluation in such languages. We provide correctness results for partial evaluation based on needed narrowing and show that the nice properties of this strategy are essential for the specialization process. In particular, the structure of the original program is preserved by partial evaluation and, thus, the same evaluation strategy can be applied for the execution of specialized programs. This is in contrast to other partial evaluation schemes for lazy functional logic programs which may change the program structure in a negative way. Recent proposals for the partial evaluation of declarative multi-paradigm programs use (some form of) needed narrowing to perform computations at partial evaluation time. Therefore, our results constitute the basis for the correctness of such partial evaluators.


title: Distributed Control by Lagrangian Steepest Descent

abstract: Often adaptive, distributed control can be viewed as an iterated game between independent players. The coupling between the players' mixed strategies, arising as the system evolves from one instant to the next, is determined by the system designer. Information theory tells us that the most likely joint strategy of the players, given a value of the expectation of the overall control objective function, is the minimizer of a Lagrangian function of the joint strategy. So the goal of the system designer is to speed evolution of the joint strategy to that Lagrangian minimizing point, lower the expectated value of the control objective function, and repeat. Here we elaborate the theory of algorithms that do this using local descent procedures, and that thereby achieve efficient, adaptive, distributed control.


title: Predictable Software -- A Shortcut to Dependable Computing ?

abstract: Many dependability techniques expect certain behaviors from the underlying subsystems and fail in chaotic ways if these expectations are not met. Under expected circumstances, however, software tends to work quite well. This paper suggests that, instead of fixing elusive bugs or rewriting software, we improve the predictability of conditions faced by our programs. This approach might be a cheaper and faster way to improve dependability of software. After identifying some of the common triggers of unpredictability, the paper describes three engineering principles that hold promise in combating unpredictability, suggests a way to benchmark predictability, and outlines a brief research agenda.


title: Search Efficiency in Indexing Structures for Similarity Searching

abstract: Similarity searching finds application in a wide variety of domains including multilingual databases, computational biology, pattern recognition and text retrieval. Similarity is measured in terms of a distance function, edit distance, in general metric spaces, which is expensive to compute. Indexing techniques can be used reduce the number of distance computations. We present an analysis of various existing similarity indexing structures for the same. The performance obtained using the index structures studied was found to be unsatisfactory . We propose an indexing technique that combines the features of clustering with M tree(MTB) and the results indicate that this gives better performance.


title: Belle Computing System

abstract: We describe the present status of the computing system in the Belle experiment at the KEKB $e^+e^-$ asymmetric-energy collider. So far, we have logged more than 160 fb$^{-1}$ of data, corresponding to the world's largest data sample of 170M $B\bar{B}$ pairs at the $\Upsilon(4S)$ energy region. A large amount of event data has to be processed to produce an analysis event sample in a timely fashion. In addition, Monte Carlo events have to be created to control systematic errors accurately. This requires stable and efficient usage of computing resources. Here we review our computing model and then describe how we efficiently proceed DST/MC productions in our system.


title: A Comparative Study of Arithmetic Constraints on Integer Intervals

abstract: We propose here a number of approaches to implement constraint propagation for arithmetic constraints on integer intervals. To this end we introduce integer interval arithmetic. Each approach is explained using appropriate proof rules that reduce the variable domains. We compare these approaches using a set of benchmarks.


title: Extending the SDSS Batch Query System to the National Virtual Observatory Grid

abstract: The Sloan Digital Sky Survey science database is approaching 2TB. While the vast majority of queries normally execute in seconds or minutes, this interactive execution time can be disproportionately increased by a small fraction of queries that take hours or days to run; either because they require non-index scans of the largest tables or because they request very large result sets. In response to this, we added a multi-queue job submission and tracking system. The transfer of very large result sets from queries over the network is another serious problem. Statistics suggested that much of this data transfer is unnecessary; users would prefer to store results locally in order to allow further cross matching and filtering. To allow local analysis, we implemented a system that gives users their own personal database (MyDB) at the portal site. Users may transfer data to their MyDB, and then perform further analysis before extracting it to their own machine. We intend to extend the MyDB and asynchronous query ideas to multiple NVO nodes. This implies development, in a distributed manner, of several features, which have been demonstrated for a single node in the SDSS Batch Query System (CasJobs). The generalization of asynchronous queries necessitates some form of MyDB storage as well as workflow tracking services on each node and coordination strategies among nodes.


title: The World Wide Telescope: An Archetype for Online Science

abstract: Most scientific data will never be directly examined by scientists; rather it will be put into online databases where it will be analyzed and summarized by computer programs. Scientists increasingly see their instruments through online scientific archives and analysis tools, rather than examining the raw data. Today this analysis is primarily driven by scientists asking queries, but scientific archives are becoming active databases that self-organize and recognize interesting and anomalous facts as data arrives. In some fields, data from many different archives can be cross-correlated to produce new insights. Astronomy presents an excellent example of these trends; and, federating Astronomy archives presents interesting challenges for computer scientists.


title: Distributed Computing Economics

abstract: Computing economics are changing. Today there is rough price parity between (1) one database access, (2) ten bytes of network traffic, (3) 100,000 instructions, (4) 10 bytes of disk storage, and (5) a megabyte of disk bandwidth. This has implications for how one structures Internet-scale distributed computing: one puts computing as close to the data as possible in order to avoid expensive network traffic.


title: The Sloan Digital Sky Survey Science Archive: Migrating a Multi-Terabyte Astronomical Archive from Object to Relational DBMS

abstract: The Sloan Digital Sky Survey Science Archive is the first in a series of multi-Terabyte digital archives in Astronomy and other data-intensive sciences. To facilitate data mining in the SDSS archive, we adapted a commercial database engine and built specialized tools on top of it. Originally we chose an object-oriented database management system due to its data organization capabilities, platform independence, query performance and conceptual fit to the data. However, after using the object database for the first couple of years of the project, it soon began to fall short in terms of its query support and data mining performance. This was as much due to the inability of the database vendor to respond our demands for features and bug fixes as it was due to their failure to keep up with the rapid improvements in hardware performance, particularly faster RAID disk systems. In the end, we were forced to abandon the object database and migrate our data to a relational database. We describe below the technical issues that we faced with the object database and how and why we migrated to relational technology.


title: A Quick Look at SATA Disk Performance

abstract: We have been investigating the use of low-cost, commodity components for multi-terabyte SQL Server databases. Dubbed storage bricks, these servers are white box PCs containing the largest ATA drives, value-priced AMD or Intel processors, and inexpensive ECC memory. One issue has been the wiring mess, air flow problems, length restrictions, and connector failures created by seven or more parallel ATA (PATA) ribbon cables and drives in]a tower or 3U rack-mount chassis. Large capacity Serial ATA (SATA) drives have recently become widely available for the PC environment at a reasonable price. In addition to being faster, the SATA connectors seem more reliable, have a more reasonable length restriction (1m) and allow better airflow. We tested two drive brands along with two RAID controllers to evaluate SATA drive performance and reliablility. This paper documents our results so far.


title: Fast Multipoint-Evaluation of Bivariate Polynomials

abstract: We generalize univariate multipoint evaluation of polynomials of degree n at sublinear amortized cost per point. More precisely, it is shown how to evaluate a bivariate polynomial p of maximum degree less than n, specified by its n^2 coefficients, simultaneously at n^2 given points using a total of O(n^{2.667}) arithmetic operations. In terms of the input size N being quadratic in n, this amounts to an amortized cost of O(N^{0.334}) per point.


title: Secure Transmission of Sensitive data using multiple channels

abstract: A new scheme for transmitting sensitive data is proposed, the proposed scheme depends on partitioning the output of a block encryption module using the Chinese Remainder Theorem among a set of channels. The purpose of using the Chinese Remainder Theorem is to hide the cipher text in order to increase the difficulty of attacking the cipher. The theory, implementation and the security of this scheme are described in this paper.


title: Uniform Proofs of Order Independence for Various Strategy Elimination Procedures

abstract: We provide elementary and uniform proofs of order independence for various strategy elimination procedures for finite strategic games, both for dominance by pure and by mixed strategies. The proofs follow the same pattern and focus on the structural properties of the dominance relations. They rely on Newman's Lemma established in 1942 and related results on the abstract reduction systems.


title: Distribution of Mutual Information from Complete and Incomplete Data

abstract: Mutual information is widely used, in a descriptive way, to measure the stochastic dependence of categorical random variables. In order to address questions such as the reliability of the descriptive value, one must consider sample-to-population inferential approaches. This paper deals with the posterior distribution of mutual information, as obtained in a Bayesian framework by a second-order Dirichlet prior distribution. The exact analytical expression for the mean, and analytical approximations for the variance, skewness and kurtosis are derived. These approximations have a guaranteed accuracy level of the order O(1/n^3), where n is the sample size. Leading order approximations for the mean and the variance are derived in the case of incomplete samples. The derived analytical expressions allow the distribution of mutual information to be approximated reliably and quickly. In fact, the derived expressions can be computed with the same order of complexity needed for descriptive mutual information. This makes the distribution of mutual information become a concrete alternative to descriptive mutual information in many applications which would benefit from moving to the inductive side. Some of these prospective applications are discussed, and one of them, namely feature selection, is shown to perform significantly better when inductive mutual information is used.

categories: cs.LG cs.AI cs.IT math.IT math.ST stat.TH


title: What we should teach, but don't: Proposal for a cross pollinated HCI-SE curriculum

abstract: Software engineering (SE) and usability engineering (UE), as disciplines, have reached substantial levels of maturity. Each of these two disciplines is now well represented with respect to most computer science (CS) curricula. But, the two disciplines are practiced almost independently - missing oppurtunities to collaborate, coordinate and communicate about the overall design - and thereby contributing to system failures. Today, a confluence of several ingredients contribute to these failures: the increasing importance of the user interface (UI) component in the overall system, the independent maturation of the human computer interaction area, and the lack of a cohesive process model to integrate the UI experts' UE development efforts with that of SE. This in turn, we believe, is a result of a void in computing curricula: a lack of education and training regarding the importance of communication, collaboration and coordination between the SE and UE processes. In this paper we describe the current approach to teaching SE and UE and its shortcomings. We identify and analyze the barriers and issues involved in developing systems having substantial interactive components. We then propose four major themes of learning for a comprehensive computing curriculum integrating SE, UE, and system architectures in a project environment.


title: An approach to membrane computing under inexactitude

abstract: In this paper we introduce a fuzzy version of symport/antiport membrane systems. Our fuzzy membrane systems handle possibly inexact copies of reactives and their rules are endowed with threshold functions that determine whether a rule can be applied or not to a given set of objects, depending of the degree of accuracy of these objects to the reactives specified in the rule. We prove that these fuzzy membrane systems generate exactly the recursively enumerable finite-valued fuzzy sets of natural numbers.


title: An Application of Rational Trees in a Logic Programming Interpreter for a Procedural Language

abstract: We describe here a simple application of rational trees to the implementation of an interpreter for a procedural language written in a logic programming language. This is possible in languages designed to support rational trees (such as Prolog II and its descendants), but also in traditional Prolog, whose data structures are initially based on Herbrand terms, but in which implementations often omit the occurs check needed to avoid the creation of infinite data structures. We provide code implementing two interpreters, one of which needs non-occurs-check unification, which makes it faster (and more economic). We provide experimental data supporting this, and we argue that rational trees are interesting enough as to receive thorough support inside the language.


title: Characterization of the Burst Stabilization Protocol for the RR/RR CICQ Switch

abstract: Input buffered switches with Virtual Output Queueing (VOQ) can be unstable when presented with unbalanced loads. Existing scheduling algorithms, including iSLIP for Input Queued (IQ) switches and Round Robin (RR) for Combined Input and Crossbar Queued (CICQ) switches, exhibit instability for some schedulable loads. We investigate the use of a queue length threshold and bursting mechanism to achieve stability without requiring internal speed-up. An analytical model is developed to prove that the burst stabilization protocol achieves stability and to predict the minimum burst value needed as a function of offered load. The analytical model is shown to have very good agreement with simulation results. These results show the advantage of the RR/RR CICQ switch as a contender for the next generation of high-speed switches.


title: Performance Evaluation of Packet-to-Cell Segmentation Schemes in Input Buffered Packet Switches

abstract: Most input buffered packet switches internally segment variable-length packets into fixed-length cells. The last cell in a segmented packet will contain overhead bytes if the packet length is not evenly divisible by the cell length. Switch speed-up is used to compensate for this overhead. In this paper, we develop an analytical model of a single-server queue where an input stream of packets is segmented into cells for service. Analytical models are developed for M/M/1, M/H2/1, and M/E2/1 queues with a discretized (or quantized) service time. These models and simulation using real packet traces are used to evaluate the effect of speed-up on mean queue length. We propose and evaluate a new method of segmenting a packet trailer and subsequent packet header into a single cell. This cell merging method reduces the required speed-up. No changes to switch-matrix scheduling algorithms are needed. Simulation with a packet trace shows a reduction in the needed speed-up for an iSLIP scheduled input buffered switch.


title: Concept of E-machine: How does a "dynamical" brain learn to process "symbolic" information? Part I

abstract: The human brain has many remarkable information processing characteristics that deeply puzzle scientists and engineers. Among the most important and the most intriguing of these characteristics are the brain's broad universality as a learning system and its mysterious ability to dynamically change (reconfigure) its behavior depending on a combinatorial number of different contexts. This paper discusses a class of hypothetically brain-like dynamically reconfigurable associative learning systems that shed light on the possible nature of these brain's properties. The systems are arranged on the general principle referred to as the concept of E-machine. The paper addresses the following questions: 1. How can "dynamical" neural networks function as universal programmable "symbolic" machines? 2. What kind of a universal programmable symbolic machine can form arbitrarily complex software in the process of programming similar to the process of biological associative learning? 3. How can a universal learning machine dynamically reconfigure its software depending on a combinatorial number of possible contexts?


title: Where Fail-Safe Default Logics Fail

abstract: Reiter's original definition of default logic allows for the application of a default that contradicts a previously applied one. We call failure this condition. The possibility of generating failures has been in the past considered as a semantical problem, and variants have been proposed to solve it. We show that it is instead a computational feature that is needed to encode some domains into default logic.


title: Integrating design synthesis and assembly of structured objects in a visual design language

abstract: Computer Aided Design systems provide tools for building and manipulating models of solid objects. Some also provide access to programming languages so that parametrised designs can be expressed. There is a sharp distinction, therefore, between building models, a concrete graphical editing activity, and programming, an abstract, textual, algorithm-construction activity. The recently proposed Language for Structured Design (LSD) was motivated by a desire to combine the design and programming activities in one language. LSD achieves this by extending a visual logic programming language to incorporate the notions of solids and operations on solids. Here we investigate another aspect of the LSD approach; namely, that by using visual logic programming as the engine to drive the parametrised assembly of objects, we also gain the powerful symbolic problem-solving capability that is the forte of logic programming languages. This allows the designer/programmer to work at a higher level, giving declarative specifications of a design in order to obtain the design descriptions. Hence LSD integrates problem solving, design synthesis, and prototype assembly in a single homogeneous programming/design environment. We demonstrate this specification-to-final-assembly capability using the masterkeying problem for designing systems of locks and keys.


title: Phantom Types and Subtyping

abstract: We investigate a technique from the literature, called the phantom-types technique, that uses parametric polymorphism, type constraints, and unification of polymorphic types to model a subtyping hierarchy. Hindley-Milner type systems, such as the one found in Standard ML, can be used to enforce the subtyping relation, at least for first-order values. We show that this technique can be used to encode any finite subtyping hierarchy (including hierarchies arising from multiple interface inheritance). We formally demonstrate the suitability of the phantom-types technique for capturing first-order subtyping by exhibiting a type-preserving translation from a simple calculus with bounded polymorphism to a calculus embodying the type system of SML.


title: Web pages search engine based on DNS

abstract: Search engine is main access to the largest information source in this world, Internet. Now Internet is changing every aspect of our life. Information retrieval service may be its most important services. But for common user, internet search service is still far from our expectation, too many unrelated search results, old information, etc. To solve these problems, a new system, search engine based on DNS is proposed. The original idea, detailed content and implementation of this system all are introduced in this paper.


title: Domain resource integration system

abstract: Domain Resource Integrated System (DRIS) is introduced in this paper. DRIS is a hierarchical distributed Internet information retrieval system. This system will solve some bottleneck problems such as long update interval, poor coverage in current web search system. DRIS will build the information retrieval infrastructure of Internet, but not a commercial search engine. The protocol series of DRIS are also detailed in this paper.


title: Schedulers and Redundancy for a Class of Constraint Propagation Rules

abstract: We study here schedulers for a class of rules that naturally arise in the context of rule-based constraint programming. We systematically derive a scheduler for them from a generic iteration algorithm of [Apt 2000]. We apply this study to so-called membership rules of [Apt and Monfroy 2001]. This leads to an implementation that yields a considerably better performance for these rules than their execution as standard CHR rules. Finally, we show how redundant rules can be identified and how appropriately reduced sets of rules can be computed.


title: Tournament versus Fitness Uniform Selection

abstract: In evolutionary algorithms a critical parameter that must be tuned is that of selection pressure. If it is set too low then the rate of convergence towards the optimum is likely to be slow. Alternatively if the selection pressure is set too high the system is likely to become stuck in a local optimum due to a loss of diversity in the population. The recent Fitness Uniform Selection Scheme (FUSS) is a conceptually simple but somewhat radical approach to addressing this problem - rather than biasing the selection towards higher fitness, FUSS biases selection towards sparsely populated fitness levels. In this paper we compare the relative performance of FUSS with the well known tournament selection scheme on a range of problems.


title: A Flexible Rule Compiler for Speech Synthesis

abstract: We present a flexible rule compiler developed for a text-to-speech (TTS) system. The compiler converts a set of rules into a finite-state transducer (FST). The input and output of the FST are subject to parameterization, so that the system can be applied to strings and sequences of feature-structures. The resulting transducer is guaranteed to realize a function (as opposed to a relation), and therefore can be implemented as a deterministic device (either a deterministic FST or a bimachine).


title: Generating connected acyclic digraphs uniformly at random

abstract: We describe a simple algorithm based on a Markov chain process to generate simply connected acyclic directed graphs over a fixed set of vertices. This algorithm is an extension of a previous one, designed to generate acyclic digraphs, non necessarily connected.


title: A Theory of Computation Based on Quantum Logic (I)

abstract: The (meta)logic underlying classical theory of computation is Boolean (two-valued) logic. Quantum logic was proposed by Birkhoff and von Neumann as a logic of quantum mechanics more than sixty years ago. The major difference between Boolean logic and quantum logic is that the latter does not enjoy distributivity in general. The rapid development of quantum computation in recent years stimulates us to establish a theory of computation based on quantum logic. The present paper is the first step toward such a new theory and it focuses on the simplest models of computation, namely finite automata. It is found that the universal validity of many properties of automata depend heavily upon the distributivity of the underlying logic. This indicates that these properties does not universally hold in the realm of quantum logic. On the other hand, we show that a local validity of them can be recovered by imposing a certain commutativity to the (atomic) statements about the automata under consideration. This reveals an essential difference between the classical theory of computation and the computation theory based on quantum logic.


title: Protecting Public-Access Sites Against Distributed Denial-of-Service Attacks

abstract: A distributed denial-of-service (DDoS) attack can flood a victim site with malicious traffic, causing service disruption or even complete failure. Public-access sites like amazon or ebay are particularly vulnerable to such attacks, because they have no way of a priori blocking unauthorized traffic. We present Active Internet Traffic Filtering (AITF), a mechanism that protects public-access sites from highly distributed attacks by causing undesired traffic to be blocked as close as possible to its sources. We identify filters as a scarce resource and show that AITF protects a significant amount of the victim's bandwidth, while requiring from each participating router a number of filters that can be accommodated by today's routers. AITF is incrementally deployable, because it offers a substantial benefit even to the first sites that deploy it.


title: Stream cipher based on quasigroup string transformations in $Z_p^*$

abstract: In this paper we design a stream cipher that uses the algebraic structure of the multiplicative group $\bbbz_p^*$ (where p is a big prime number used in ElGamal algorithm), by defining a quasigroup of order $p-1$ and by doing quasigroup string transformations. The cryptographical strength of the proposed stream cipher is based on the fact that breaking it would be at least as hard as solving systems of multivariate polynomial equations modulo big prime number $p$ which is NP-hard problem and there are no known fast randomized or deterministic algorithms for solving it. Unlikely the speed of known ciphers that work in $\bbbz_p^*$ for big prime numbers $p$, the speed of this stream cipher both in encryption and decryption phase is comparable with the fastest symmetric-key stream ciphers.


title: Scalable Probabilistic Models for 802.11 Protocol Verification

abstract: The IEEE 802.11 protocol is a popular standard for wireless local area networks. Its medium access control layer (MAC) is a carrier sense multiple access with collision avoidance (CSMA/CA) design and includes an exponential backoff mechanism that makes it a possible target for probabilistic model checking. In this work, we identify ways to increase the scope of application of probabilistic model checking to the 802.11 MAC. Current techniques do not scale to networks of even moderate size. To work around this problem, we identify properties of the protocol that can be used to simplify the models and make verification feasible. Using these observations, we directly optimize the probabilistic timed automata models while preserving probabilistic reachability measures. We substantiate our claims of significant reduction by our results from using the probabilistic model checker PRISM.


title: On the Practicality of Intrinsic Reconfiguration As a Fault Recovery Method in Analog Systems

abstract: Evolvable hardware combines the powerful search capability of evolutionary algorithms with the flexibility of reprogrammable devices, thereby providing a natural framework for reconfiguration. This framework has generated an interest in using evolvable hardware for fault-tolerant systems because reconfiguration can effectively deal with hardware faults whenever it is impossible to provide spares. But systems cannot tolerate faults indefinitely, which means reconfiguration does have a deadline. The focus of previous evolvable hardware research relating to fault-tolerance has been primarily restricted to restoring functionality, with no real consideration of time constraints. In this paper we are concerned with evolvable hardware performing reconfiguration under deadline constraints. In particular, we investigate reconfigurable hardware that undergoes intrinsic evolution. We show that fault recovery done by intrinsic reconfiguration has some restrictions, which designers cannot ignore.


title: Mathematical Analysis of Multi-Agent Systems

abstract: We review existing approaches to mathematical modeling and analysis of multi-agent systems in which complex collective behavior arises out of local interactions between many simple agents. Though the behavior of an individual agent can be considered to be stochastic and unpredictable, the collective behavior of such systems can have a simple probabilistic description. We show that a class of mathematical models that describe the dynamics of collective behavior of multi-agent systems can be written down from the details of the individual agent controller. The models are valid for Markov or memoryless agents, in which each agents future state depends only on its present state and not any of the past states. We illustrate the approach by analyzing in detail applications from the robotics domain: collaboration and foraging in groups of robots.


title: Enhancing the expressive power of the U-Datalog language

abstract: U-Datalog has been developed with the aim of providing a set-oriented logical update language, guaranteeing update parallelism in the context of a Datalog-like language. In U-Datalog, updates are expressed by introducing constraints (+p(X), to denote insertion, and [minus sign]p(X), to denote deletion) inside Datalog rules. A U-Datalog program can be interpreted as a CLP program. In this framework, a set of updates (constraints) is satisfiable if it does not represent an inconsistent theory, that is, it does not require the insertion and the deletion of the same fact. This approach resembles a very simple form of negation. However, on the other hand, U-Datalog does not provide any mechanism to explicitly deal with negative information, resulting in a language with limited expressive power. In this paper, we provide a semantics, based on stratification, handling the use of negated atoms in U-Datalog programs, and we show which problems arise in defining a compositional semantics.


title: Dealing With Curious Players in Secure Networks

abstract: In secure communications networks there are a great number of user behavioural problems, which need to be dealt with. Curious players pose a very real and serious threat to the integrity of such a network. By traversing a network a Curious player could uncover secret information, which that user has no need to know, by simply posing as a loyalty check. Loyalty checks are done simply to gauge the integrity of the network with respect to players who act in a malicious manner. We wish to propose a method, which can deal with Curious players trying to obtain "Need to Know" information using a combined Fault-tolerant, Cryptographic and Game Theoretic Approach.


title: Government mandated blocking of foreign Web content

abstract: Blocking of foreign Web content by Internet access providers has been a hot topic for the last 18 months in Germany. Since fall 2001 the state of North-Rhine-Westphalia very actively tries to mandate such blocking. This paper will take a technical view on the problems imposed by the blocking orders and blocking content at access or network provider level in general. It will also give some empirical data on the effects of the blocking orders to help in the legal assessment of the orders.


title: Delimited continuations in natural language: quantification and polarity sensitivity

abstract: Making a linguistic theory is like making a programming language: one typically devises a type system to delineate the acceptable utterances and a denotational semantics to explain observations on their behavior. Via this connection, the programming language concept of delimited continuations can help analyze natural language phenomena such as quantification and polarity sensitivity. Using a logical metalanguage whose syntax includes control operators and whose semantics involves evaluation order, these analyses can be expressed in direct style rather than continuation-passing style, and these phenomena can be thought of as computational side effects.


title: Polarity sensitivity and evaluation order in type-logical grammar

abstract: We present a novel, type-logical analysis of_polarity sensitivity_: how negative polarity items (like "any" and "ever") or positive ones (like "some") are licensed or prohibited. It takes not just scopal relations but also linear order into account, using the programming-language notions of delimited continuations and evaluation order, respectively. It thus achieves greater empirical coverage than previous proposals.


title: Efficient dot product over word-size finite fields

abstract: We want to achieve efficiency for the exact computation of the dot product of two vectors over word-size finite fields. We therefore compare the practical behaviors of a wide range of implementation techniques using different representations. The techniques used include oating point representations, discrete logarithms, tabulations, Montgomery reduction, delayed modulus.


title: Tabular Parsing

abstract: This is a tutorial on tabular parsing, on the basis of tabulation of nondeterministic push-down automata. Discussed are Earley's algorithm, the Cocke-Kasami-Younger algorithm, tabular LR parsing, the construction of parse trees, and further issues.


title: On the universality of rank distributions of website popularity

abstract: We present an extensive analysis of long-term statistics of the queries to websites using logs collected on several web caches in Russian academic networks and on US IRCache caches. We check the sensitivity of the statistics to several parameters: (1) duration of data collection, (2) geographical location of the cache server collecting data, and (3) the year of data collection. We propose a two-parameter modification of the Zipf law and interpret the parameters. We find that the rank distribution of websites is stable when approximated by the modified Zipf law. We suggest that website popularity may be a universal property of Internet.


title: Parametric external predicates for the DLV System

abstract: This document describes syntax, semantics and implementation guidelines in order to enrich the DLV system with the possibility to make external C function calls. This feature is realized by the introduction of parametric external predicates, whose extension is not specified through a logic program but implicitly computed through external code.


title: Toward the Implementation of Functions in the DLV System (Preliminary Technical Report)

abstract: This document describes the functions as they are treated in the DLV system. We give first the language, then specify the main implementation issues.


title: Tycoon: A Distributed Market-based Resource Allocation System

abstract: P2P clusters like the Grid and PlanetLab enable in principle the same statistical multiplexing efficiency gains for computing as the Internet provides for networking. The key unsolved problem is resource allocation. Existing solutions are not economically efficient and require high latency to acquire resources. We designed and implemented Tycoon, a market based distributed resource allocation system based on an Auction Share scheduling algorithm. Preliminary results show that Tycoon achieves low latency and high fairness while providing incentives for truth-telling on the part of strategic users.


title: A Modular and Fault-Tolerant Data Transport Framework

abstract: The High Level Trigger (HLT) of the future ALICE heavy-ion experiment has to reduce its input data rate of up to 25 GB/s to at most 1.25 GB/s for output before the data is written to permanent storage. To cope with these data rates a large PC cluster system is being designed to scale to several 1000 nodes, connected by a fast network. For the software that will run on these nodes a flexible data transport and distribution software framework, described in this thesis, has been developed. The framework consists of a set of separate components, that can be connected via a common interface. This allows to construct different configurations for the HLT, that are even changeable at runtime. To ensure a fault-tolerant operation of the HLT, the framework includes a basic fail-over mechanism that allows to replace whole nodes after a failure. The mechanism will be further expanded in the future, utilizing the runtime reconnection feature of the framework's component interface. To connect cluster nodes a communication class library is used that abstracts from the actual network technology and protocol used to retain flexibility in the hardware choice. It contains already two working prototype versions for the TCP protocol as well as SCI network adapters. Extensions can be added to the library without modifications to other parts of the framework. Extensive tests and measurements have been performed with the framework. Their results as well as conclusions drawn from them are also presented in this thesis. Performance tests show very promising results for the system, indicating that it can fulfill ALICE's requirements concerning the data transport.


title: The study of distributed computing algorithms by multithread applications

abstract: The material in this note is used as an introduction to distributed algorithms in a four year course on software and automatic control system in the computer technology department of the Komsomolsk-on-Amur state technical university. All our the program examples are written in Borland C/C++ 5.02 for Windows 95/98/2000/NT/XP, and hence suit to compile and execute by Visual C/C++. We consider the following approaches of the distributed computing: the conversion of recursive algorithms to multithread applications, a realization of the pairing algorithm, the building of wave systems by Petri nets and object oriented programming.


title: Parrondo's games with chaotic switching

abstract: This paper investigates the different effects of chaotic switching on Parrondo's games, as compared to random and periodic switching. The rate of winning of Parrondo's games with chaotic switching depends on coefficient(s) defining the chaotic generator, initial conditions of the chaotic sequence and the proportion of Game A played. Maximum rate of winning can be obtained with all the above mentioned factors properly set, and this occurs when chaotic switching approaches periodic behavior.


title: Exploring tradeoffs in pleiotropy and redundancy using evolutionary computing

abstract: Evolutionary computation algorithms are increasingly being used to solve optimization problems as they have many advantages over traditional optimization algorithms. In this paper we use evolutionary computation to study the trade-off between pleiotropy and redundancy in a client-server based network. Pleiotropy is a term used to describe components that perform multiple tasks, while redundancy refers to multiple components performing one same task. Pleiotropy reduces cost but lacks robustness, while redundancy increases network reliability but is more costly, as together, pleiotropy and redundancy build flexibility and robustness into systems. Therefore it is desirable to have a network that contains a balance between pleiotropy and redundancy. We explore how factors such as link failure probability, repair rates, and the size of the network influence the design choices that we explore using genetic algorithms.


title: NLML--a Markup Language to Describe the Unlimited English Grammar

abstract: In this paper we present NLML (Natural Language Markup Language), a markup language to describe the syntactic and semantic structure of any grammatically correct English expression. At first the related works are analyzed to demonstrate the necessity of the NLML: simple form, easy management and direct storage. Then the description of the English grammar with NLML is introduced in details in three levels: sentences (with different complexities, voices, moods, and tenses), clause (relative clause and noun clause) and phrase (noun phrase, verb phrase, prepositional phrase, adjective phrase, adverb phrase and predicate phrase). At last the application fields of the NLML in NLP are shown with two typical examples: NLOJM (Natural Language Object Modal in Java) and NLDB (Natural Language Database).


title: Optimizing genetic algorithm strategies for evolving networks

abstract: This paper explores the use of genetic algorithms for the design of networks, where the demands on the network fluctuate in time. For varying network constraints, we find the best network using the standard genetic algorithm operators such as inversion, mutation and crossover. We also examine how the choice of genetic algorithm operators affects the quality of the best network found. Such networks typically contain redundancy in servers, where several servers perform the same task and pleiotropy, where servers perform multiple tasks. We explore this trade-off between pleiotropy versus redundancy on the cost versus reliability as a measure of the quality of the network.


title: A treatment of higher-order features in logic programming

abstract: The logic programming paradigm provides the basis for a new intensional view of higher-order notions. This view is realized primarily by employing the terms of a typed lambda calculus as representational devices and by using a richer form of unification for probing their structures. These additions have important meta-programming applications but they also pose non-trivial implementation problems. One issue concerns the machine representation of lambda terms suitable to their intended use: an adequate encoding must facilitate comparison operations over terms in addition to supporting the usual reduction computation. Another aspect relates to the treatment of a unification operation that has a branching character and that sometimes calls for the delaying of the solution of unification problems. A final issue concerns the execution of goals whose structures become apparent only in the course of computation. These various problems are exposed in this paper and solutions to them are described. A satisfactory representation for lambda terms is developed by exploiting the nameless notation of de Bruijn as well as explicit encodings of substitutions. Special mechanisms are molded into the structure of traditional Prolog implementations to support branching in unification and carrying of unification problems over other computation steps; a premium is placed in this context on exploiting determinism and on emulating usual first-order behaviour. An extended compilation model is presented that treats higher-order unification and also handles dynamically emergent goals. The ideas described here have been employed in the Teyjus implementation of the Lambda Prolog language, a fact that is used to obtain a preliminary assessment of their efficacy.


title: Decidability and Universality in Symbolic Dynamical Systems

abstract: Many different definitions of computational universality for various types of dynamical systems have flourished since Turing's work. We propose a general definition of universality that applies to arbitrary discrete time symbolic dynamical systems. Universality of a system is defined as undecidability of a model-checking problem. For Turing machines, counter machines and tag systems, our definition coincides with the classical one. It yields, however, a new definition for cellular automata and subshifts. Our definition is robust with respect to initial condition, which is a desirable feature for physical realizability. We derive necessary conditions for undecidability and universality. For instance, a universal system must have a sensitive point and a proper subsystem. We conjecture that universal systems have infinite number of subsystems. We also discuss the thesis according to which computation should occur at the `edge of chaos' and we exhibit a universal chaotic system.


title: An Algorithm for Transforming Color Images into Tactile Graphics

abstract: This paper presents an algorithm that transforms color visual images, like photographs or paintings, into tactile graphics. In the algorithm, the edges of objects are detected and colors of the objects are estimated. Then, the edges and the colors are encoded into lines and textures in the output tactile image. Design of the method is substantiated by various qualities of haptic recognizing of images. Also, means of presentation of the tactile images in printouts are discussed. Example translated images are shown.


title: Propositional computability logic I

abstract: In the same sense as classical logic is a formal theory of truth, the recently initiated approach called computability logic is a formal theory of computability. It understands (interactive) computational problems as games played by a machine against the environment, their computability as existence of a machine that always wins the game, logical operators as operations on computational problems, and validity of a logical formula as being a scheme of "always computable" problems. The present contribution gives a detailed exposition of a soundness and completeness proof for an axiomatization of one of the most basic fragments of computability logic. The logical vocabulary of this fragment contains operators for the so called parallel and choice operations, and its atoms represent elementary problems, i.e. predicates in the standard sense. This article is self-contained as it explains all relevant concepts. While not technically necessary, however, familiarity with the foundational paper "Introduction to computability logic" [Annals of Pure and Applied Logic 123 (2003), pp.1-99] would greatly help the reader in understanding the philosophy, underlying motivations, potential and utility of computability logic, -- the context that determines the value of the present results. Online introduction to the subject is available at http://www.cis.upenn.edu/~giorgi/cl.html and http://www.csc.villanova.edu/~japaridz/CL/gsoll.html .


title: Computability Logic: a formal theory of interaction

abstract: Computability logic is a formal theory of (interactive) computability in the same sense as classical logic is a formal theory of truth. This approach was initiated very recently in "Introduction to computability logic" (Annals of Pure and Applied Logic 123 (2003), pp.1-99). The present paper reintroduces computability logic in a more compact and less technical way. It is written in a semitutorial style with a general computer science, logic or mathematics audience in mind. An Internet source on the subject is available at http://www.cis.upenn.edu/~giorgi/cl.html, and additional material at http://www.csc.villanova.edu/~japaridz/CL/gsoll.html .


title: Test Collections for Patent-to-Patent Retrieval and Patent Map Generation in NTCIR-4 Workshop

abstract: This paper describes the Patent Retrieval Task in the Fourth NTCIR Workshop, and the test collections produced in this task. We perform the invalidity search task, in which each participant group searches a patent collection for the patents that can invalidate the demand in an existing claim. We also perform the automatic patent map generation task, in which the patents associated with a specific topic are organized in a multi-dimensional matrix.


title: DAB Content Annotation and Receiver Hardware Control with XML

abstract: The Eureka-147 Digital Audio Broadcasting (DAB) standard defines the 'dynamic labels' data field for holding information about the transmission content. However, this information does not follow a well-defined structure since it is designed to carry text for direct output to displays, for human interpretation. This poses a problem when machine interpretation of DAB content information is desired. Extensible Markup Language (XML) was developed to allow for the well-defined, structured machine-to-machine exchange of data over computer networks. This article proposes a novel technique of machine-interpretable DAB content annotation and receiver hardware control, involving the utilisation of XML as metadata in the transmitted DAB frames.


title: The Gridbus Toolkit for Service Oriented Grid and Utility Computing: An Overview and Status Report

abstract: Grids aim at exploiting synergies that result from cooperation of autonomous distributed entities. The synergies that result from grid cooperation include the sharing, exchange, selection, and aggregation of geographically distributed resources such as computers, data bases, software, and scientific instruments for solving large-scale problems in science, engineering, and commerce. For this cooperation to be sustainable, participants need to have economic incentive. Therefore, "incentive" mechanisms should be considered as one of key design parameters of Grid architectures. In this article, we present an overview and status of an open source Grid toolkit, called Gridbus, whose architecture is fundamentally driven by the requirements of Grid economy. Gridbus technologies provide services for both computational and data grids that power the emerging eScience and eBusiness applications.