title: Gestion Dynamique des Services Techniques pour Modele a Composants

abstract: The new applications being intended for more and more heterogeneous environments, it is necessary to propose solutions of development which answer in best the necessities of adaptation of new services. Component-based programming partially answers this aim, allowing easy replacement of software blocks in order to provide the most adapted version of a component. Nevertheless, most of the industrial component-based model implementations do not allow to provide to components the most adapted technical services (naming, trading, security, transaction, etc.). In this paper, we suggest defining technical services themselves under the shape of components. We shall detail our proposition, by basing it on the Fractal component model of Objectweb. Then, we shall bring solutions for the use of these new component-based technical services and shall propose a set of management components which allow to administer in a dynamic and stand-alone way the obtained components. Finally we present the prototype of the proposed solution.


title: Local heuristics and the emergence of spanning subgraphs in complex networks

abstract: We study the use of local heuristics to determine spanning subgraphs for use in the dissemination of information in complex networks. We introduce two different heuristics and analyze their behavior in giving rise to spanning subgraphs that perform well in terms of allowing every node of the network to be reached, of requiring relatively few messages and small node bandwidth for information dissemination, and also of stretching paths with respect to the underlying network only modestly. We contribute a detailed mathematical analysis of one of the heuristics and provide extensive simulation results on random graphs for both of them. These results indicate that, within certain limits, spanning subgraphs are indeed expected to emerge that perform well in respect to all requirements. We also discuss the spanning subgraphs' inherent resilience to failures and adaptability to topological changes.


title: Principles for Digital Preservation

abstract: The immense investments in creating and disseminating digitally represented information have not been accompanied by commensurate effort to ensure the longevity of information of permanent interest. Asserted difficulties with long-term digital preservation prove to be largely underestimation of what technology can provide. We show how to clarify prominent misunderstandings and sketch a 'Trustworthy Digital Object (TDO)' method that solves all the published technical challenges.


title: Trustworthy 100-Year Digital Objects: Durable Encoding for When It's Too Late to Ask

abstract: How can an author store digital information so that it will be reliably useful, even years later when he is no longer available to answer questions? Methods that might work are not good enough; what is preserved today should be reliably useful whenever someone wants it. Prior proposals fail because they confound saved data with irrelevant details of today's information technology--details that are difficult to define, extract, and save completely and accurately. We use a virtual machine to represent and eventually to render any data whatsoever. We focus on a case of intermediate difficulty--an executable procedure--and identify a variant for every other data type. This solution might be more elaborate than needed to render some text, image, audio, or video data. Simple data can be preserved as representations using well-known standards. We sketch practical methods for files ranging from simple structures to those containing computer programs, treating simple cases here and deferring complex cases for future work. Enough of the complete solution is known to enable practical aggressive preservation programs today.


title: Forbidden Subgraphs in Connected Graphs

abstract: Given a set $\xi=\{H_1,H_2,...\}$ of connected non acyclic graphs, a $\xi$-free graph is one which does not contain any member of $% \xi$ as copy. Define the excess of a graph as the difference between its number of edges and its number of vertices. Let ${\gr{W}}_{k,\xi}$ be theexponential generating function (EGF for brief) of connected $\xi$-free graphs of excess equal to $k$ ($k \geq 1$). For each fixed $\xi$, a fundamental differential recurrence satisfied by the EGFs ${\gr{W}}_{k,\xi}$ is derived. We give methods on how to solve this nonlinear recurrence for the first few values of $k$ by means of graph surgery. We also show that for any finite collection $\xi$ of non-acyclic graphs, the EGFs ${\gr{W}}_{k,\xi}$ are always rational functions of the generating function, $T$, of Cayley's rooted (non-planar) labelled trees. From this, we prove that almost all connected graphs with $n$ nodes and $n+k$ edges are $\xi$-free, whenever $k=o(n^{1/3})$ and $|\xi| < \infty$ by means of Wright's inequalities and saddle point method. Limiting distributions are derived for sparse connected $\xi$-free components that are present when a random graph on $n$ nodes has approximately $\frac{n}{2}$ edges. In particular, the probability distribution that it consists of trees, unicyclic components, $...$, $(q+1)$-cyclic components all $\xi$-free is derived. Similar results are also obtained for multigraphs, which are graphs where self-loops and multiple-edges are allowed.


title: On the existence of truly autonomic computing systems and the link with quantum computing

abstract: A theoretical model of truly autonomic computing systems (ACS), with infinitely many constraints, is proposed. An argument similar to Turing's for the unsolvability of the halting problem, which is permitted in classical logic, shows that such systems cannot exist. Turing's argument fails in the recently proposed non-Aristotelian finitary logic (NAFL), which permits the existence of ACS. NAFL also justifies quantum superposition and entanglement, which are essential ingredients of quantum algorithms, and resolves the Einstein-Podolsky-Rosen (EPR) paradox in favour of quantum mechanics and non-locality. NAFL requires that the autonomic manager (AM) must be conceptually and architecturally distinct from the managed element, in order for the ACS to exist as a non-self-referential entity. Such a scenario is possible if the AM uses quantum algorithms and is protected from all problems by (unbreakable) quantum encryption, while the managed element remains classical. NAFL supports such a link between autonomic and quantum computing, with the AM existing as a metamathematical entity. NAFL also allows quantum algorithms to access truly random elements and thereby supports non-standard models of quantum (hyper-) computation that permit infinite parallelism.


title: Embeddings into the Pancake Interconnection Network

abstract: Owing to its nice properties, the pancake is one of the Cayley graphs that were proposed as alternatives to the hypercube for interconnecting processors in parallel computers. In this paper, we present embeddings of rings, grids and hypercubes into the pancake with constant dilation and congestion. We also extend the results to similar efficient embeddings into the star graph.


title: Inter-Package Dependency Networks in Open-Source Software

abstract: This research analyzes complex networks in open-source software at the inter-package level, where package dependencies often span across projects and between development groups. We review complex networks identified at ``lower'' levels of abstraction, and then formulate a description of interacting software components at the package level, a relatively ``high'' level of abstraction. By mining open-source software repositories from two sources, we empirically show that the coupling of modules at this granularity creates a small-world and scale-free network in both instances.


title: Deterministic Bayesian Logic

abstract: In this paper a conditional logic is defined and studied. This conditional logic, Deterministic Bayesian Logic, is constructed as a deterministic counterpart to the (probabilistic) Bayesian conditional. The logic is unrestricted, so that any logical operations are allowed. This logic is shown to be non-trivial and is not reduced to classical propositions. The Bayesian conditional of DBL implies a definition of logical independence. Interesting results are derived about the interactions between the logical independence and the proofs. A model is constructed for the logic. Completeness results are proved. It is shown that any unconditioned probability can be extended to the whole logic DBL. The Bayesian conditional is then recovered from the probabilistic DBL. At last, it is shown why DBL is compliant with Lewis triviality.


title: On the High-SNR Capacity of Non-Coherent Networks

abstract: We obtain the first term in the high signal-to-noise ratio (SNR) expansion of the capacity of fading networks where the transmitters and receivers--while fully cognizant of the fading \emph{law}--have no access to the fading \emph{realization}. This term is an integer multiple of $\log \log \textnormal{SNR}$ with the coefficient having a simple combinatorial characterization.


title: A Note on the PAC Bayesian Theorem

abstract: We prove general exponential moment inequalities for averages of [0,1]-valued iid random variables and use them to tighten the PAC Bayesian Theorem. The logarithmic dependence on the sample count in the enumerator of the PAC Bayesian bound is halved.


title: A Decidable Probability Logic for Timed Probabilistic Systems

abstract: In this paper we extend the predicate logic introduced in [Beauquier et al. 2002] in order to deal with Semi-Markov Processes. We prove that with respect to qualitative probabilistic properties, model checking is decidable for this logic applied to Semi-Markov Processes. Furthermore we apply our logic to Probabilistic Timed Automata considering classical and urgent semantics, and considering also predicates on clock. We prove that results on Semi Markov Processes hold also for Probabilistic Timed Automata for both the two semantics considered. Moreover, we prove that results for Markov Processes shown in [Beauquier et al. 2002] are extensible to Probabilistic Timed Automata where urgent semantics is considered.


title: EURYDICE : A platform for unified access to documents

abstract: In this paper we present Eurydice, a platform dedicated to provide a unified gateway to documents. Its basic functionalities about collecting documents have been designed based on a long experience about the management of scientific documentation among large and demanding academic communities such as IMAG and INRIA. Besides the basic problem of accessing documents - which was of course the original and main motivation of the project - a great effort has been dedicated to the development of management functionalities which could help institutions to control, analyse the current situation about the use of the documentation, and finally to set a better ground for a documentation policy. Finally a great emphasis - and corresponding technical investment - has been put on the protection of property and reproduction rights both from the users' intitution side and from the editors' side.


title: Ranking Pages by Topology and Popularity within Web Sites

abstract: We compare two link analysis ranking methods of web pages in a site. The first, called Site Rank, is an adaptation of PageRank to the granularity of a web site and the second, called Popularity Rank, is based on the frequencies of user clicks on the outlinks in a page that are captured by navigation sessions of users through the web site. We ran experiments on artificially created web sites of different sizes and on two real data sets, employing the relative entropy to compare the distributions of the two ranking methods. For the real data sets we also employ a nonparametric measure, called Spearman's footrule, which we use to compare the top-ten web pages ranked by the two methods. Our main result is that the distributions of the Popularity Rank and Site Rank are surprisingly close to each other, implying that the topology of a web site is very instrumental in guiding users through the site. Thus, in practice, the Site Rank provides a reasonable first order approximation of the aggregate behaviour of users within a web site given by the Popularity Rank.


title: Mining Heterogeneous Multivariate Time-Series for Learning Meaningful Patterns: Application to Home Health Telecare

abstract: For the last years, time-series mining has become a challenging issue for researchers. An important application lies in most monitoring purposes, which require analyzing large sets of time-series for learning usual patterns. Any deviation from this learned profile is then considered as an unexpected situation. Moreover, complex applications may involve the temporal study of several heterogeneous parameters. In that paper, we propose a method for mining heterogeneous multivariate time-series for learning meaningful patterns. The proposed approach allows for mixed time-series -- containing both pattern and non-pattern data -- such as for imprecise matches, outliers, stretching and global translating of patterns instances in time. We present the early results of our approach in the context of monitoring the health status of a person at home. The purpose is to build a behavioral profile of a person by analyzing the time variations of several quantitative or qualitative parameters recorded through a provision of sensors installed in the home.


title: Finding Approximate Palindromes in Strings Quickly and Simply

abstract: Described are two algorithms to find long approximate palindromes in a string, for example a DNA sequence. A simple algorithm requires O(n)-space and almost always runs in $O(k.n)$-time where n is the length of the string and k is the number of ``errors'' allowed in the palindrome. Its worst-case time-complexity is $O(n^2)$ but this does not occur with real biological sequences. A more complex algorithm guarantees $O(k.n)$ worst-case time complexity.


title: Jordan Normal and Rational Normal Form Algorithms

abstract: In this paper, we present a determinist Jordan normal form algorithms based on the Fadeev formula: \[(\lambda \cdot I-A) \cdot B(\lambda)=P(\lambda) \cdot I\] where $B(\lambda)$ is $(\lambda \cdot I-A)$'s comatrix and $P(\lambda)$ is $A$'s characteristic polynomial. This rational Jordan normal form algorithm differs from usual algorithms since it is not based on the Frobenius/Smith normal form but rather on the idea already remarked in Gantmacher that the non-zero column vectors of $B(\lambda_0)$ are eigenvectors of $A$ associated to $\lambda_0$ for any root $\lambda_0$ of the characteristical polynomial. The complexity of the algorithm is $O(n^4)$ field operations if we know the factorization of the characteristic polynomial (or $O(n^5 \ln(n))$ operations for a matrix of integers of fixed size). This algorithm has been implemented using the Maple and Giac/Xcas computer algebra systems.


title: The Accelerated Euclidean Algorithm

abstract: We present a new GCD algorithm of two integers or polynomials. The algorithm is iterative and its time complexity is still $O(n \\log^2 n ~ log \\log n)$ for $n$-bit inputs.


title: Exploring networks with traceroute-like probes: theory and simulations

abstract: Mapping the Internet generally consists in sampling the network from a limited set of sources by using traceroute-like probes. This methodology, akin to the merging of different spanning trees to a set of destination, has been argued to introduce uncontrolled sampling biases that might produce statistical properties of the sampled graph which sharply differ from the original ones. In this paper we explore these biases and provide a statistical analysis of their origin. We derive an analytical approximation for the probability of edge and vertex detection that exploits the role of the number of sources and targets and allows us to relate the global topological properties of the underlying network with the statistical accuracy of the sampled graph. In particular, we find that the edge and vertex detection probability depends on the betweenness centrality of each element. This allows us to show that shortest path routed sampling provides a better characterization of underlying graphs with broad distributions of connectivity. We complement the analytical discussion with a throughout numerical investigation of simulated mapping strategies in network models with different topologies. We show that sampled graphs provide a fair qualitative characterization of the statistical properties of the original networks in a fair range of different strategies and exploration parameters. Moreover, we characterize the level of redundancy and completeness of the exploration process as a function of the topological properties of the network. Finally, we study numerically how the fraction of vertices and edges discovered in the sampled graph depends on the particular deployements of probing sources. The results might hint the steps toward more efficient mapping strategies.


title: Measured descent: A new embedding method for finite metrics

abstract: We devise a new embedding technique, which we call measured descent, based on decomposing a metric space locally, at varying speeds, according to the density of some probability measure. This provides a refined and unified framework for the two primary methods of constructing Frechet embeddings for finite metrics, due to [Bourgain, 1985] and [Rao, 1999]. We prove that any n-point metric space (X,d) embeds in Hilbert space with distortion O(sqrt{alpha_X log n}), where alpha_X is a geometric estimate on the decomposability of X. As an immediate corollary, we obtain an O(sqrt{(log lambda_X) \log n}) distortion embedding, where \lambda_X is the doubling constant of X. Since \lambda_X\le n, this result recovers Bourgain's theorem, but when the metric X is, in a sense, ``low-dimensional,'' improved bounds are achieved. Our embeddings are volume-respecting for subsets of arbitrary size. One consequence is the existence of (k, O(log n)) volume-respecting embeddings for all 1 \leq k \leq n, which is the best possible, and answers positively a question posed by U. Feige. Our techniques are also used to answer positively a question of Y. Rabinovich, showing that any weighted n-point planar graph embeds in l_\infty^{O(log n)} with O(1) distortion. The O(log n) bound on the dimension is optimal, and improves upon the previously known bound of O((log n)^2).


title: A Fully Sparse Implementation of a Primal-Dual Interior-Point Potential Reduction Method for Semidefinite Programming

abstract: In this paper, we show a way to exploit sparsity in the problem data in a primal-dual potential reduction method for solving a class of semidefinite programs. When the problem data is sparse, the dual variable is also sparse, but the primal one is not. To avoid working with the dense primal variable, we apply Fukuda et al.'s theory of partial matrix completion and work with partial matrices instead. The other place in the algorithm where sparsity should be exploited is in the computation of the search direction, where the gradient and the Hessian-matrix product of the primal and dual barrier functions must be computed in every iteration. By using an idea from automatic differentiation in backward mode, both the gradient and the Hessian-matrix product can be computed in time proportional to the time needed to compute the barrier functions of sparse variables itself. Moreover, the high space complexity that is normally associated with the use of automatic differentiation in backward mode can be avoided in this case. In addition, we suggest a technique to efficiently compute the determinant of the positive definite matrix completion that is required to compute primal search directions. The method of obtaining one of the primal search directions that minimizes the number of the evaluations of the determinant of the positive definite completion is also proposed. We then implement the algorithm and test it on the problem of finding the maximum cut of a graph.


title: Toward a Human-Centered Uml for Risk Analysis

abstract: Safety is now a major concern in many complex systems such as medical robots. A way to control the complexity of such systems is to manage risk. The first and important step of this activity is risk analysis. During risk analysis, two main studies concerning human factors must be integrated: task analysis and human error analysis. This multidisciplinary analysis often leads to a work sharing between several stakeholders who use their own languages and techniques. This often produces consistency errors and understanding difficulties between them. Hence, this paper proposes to treat the risk analysis on the common expression language UML (Unified Modeling Language) and to handle human factors concepts for task analysis and human error analysis based on the features of this language. The approach is applied to the development of a medical robot for teleechography.


title: Successful E-Business Systems - Paypal

abstract: PayPal is an account-based system that allows anyone with an email address to send and receive online payment s. This service is easy to use for customers. Members can instantaneously send money to anyone. Recipients are informed by email that they have received a payment. PayPal is also available to people in 38 countries. This paper starts with introduction to the company and its services. The information about the history and the current company situation are covered. Later some interesting and different technical issues are discussed. The Paper ends with analysis of the company and several future recommendations.


title: Jartege: a Tool for Random Generation of Unit Tests for Java Classes

abstract: This report presents Jartege, a tool which allows random generation of unit tests for Java classes specified in JML. JML (Java Modeling Language) is a specification language for Java which allows one to write invariants for classes, and pre- and postconditions for operations. As in the JML-JUnit tool, we use JML specifications on the one hand to eliminate irrelevant test cases, and on the other hand as a test oracle. Jartege randomly generates test cases, which consist of a sequence of constructor and method calls for the classes under test. The random aspect of the tool can be parameterized by associating weights to classes and operations, and by controlling the number of instances which are created for each class under test. The practical use of Jartege is illustrated by a small case study.


title: Signals for Cellular Automata in dimension 2 or higher

abstract: We investigate how increasing the dimension of the array can help to draw signals on cellular automata.We show the existence of a gap of constructible signals in any dimension. We exhibit two cellular automata in dimension 2 to show that increasing the dimension allows to reduce the number of states required for some constructions.


title: Randomized Initialization of a Wireless Multihop Network

abstract: Address autoconfiguration is an important mechanism required to set the IP address of a node automatically in a wireless network. The address autoconfiguration, also known as initialization or naming, consists to give a unique identifier ranging from 1 to $n$ for a set of $n$ indistinguishable nodes. We consider a wireless network where $n$ nodes (processors) are randomly thrown in a square $X$, uniformly and independently. We assume that the network is synchronous and two nodes are able to communicate if they are within distance at most of $r$ of each other ($r$ is the transmitting/receiving range). The model of this paper concerns nodes without the collision detection ability: if two or more neighbors of a processor $u$ transmit concurrently at the same time, then $u$ would not receive either messages. We suppose also that nodes know neither the topology of the network nor the number of nodes in the network. Moreover, they start indistinguishable, anonymous and unnamed. Under this extremal scenario, we design and analyze a fully distributed protocol to achieve the initialization task for a wireless multihop network of $n$ nodes uniformly scattered in a square $X$. We show how the transmitting range of the deployed stations can affect the typical characteristics such as the degrees and the diameter of the network. By allowing the nodes to transmit at a range $r= \sqrt{\frac{(1+\ell) \ln{n} \SIZE}{\pi n}}$ (slightly greater than the one required to have a connected network), we show how to design a randomized protocol running in expected time $O(n^{3/2} \log^2{n})$ in order to assign a unique number ranging from 1 to $n$ to each of the $n$ participating nodes.


title: A Tutorial on the Expectation-Maximization Algorithm Including Maximum-Likelihood Estimation and EM Training of Probabilistic Context-Free Grammars

abstract: The paper gives a brief review of the expectation-maximization algorithm (Dempster 1977) in the comprehensible framework of discrete mathematics. In Section 2, two prominent estimation methods, the relative-frequency estimation and the maximum-likelihood estimation are presented. Section 3 is dedicated to the expectation-maximization algorithm and a simpler variant, the generalized expectation-maximization algorithm. In Section 4, two loaded dice are rolled. A more interesting example is presented in Section 5: The estimation of probabilistic context-free grammars.


title: Inside-Outside Estimation Meets Dynamic EM

abstract: We briefly review the inside-outside and EM algorithm for probabilistic context-free grammars. As a result, we formally prove that inside-outside estimation is a dynamic-programming variant of EM. This is interesting in its own right, but even more when considered in a theoretical context since the well-known convergence behavior of inside-outside estimation has been confirmed by many experiments but apparently has never been formally proved. However, being a version of EM, inside-outside estimation also inherits the good convergence behavior of EM. Therefore, the as yet imperfect line of argumentation can be transformed into a coherent proof.


title: An Analysis of the Skype Peer-to-Peer Internet Telephony Protocol

abstract: Skype is a peer-to-peer VoIP client developed by KaZaa in 2003. Skype claims that it can work almost seamlessly across NATs and firewalls and has better voice quality than the MSN and Yahoo IM applications. It encrypts calls end-to-end, and stores user information in a decentralized fashion. Skype also supports instant messaging and conferencing. This report analyzes key Skype functions such as login, NAT and firewall traversal, call establishment, media transfer, codecs, and conferencing under three different network setups. Analysis is performed by careful study of Skype network traffic.


title: Modeling Complex Higher Order Patterns

abstract: The goal of this paper is to show that generalizing the notion of frequent patterns can be useful in extending association analysis to more complex higher order patterns. To that end, we describe a general framework for modeling a complex pattern based on evaluating the interestingness of its sub-patterns. A key goal of any framework is to allow people to more easily express, explore, and communicate ideas, and hence, we illustrate how our framework can be used to describe a variety of commonly used patterns, such as frequent patterns, frequent closed patterns, indirect association patterns, hub patterns and authority patterns. To further illustrate the usefulness of the framework, we also present two new kinds of patterns that derived from the framework: clique pattern and bi-clique pattern and illustrate their practical use.


title: A Link Clustering Based Approach for Clustering Categorical Data

abstract: Categorical data clustering (CDC) and link clustering (LC) have been considered as separate research and application areas. The main focus of this paper is to investigate the commonalities between these two problems and the uses of these commonalities for the creation of new clustering algorithms for categorical data based on cross-fertilization between the two disjoint research fields. More precisely, we formally transform the CDC problem into an LC problem, and apply LC approach for clustering categorical data. Experimental results on real datasets show that LC based clustering method is competitive with existing CDC algorithms with respect to clustering accuracy.


title: Towards Reliable Network Wide Broadcast in Mobile Ad Hoc Networks

abstract: Network-Wide Broadcast (NWB) is a common operation in Mobile Ad hoc Networks (MANETs) used by routing protocols to discover routes and in group communication operations. NWB is commonly performed via flooding, which has been shown to be expensive in dense MANETs because of its high redundancy. Several efforts have targeted reducing the redundancy of floods. In this work, we target another problem that can substantially impact the success of NWBs: since MAC level broadcasts are unreliable, it is possible for critical rebroadcasts to be lost, leading to a significant drop in the node coverage. This is especially true under heavy load and in sparse topologies. We show that the techniques that target reducing the overhead of flooding, reduce its inherent redundancy and harm its reliability. In addition, we show that static approaches are more vulnerable to this problem. We then present a selective rebroadcast approach to improve the robustness of NWBs. We show that our approach leads to considerable improvement in NWB coverage relative to a recently proposed solution to this problem, with a small increase in overhead. The proposed approaches do not require proactive neighbor discovery and are therefore resilient to mobility. Finally, the solution can be added to virtually all NWB approaches to improve their reliability.


title: Finite Domain Bounds Consistency Revisited

abstract: A widely adopted approach to solving constraint satisfaction problems combines systematic tree search with constraint propagation for pruning the search space. Constraint propagation is performed by propagators implementing a certain notion of consistency. Bounds consistency is the method of choice for building propagators for arithmetic constraints and several global constraints in the finite integer domain. However, there has been some confusion in the definition of bounds consistency. In this paper we clarify the differences and similarities among the three commonly used notions of bounds consistency.


title: Zeno machines and hypercomputation

abstract: This paper reviews the Church-Turing Thesis (or rather, theses) with reference to their origin and application and considers some models of "hypercomputation", concentrating on perhaps the most straight-forward option: Zeno machines (Turing machines with accelerating clock). The halting problem is briefly discussed in a general context and the suggestion that it is an inevitable companion of any reasonable computational model is emphasised. It is hinted that claims to have "broken the Turing barrier" could be toned down and that the important and well-founded role of Turing computability in the mathematical sciences stands unchallenged.


title: Multidimensional data classification with artificial neural networks

abstract: Multi-dimensional data classification is an important and challenging problem in many astro-particle experiments. Neural networks have proved to be versatile and robust in multi-dimensional data classification. In this article we shall study the classification of gamma from the hadrons for the MAGIC Experiment. Two neural networks have been used for the classification task. One is Multi-Layer Perceptron based on supervised learning and other is Self-Organising Map (SOM), which is based on unsupervised learning technique. The results have been shown and the possible ways of combining these networks have been proposed to yield better and faster classification results.


title: Human-Level Performance on Word Analogy Questions by Latent Relational Analysis

abstract: This paper introduces Latent Relational Analysis (LRA), a method for measuring relational similarity. LRA has potential applications in many areas, including information extraction, word sense disambiguation, machine translation, and information retrieval. Relational similarity is correspondence between relations, in contrast with attributional similarity, which is correspondence between attributes. When two words have a high degree of attributional similarity, we call them synonyms. When two pairs of words have a high degree of relational similarity, we say that their relations are analogous. For example, the word pair mason/stone is analogous to the pair carpenter/wood. Past work on semantic similarity measures has mainly been concerned with attributional similarity. Recently the Vector Space Model (VSM) of information retrieval has been adapted to the task of measuring relational similarity, achieving a score of 47% on a collection of 374 college-level multiple-choice word analogy questions. In the VSM approach, the relation between a pair of words is characterized by a vector of frequencies of predefined patterns in a large corpus. LRA extends the VSM approach in three ways: (1) the patterns are derived automatically from the corpus (they are not predefined), (2) the Singular Value Decomposition (SVD) is used to smooth the frequency data (it is also used this way in Latent Semantic Analysis), and (3) automatically generated synonyms are used to explore reformulations of the word pairs. LRA achieves 56% on the 374 analogy questions, statistically equivalent to the average human score of 57%. On the related problem of classifying noun-modifier relations, LRA achieves similar gains over the VSM, while using a smaller corpus.


title: Minimum Dilation Stars

abstract: The dilation of a Euclidean graph is defined as the ratio of distance in the graph divided by distance in R^d. In this paper we consider the problem of positioning the root of a star such that the dilation of the resulting star is minimal. We present a deterministic O(n log n)-time algorithm for evaluating the dilation of a given star; a randomized O(n log n) expected-time algorithm for finding an optimal center in R^d; and for the case d=2, a randomized O(n 2^(alpha(n)) log^2 n) expected-time algorithm for finding an optimal center among the input points.


title: Removing Propagation Redundant Constraints in Redundant Modeling

abstract: A widely adopted approach to solving constraint satisfaction problems combines systematic tree search with various degrees of constraint propagation for pruning the search space. One common technique to improve the execution efficiency is to add redundant constraints, which are constraints logically implied by others in the problem model. However, some redundant constraints are propagation redundant and hence do not contribute additional propagation information to the constraint solver. Redundant constraints arise naturally in the process of redundant modeling where two models of the same problem are connected and combined through channeling constraints. In this paper, we give general theorems for proving propagation redundancy of one constraint with respect to channeling constraints and constraints in the other model. We illustrate, on problems from CSPlib (http://www.csplib.org/), how detecting and removing propagation redundant constraints in redundant modeling can significantly speed up constraint solving.


title: Correlated dynamics in human printing behavior

abstract: Arrival times of requests to print in a student laboratory were analyzed. Inter-arrival times between subsequent requests follow a universal scaling law relating time intervals and the size of the request, indicating a scale invariant dynamics with respect to the size. The cumulative distribution of file sizes is well-described by a modified power law often seen in non-equilibrium critical systems. For each user, waiting times between their individual requests show long range dependence and are broadly distributed from seconds to weeks. All results are incompatible with Poisson models, and may provide evidence of critical dynamics associated with voluntary thought processes in the brain.


title: A feasible algorithm for typing in Elementary Affine Logic

abstract: We give a new type inference algorithm for typing lambda-terms in Elementary Affine Logic (EAL), which is motivated by applications to complexity and optimal reduction. Following previous references on this topic, the variant of EAL type system we consider (denoted EAL*) is a variant without sharing and without polymorphism. Our algorithm improves over the ones already known in that it offers a better complexity bound: if a simple type derivation for the term t is given our algorithm performs EAL* type inference in polynomial time.


title: The modular technology of development of the CAD expansions: profiles of outside networks of water supply and water drain

abstract: The modular technology of development of the problem-oriented CAD expansions is applied to a task of designing of profiles of outside networks of water supply and water drain with realization in program system TechnoCAD GlassX. The unity of structure of this profiles is revealed, the system model of the drawings of profiles of networks is developed including the structured parametric representation (properties of objects and their interdependence, general settings and default settings) and operations with it, which efficiently automate designing


title: The modular technology of development of the CAD expansions: protection of the buildings from the lightning

abstract: The modular technology of development of the problem-oriented CAD expansions is applied to a task of designing of protection of the buildings from the lightning with realization in program system TechnoCAD GlassX. The system model of the drawings of lightning protection is developed including the structured parametric representation (properties of objects and their interdependence, general settings and default settings) and operations with it, which efficiently automate designing


title: The Features of the Complex CAD system of Reconstruction of the Industrial Plants

abstract: The features of designing of reconstruction of the acting plant by its design department are considered: the results of work are drawings corresponding with the national standards; large number of the small projects for different acting objects; variety of the types of the drawings in one project; large paper archive. The models and methods of developing of the complex CAD system with friend uniform environment of designing, with setting a profile of operations, with usage of the general parts of the project, with a series of problem-oriented subsystems are described on an example of a CAD system TechnoCAD GlassX


title: The methods of support of the requirements of the Russian standards at development of a CAD of industrial objects

abstract: The methods of support of the requirements of the Russian standards in a CAD of industrial objects are explained, which were implemented in the CAD system TechnoCAD GlassX with an own graphics core and own structures of data storage. It is rotined, that the binding of storage structures and program code of a CAD to the requirements of standards enable not only to fulfil these requirements in project documentation, but also to increase a degree of compactness of storage of drawings both on the disk and in the RAM


title: The modelling of the build constructions in a CAD of the renovation of the enterprises by means of units in the drawings

abstract: The parametric model of build constructions and features of design operations are described for making drawings, which are the common component of the different parts of the projects of renovation of enterprises. The key moment of the deep design automation is the using of so-called units in the drawings, which are joining a visible graphic part and invisible parameters. The model has passed check during designing of several hundreds of drawings


title: The informatization of design works at industry firm during its renovation

abstract: The characteristic of design works on firm at its renovation and of the common directions of their informatization is given. The implantation of a CAD is selected as the key direction, and the requirements to a complex CAD-system are stated. The methods of such a CAD-system development are featured, and the connectedness of this development with the process of integration of information space of design department of the firm is characterized. The experience of development and implantation of a complex CAD of renovation of firms TechnoCAD GlassX lies in a basis of this reviewing


title: Deployment of a Grid-based Medical Imaging Application

abstract: The MammoGrid project has deployed its Service-Oriented Architecture (SOA)-based Grid application in a real environment comprising actual participating hospitals. The resultant setup is currently being exploited to conduct rigorous in-house tests in the first phase before handing over the setup to the actual clinicians to get their feedback. This paper elaborates the deployment details and the experiences acquired during this phase of the project. Finally the strategy regarding migration to an upcoming middleware from EGEE project will be described. This paper concludes by highlighting some of the potential areas of future work.


title: Reverse Engineering Ontology to Conceptual Data Models

abstract: Ontologies facilitate the integration of heterogeneous data sources by resolving semantic heterogeneity between them. This research aims to study the possibility of generating a domain conceptual model from a given ontology with the vision to grow this generated conceptual data model into a global conceptual model integrating a number of existing data and information sources. Based on ontologically derived semantics of the BWW model, rules are identified that map elements of the ontology language (DAML+OIL) to domain conceptual model elements. This mapping is demonstrated using TAMBIS ontology. A significant corollary of this study is that it is possible to generate a domain conceptual model from a given ontology subject to validation that needs to be performed by the domain specialist before evolving this model into a global conceptual model.


title: A Statistical Framework for Efficient Monitoring of End-to-End Network Properties

abstract: Network service providers and customers are often concerned with aggregate performance measures that span multiple network paths. Unfortunately, forming such network-wide measures can be difficult, due to the issues of scale involved. In particular, the number of paths grows too rapidly with the number of endpoints to make exhaustive measurement practical. As a result, there is interest in the feasibility of methods that dramatically reduce the number of paths measured in such situations while maintaining acceptable accuracy. In previous work we proposed a statistical framework to efficiently address this problem, in the context of additive metrics such as delay and loss rate, for which the per-path metric is a sum of (possibly transformed) per-link measures. The key to our method lies in the observation and exploitation of significant redundancy in network paths (sharing of common links). In this paper we make three contributions: (1) we generalize the framework to make it more immediately applicable to network measurements encountered in practice; (2) we demonstrate that the observed path redundancy upon which our method is based is robust to variation in key network conditions and characteristics, including link failures; and (3) we show how the framework may be applied to address three practical problems of interest to network providers and customers, using data from an operating network. In particular, we show how appropriate selection of small sets of path measurements can be used to accurately estimate network-wide averages of path delays, to reliably detect network anomalies, and to effectively make a choice between alternative sub-networks, as a customer choosing between two providers or two ingress points into a provider network.


title: Tycoon: an Implementation of a Distributed, Market-based Resource Allocation System

abstract: Distributed clusters like the Grid and PlanetLab enable the same statistical multiplexing efficiency gains for computing as the Internet provides for networking. One major challenge is allocating resources in an economically efficient and low-latency way. A common solution is proportional share, where users each get resources in proportion to their pre-defined weight. However, this does not allow users to differentiate the value of their jobs. This leads to economic inefficiency. In contrast, systems that require reservations impose a high latency (typically minutes to hours) to acquire resources. We present Tycoon, a market based distributed resource allocation system based on proportional share. The key advantages of Tycoon are that it allows users to differentiate the value of their jobs, its resource acquisition latency is limited only by communication delays, and it imposes no manual bidding overhead on users. We present experimental results using a prototype implementation of our design.


title: Security in Carrier Class Server Applications for All-IP Networks

abstract: A revolution is taking place in telecommunication networks. New services are appearing on platforms such as third generation cellular phones (3G) and broadband Internet access. This motivates the transition from mostly switched to all-IP networks. The replacement of the traditional shallow and well-defined interface to telephony networks brings accrued flexibility, but also makes the network accordingly difficult to properly secure. This paper surveys the implications of this transition on security issues in telecom applications. It does not give an exhaustive list of security tools or security protocols. Its goal is rather to initiate the reader to the security issues brought to carrier class servers by this revolution.


title: Data-stationary Architecture to Execute Quantum Algorithms Classically

abstract: This paper presents a data stationary architecture in which each word has an attached address field. Address fields massively update in parallel to record data interchanges. Words do not move until memory is read for post processing. A sea of such cells can test large-scale quantum algorithms, although other programming is possible.


title: An Efficient and Flexible Engine for Computing Fixed Points

abstract: An efficient and flexible engine for computing fixed points is critical for many practical applications. In this paper, we firstly present a goal-directed fixed point computation strategy in the logic programming paradigm. The strategy adopts a tabled resolution (or memorized resolution) to mimic the efficient semi-naive bottom-up computation. Its main idea is to dynamically identify and record those clauses that will lead to recursive variant calls, and then repetitively apply those alternatives incrementally until the fixed point is reached. Secondly, there are many situations in which a fixed point contains a large number or even infinite number of solutions. In these cases, a fixed point computation engine may not be efficient enough or feasible at all. We present a mode-declaration scheme which provides the capabilities to reduce a fixed point from a big solution set to a preferred small one, or from an infeasible infinite set to a finite one. The mode declaration scheme can be characterized as a meta-level operation over the original fixed point. We show the correctness of the mode declaration scheme. Thirdly, the mode-declaration scheme provides a new declarative method for dynamic programming, which is typically used for solving optimization problems. There is no need to define the value of an optimal solution recursively, instead, defining a general solution suffices. The optimal value as well as its corresponding concrete solution can be derived implicitly and automatically using a mode-directed fixed point computation engine. Finally, this fixed point computation engine has been successfully implemented in a commercial Prolog system. Experimental results are shown to indicate that the mode declaration improves both time and space performances in solving dynamic programming problems.


title: The approximability of three-valued MAX CSP

abstract: In the maximum constraint satisfaction problem (Max CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given domain to the variables so as to maximize the number (or the total weight, for the weighted case) of satisfied constraints. This problem is NP-hard in general, and, therefore, it is natural to study how restricting the allowed types of constraints affects the approximability of the problem. It is known that every Boolean (that is, two-valued) Max CSP problem with a finite set of allowed constraint types is either solvable exactly in polynomial time or else APX-complete (and hence can have no polynomial time approximation scheme unless P=NP. It has been an open problem for several years whether this result can be extended to non-Boolean Max CSP, which is much more difficult to analyze than the Boolean case. In this paper, we make the first step in this direction by establishing this result for Max CSP over a three-element domain. Moreover, we present a simple description of all polynomial-time solvable cases of our problem. This description uses the well-known algebraic combinatorial property of supermodularity. We also show that every hard three-valued Max CSP problem contains, in a certain specified sense, one of the two basic hard Max CSP problems which are the Maximum k-colourable subgraph problems for k=2,3.


title: Widening Operators for Weakly-Relational Numeric Abstractions (Extended Abstract)

abstract: We discuss the divergence problems recently identified in some extrapolation operators for weakly-relational numeric domains. We identify the cause of the divergences and point out that resorting to more concrete, syntactic domains can be avoided by researching suitable algorithms for the elimination of redundant constraints in the chosen representation.


title: TulaFale: A Security Tool for Web Services

abstract: Web services security specifications are typically expressed as a mixture of XML schemas, example messages, and narrative explanations. We propose a new specification language for writing complementary machine-checkable descriptions of SOAP-based security protocols and their properties. Our TulaFale language is based on the pi calculus (for writing collections of SOAP processors running in parallel), plus XML syntax (to express SOAP messaging), logical predicates (to construct and filter SOAP messages), and correspondence assertions (to specify authentication goals of protocols). Our implementation compiles TulaFale into the applied pi calculus, and then runs Blanchet's resolution-based protocol verifier. Hence, we can automatically verify authentication properties of SOAP protocols.


title: Validating a Web Service Security Abstraction by Typing

abstract: An XML web service is, to a first approximation, an RPC service in which requests and responses are encoded in XML as SOAP envelopes, and transported over HTTP. We consider the problem of authenticating requests and responses at the SOAP-level, rather than relying on transport-level security. We propose a security abstraction, inspired by earlier work on secure RPC, in which the methods exported by a web service are annotated with one of three security levels: none, authenticated, or both authenticated and encrypted. We model our abstraction as an object calculus with primitives for defining and calling web services. We describe the semantics of our object calculus by translating to a lower-level language with primitives for message passing and cryptography. To validate our semantics, we embed correspondence assertions that specify the correct authentication of requests and responses. By appeal to the type theory for cryptographic protocols of Gordon and Jeffrey's Cryptyc, we verify the correspondence assertions simply by typing. Finally, we describe an implementation of our semantics via custom SOAP headers.


title: Quasiconvex Programming

abstract: We define quasiconvex programming, a form of generalized linear programming in which one seeks the point minimizing the pointwise maximum of a collection of quasiconvex functions. We survey algorithms for solving quasiconvex programs either numerically or via generalizations of the dual simplex method from linear programming, and describe varied applications of this geometric optimization technique in meshing, scientific computation, information visualization, automated algorithm analysis, and robust statistics.


title: A Social Network for Societal-Scale Decision-Making Systems

abstract: In societal-scale decision-making systems the collective is faced with the problem of ensuring that the derived group decision is in accord with the collective's intention. In modern systems, political institutions have instatiated representative forms of decision-making to ensure that every individual in the society has a participatory voice in the decision-making behavior of the whole--even if only indirectly through representation. An agent-based simulation demonstrates that in modern representative systems, as the ratio of representatives increases, there exists an exponential decrease in the ability for the group to behave in accord with the desires of the whole. To remedy this issue, this paper provides a novel representative power structure for decision-making that utilizes a social network and power distribution algorithm to maintain the collective's perspective over varying degrees of participation and/or ratios of representation. This work shows promise for the future development of policy-making systems that are supported by the computer and network infrastructure of our society.


title: On computing fixed points for generalized sandpiles

abstract: We prove fixed points results for sandpiles starting with arbitrary initial conditions. We give an effective algorithm for computing such fixed points, and we refine it in the particular case of SPM.


title: Neural Networks in Mobile Robot Motion

abstract: This paper deals with a path planning and intelligent control of an autonomous robot which should move safely in partially structured environment. This environment may involve any number of obstacles of arbitrary shape and size; some of them are allowed to move. We describe our approach to solving the motion-planning problem in mobile robot control using neural networks-based technique. Our method of the construction of a collision-free path for moving robot among obstacles is based on two neural networks. The first neural network is used to determine the "free" space using ultrasound range finder data. The second neural network "finds" a safe direction for the next robot section of the path in the workspace while avoiding the nearest obstacles. Simulation examples of generated path with proposed techniques will be presented.


title: Gyroscopically Stabilized Robot: Balance and Tracking

abstract: The single wheel, gyroscopically stabilized robot - Gyrover, is a dynamically stable but statically unstable, underactuated system. In this paper, based on the dynamic model of the robot, we investigate two classes of nonholonomic constraints associated with the system. Then, based on the backstepping technology, we propose a control law for balance control of Gyrover. Next, through transferring the systems states from Cartesian coordinate to polar coordinate, control laws for point-to-point control and line tracking in Cartesian space are provided.


title: Dynamic replanning in uncertain environments for a sewer inspection robot

abstract: The sewer inspection robot MAKRO is an autonomous multi-segment robot with worm-like shape driven by wheels. It is currently under development in the project MAKRO-PLUS. The robot has to navigate autonomously within sewer systems. Its first tasks will be to take water probes, analyze it onboard, and measure positions of manholes and pipes to detect polluted-loaded sewage and to improve current maps of sewer systems. One of the challenging problems is the controller software, which should enable the robot to navigate in the sewer system and perform the inspection tasks autonomously, not inflicting any self-damage. This paper focuses on the route planning and replanning aspect of the robot. The robots software has four different levels, of which the planning system is the highest level, and the remaining three are controller levels each with a different degree of abstraction. The planner coordinates the sequence of actions that are to be successively executed by the robot.


title: WebotsTM: Professional Mobile Robot Simulation

abstract: Cyberbotics Ltd. develops WebotsTM, a mobile robotics simulation software that provides you with a rapid prototyping environment for modelling, programming and simulating mobile robots. The provided robot libraries enable you to transfer your control programs to several commercially available real mobile robots. WebotsTM lets you define and modify a complete mobile robotics setup, even several different robots sharing the same environment. For each object, you can define a number of properties, such as shape, color, texture, mass, friction, etc. You can equip each robot with a large number of available sensors and actuators. You can program these robots using your favorite development environment, simulate them and optionally transfer the resulting programs onto your real robots. WebotsTM has been developed in collaboration with the Swiss Federal Institute of Technology in Lausanne, thoroughly tested, well documented and continuously maintained for over 7 years. It is now the main commercial product available from Cyberbotics Ltd.


title: Dynamic simulation of task constrained of a rigid-flexible manipulator

abstract: A rigid-flexible manipulator may be assigned tasks in a moving environment where the winds or vibrations affect the position and/or orientation of surface of operation. Consequently, losses of the contact and perhaps degradation of the performance may occur as references are changed. When the environment is moving, knowledge of the angle α between the contact surface and the horizontal is required at every instant. In this paper, different profiles for the time varying angle α are proposed to investigate the effect of this change into the contact force and the joint torques of a rigid-flexible manipulator. The coefficients of the equation of the proposed rotating surface are changing with time to determine the new X and Y coordinates of the moving surface as the surface rotates.


title: Assembly and Disassembly Planning by using Fuzzy Logic & Genetic Algorithms

abstract: The authors propose the implementation of hybrid Fuzzy Logic-Genetic Algorithm (FL-GA) methodology to plan the automatic assembly and disassembly sequence of products. The GA-Fuzzy Logic approach is implemented onto two levels. The first level of hybridization consists of the development of a Fuzzy controller for the parameters of an assembly or disassembly planner based on GAs. This controller acts on mutation probability and crossover rate in order to adapt their values dynamically while the algorithm runs. The second level consists of the identification of theoptimal assembly or disassembly sequence by a Fuzzy function, in order to obtain a closer control of the technological knowledge of the assembly/disassembly process. Two case studies were analyzed in order to test the efficiency of the Fuzzy-GA methodologies.


title: Robotic Applications in Cardiac Surgery

abstract: Traditionally, cardiac surgery has been performed through a median sternotomy, which allows the surgeon generous access to the heart and surrounding great vessels. As a paradigm shift in the size and location of incisions occurs in cardiac surgery, new methods have been developed to allow the surgeon the same amount of dexterity and accessibility to the heart in confined spaces and in a less invasive manner. Initially, long instruments without pivot points were used, however, more recent robotic telemanipulation systems have been applied that allow for improved dexterity, enabling the surgeon to perform cardiac surgery from a distance not previously possible. In this rapidly evolving field, we review the recent history and clinical results of using robotics in cardiac surgery.


title: One-Chip Solution to Intelligent Robot Control: Implementing Hexapod Subsumption Architecture Using a Contemporary Microprocessor

abstract: This paper introduces a six-legged autonomous robot managed by a single controller and a software core modeled on subsumption architecture. We begin by discussing the features and capabilities of IsoPod, a new processor for robotics which has enabled a streamlined implementation of our project. We argue that this processor offers a unique set of hardware and software features, making it a practical development platform for robotics in general and for subsumption-based control architectures in particular. Next, we summarize original ideas on subsumption architecture implementation for a six-legged robot, as presented by its inventor Rodney Brooks in 1980s. A comparison is then made to a more recent example of a hexapod control architecture based on subsumption. The merits of both systems are analyzed and a new subsumption architecture layout is formulated as a response. We conclude with some remarks regarding the development of this project as a hint at new potentials for intelligent robot design, opened by a recent development in embedded controller market.


title: How to achieve various gait patterns from single nominal

abstract: In this paper is presented an approach to achieving on-line modification of nominal biped gait without recomputing entire dynamics when steady motion is performed. Straight, dynamically balanced walk was used as a nominal gait, and applied modifications were speed-up and slow-down walk and turning left and right. It is shown that the disturbances caused by these modifications jeopardize dynamic stability, but they can be simply compensated to enable walk continuation.


title: Clustering Categorical Data Streams

abstract: The data stream model has been defined for new classes of applications involving massive data being generated at a fast pace. Web click stream analysis and detection of network intrusions are two examples. Cluster analysis on data streams becomes more difficult, because the data objects in a data stream must be accessed in order and can be read only once or few times with limited resources. Recently, a few clustering algorithms have been developed for analyzing numeric data streams. However, to our knowledge to date, no algorithm exists for clustering categorical data streams. In this paper, we propose an efficient clustering algorithm for analyzing categorical data streams. It has been proved that the proposed algorithm uses small memory footprints. We provide empirical analysis on the performance of the algorithm in clustering both synthetic and real data streams


title: Vector Symbolic Architectures answer Jackendoff's challenges for cognitive neuroscience

abstract: Jackendoff (2002) posed four challenges that linguistic combinatoriality and rules of language present to theories of brain function. The essence of these problems is the question of how to neurally instantiate the rapid construction and transformation of the compositional structures that are typically taken to be the domain of symbolic processing. He contended that typical connectionist approaches fail to meet these challenges and that the dialogue between linguistic theory and cognitive neuroscience will be relatively unproductive until the importance of these problems is widely recognised and the challenges answered by some technical innovation in connectionist modelling. This paper claims that a little-known family of connectionist models (Vector Symbolic Architectures) are able to meet Jackendoff's challenges.


title: Monotonicity Results for Coherent MIMO Rician Channels

abstract: The dependence of the Gaussian input information rate on the line-of-sight (LOS) matrix in multiple-input multiple-output coherent Rician fading channels is explored. It is proved that the outage probability and the mutual information induced by a multivariate circularly symmetric Gaussian input with any covariance matrix are monotonic in the LOS matrix D, or more precisely, monotonic in D'D in the sense of the Loewner partial order. Conversely, it is also demonstrated that this ordering on the LOS matrices is a necessary condition for the uniform monotonicity over all input covariance matrices. This result is subsequently applied to prove the monotonicity of the isotropic Gaussian input information rate and channel capacity in the singular values of the LOS matrix. Extensions to multiple-access channels are also discussed.


title: Free quasi-symmetric functions, product actions and quantum field theory of partitions

abstract: We examine two associative products over the ring of symmetric functions related to the intransitive and Cartesian products of permutation groups. As an application, we give an enumeration of some Feynman type diagrams arising in Bender's QFT of partitions. We end by exploring possibilities to construct noncommutative analogues.


title: Isomorphic Implication

abstract: We study the isomorphic implication problem for Boolean constraints. We show that this is a natural analog of the subgraph isomorphism problem. We prove that, depending on the set of constraints, this problem is in P, NP-complete, or NP-hard, coNP-hard, and in parallel access to NP. We show how to extend the NP-hardness and coNP-hardness to hardness for parallel access to NP for some cases, and conjecture that this can be done in all cases.


title: Labelled transition systems as a Stone space

abstract: A fully abstract and universal domain model for modal transition systems and refinement is shown to be a maximal-points space model for the bisimulation quotient of labelled transition systems over a finite set of events. In this domain model we prove that this quotient is a Stone space whose compact, zero-dimensional, and ultra-metrizable Hausdorff topology measures the degree of bisimilarity such that image-finite labelled transition systems are dense. Using this compactness we show that the set of labelled transition systems that refine a modal transition system, its ''set of implementations'', is compact and derive a compactness theorem for Hennessy-Milner logic on such implementation sets. These results extend to systems that also have partially specified state propositions, unify existing denotational, operational, and metric semantics on partial processes, render robust consistency measures for modal transition systems, and yield an abstract interpretation of compact sets of labelled transition systems as Scott-closed sets of modal transition systems.


title: Collective Intelligence Quanitifed for Computer-Mediated Group Problem Solving

abstract: Collective Intelligence (CI) is the ability of a group to exhibit greater intelligence than its individual members. Expressed by the common saying that "two minds are better than one," CI has been a topic of interest for social psychology and the information sciences. Computer mediation adds a new element in the form of distributed networks and group support systems. These facilitate highly organized group activities that were all but impossible before computer mediation. This paper presents experimental findings on group problem solving where a distributed software system automatically integrates input from many humans. In order to quantify Collective Intelligence, we compare the performance of groups to individuals when solving a mathematically formalized problem. This study shows that groups can outperform individuals on difficult but not easy problems, though groups are slower to produce solutions. The subjects are 57 university students. The task is the 8-Puzzle sliding tile game.


title: A Framework for Creating Natural Language User Interfaces for Action-Based Applications

abstract: In this paper we present a framework for creating natural language interfaces to action-based applications. Our framework uses a number of reusable application-independent components, in order to reduce the effort of creating a natural language interface for a given application. Using a type-logical grammar, we first translate natural language sentences into expressions in an extended higher-order logic. These expressions can be seen as executable specifications corresponding to the original sentences. The executable specifications are then interpreted by invoking appropriate procedures provided by the application for which a natural language interface is being created.


title: From Feature Extraction to Classification: A multidisciplinary Approach applied to Portuguese Granites

abstract: The purpose of this paper is to present a complete methodology based on a multidisciplinary approach, that goes from the extraction of features till the classification of a set of different portuguese granites. The set of tools to extract the features that characterise polished surfaces of the granites is mainly based on mathematical morphology. The classification methodology is based on a genetic algorithm capable of search the input feature space used by the nearest neighbour rule classifier. Results show that is adequate to perform feature reduction and simultaneous improve the recognition rate. Moreover, the present methodology represents a robust strategy to understand the proper nature of the images treated, and their discriminant features. KEYWORDS: Portuguese grey granites, feature extraction, mathematical morphology, feature reduction, genetic algorithms, nearest neighbour rule classifiers (k-NNR).


title: Complete Characterization of the Equivalent MIMO Channel for Quasi-Orthogonal Space-Time Codes

abstract: Recently, a quasi-orthogonal space-time block code (QSTBC) capable of achieving a significant fraction of the outage mutual information of a multiple-input-multiple output (MIMO) wireless communication system for the case of four transmit and one receive antennas was proposed. We generalize these results to $n_T=2^n$ transmit and an arbitrary number of receive antennas $n_R$. Furthermore, we completely characterize the structure of the equivalent channel for the general case and show that for all $n_T=2^n$ and $n_R$ the eigenvectors of the equivalent channel are fixed and independent from the channel realization. Furthermore, the eigenvalues of the equivalent channel are independent identically distributed random variables each following a noncentral chi-square distribution with $4n_R$ degrees of freedom. Based on these important insights into the structure of the QSTBC, we derive an analytical lower bound for the fraction of outage probability achieved with QSTBC and show that this bound is tight for low signal-to-noise-ratios (SNR) values and also for increasing number of receive antennas. We also present an upper bound, which is tight for high SNR values and derive analytical expressions for the case of four transmit antennas. Finally, by utilizing the special structure of the QSTBC we propose a new transmit strategy, which decouples the signals transmitted from different antennas in order to detect the symbols separately with a linear ML-detector rather than joint detection, an up to now only known advantage of orthogonal space-time block codes (OSTBC).


title: ANTIDS: Self-Organized Ant-based Clustering Model for Intrusion Detection System

abstract: Security of computers and the networks that connect them is increasingly becoming of great significance. Computer security is defined as the protection of computing systems against threats to confidentiality, integrity, and availability. There are two types of intruders: the external intruders who are unauthorized users of the machines they attack, and internal intruders, who have permission to access the system with some restrictions. Due to the fact that it is more and more improbable to a system administrator to recognize and manually intervene to stop an attack, there is an increasing recognition that ID systems should have a lot to earn on following its basic principles on the behavior of complex natural systems, namely in what refers to self-organization, allowing for a real distributed and collective perception of this phenomena. With that aim in mind, the present work presents a self-organized ant colony based intrusion detection system (ANTIDS) to detect intrusions in a network infrastructure. The performance is compared among conventional soft computing paradigms like Decision Trees, Support Vector Machines and Linear Genetic Programming to model fast, online and efficient intrusion detection systems.


title: Swarming around Shellfish Larvae

abstract: The collection of wild larvae seed as a source of raw material is a major sub industry of shellfish aquaculture. To predict when, where and in what quantities wild seed will be available, it is necessary to track the appearance and growth of planktonic larvae. One of the most difficult groups to identify, particularly at the species level are the Bivalvia. This difficulty arises from the fact that fundamentally all bivalve larvae have a similar shape and colour. Identification based on gross morphological appearance is limited by the time-consuming nature of the microscopic examination and by the limited availability of expertise in this field. Molecular and immunological methods are also being studied. We describe the application of computational pattern recognition methods to the automated identification and size analysis of scallop larvae. For identification, the shape features used are binary invariant moments; that is, the features are invariant to shift (position within the image), scale (induced either by growth or differential image magnification) and rotation. Images of a sample of scallop and non-scallop larvae covering a range of maturities have been analysed. In order to overcome the automatic identification, as well as to allow the system to receive new unknown samples at any moment, a self-organized and unsupervised ant-like clustering algorithm based on Swarm Intelligence is proposed, followed by simple k-NNR nearest neighbour classification on the final map. Results achieve a full recognition rate of 100% under several situations (k =1 or 3).


title: Less is More - Genetic Optimisation of Nearest Neighbour Classifiers

abstract: The present paper deals with optimisation of Nearest Neighbour rule Classifiers via Genetic Algorithms. The methodology consists on implement a Genetic Algorithm capable of search the input feature space used by the NNR classifier. Results show that is adequate to perform feature reduction and simultaneous improve the Recognition Rate. Some practical examples prove that is possible to Recognise Portuguese Granites in 100%, with only 3 morphological features (from an original set of 117 features), which is well suited for real time applications. Moreover, the present method represents a robust strategy to understand the proper nature of the images treated, and their discriminant features. KEYWORDS: Feature Reduction, Genetic Algorithms, Nearest Neighbour Rule Classifiers (k-NNR).


title: Web Usage Mining Using Artificial Ant Colony Clustering and Genetic Programming

abstract: The rapid e-commerce growth has made both business community and customers face a new situation. Due to intense competition on one hand and the customer's option to choose from several alternatives business community has realized the necessity of intelligent marketing strategies and relationship management. Web usage mining attempts to discover useful knowledge from the secondary data obtained from the interactions of the users with the Web. Web usage mining has become very critical for effective Web site management, creating adaptive Web sites, business and support services, personalization, network traffic flow analysis and so on. The study of ant colonies behavior and their self-organizing capabilities is of interest to knowledge retrieval/management and decision support systems sciences, because it provides models of distributed adaptive organization, which are useful to solve difficult optimization, classification, and distributed control problems, among others. In this paper, we propose an ant clustering algorithm to discover Web usage patterns (data clusters) and a linear genetic programming approach to analyze the visitor trends. Empirical results clearly shows that ant colony clustering performs well when compared to a self-organizing map (for clustering Web usage patterns) even though the performance accuracy is not that efficient when comparared to evolutionary-fuzzy clustering (i-miner) approach. KEYWORDS: Web Usage Mining, Swarm Intelligence, Ant Systems, Stigmergy, Data-Mining, Linear Genetic Programming.


title: Swarms on Continuous Data

abstract: While being it extremely important, many Exploratory Data Analysis (EDA) systems have the inhability to perform classification and visualization in a continuous basis or to self-organize new data-items into the older ones (evenmore into new labels if necessary), which can be crucial in KDD - Knowledge Discovery, Retrieval and Data Mining Systems (interactive and online forms of Web Applications are just one example). This disadvantge is also present in more recent approaches using Self-Organizing Maps. On the present work, and exploiting past sucesses in recently proposed Stigmergic Ant Systems a robust online classifier is presented, which produces class decisions on a continuous stream data, allowing for continuous mappings. Results show that increasingly better results are achieved, as demonstraded by other authors in different areas. KEYWORDS: Swarm Intelligence, Ant Systems, Stigmergy, Data-Mining, Exploratory Data Analysis, Image Retrieval, Continuous Classification.


title: Self-Organizing the Abstract: Canvas as a Swarm Habitat for Collective Memory, Perception and Cooperative Distributed Creativity

abstract: Past experiences under the designation of "Swarm Paintings" conducted in 2001, not only confirmed the possibility of realizing an artificial art (thus non-human), as introduced into the process the questioning of creative migration, specifically from the computer monitors to the canvas via a robotic harm. In more recent self-organized based research we seek to develop and profound the initial ideas by using a swarm of autonomous robots (ARTsBOT project 2002-03), that "live" avoiding the purpose of being merely a simple perpetrator of order streams coming from an external computer, but instead, that actually co-evolve within the canvas space, acting (that is, laying ink) according to simple inner threshold stimulus response functions, reacting simultaneously to the chromatic stimulus present in the canvas environment done by the passage of their team-mates, as well as by the distributed feedback, affecting their future collective behaviour. In parallel, and in what respects to certain types of collective systems, we seek to confirm, in a physically embedded way, that the emergence of order (even as a concept) seems to be found at a lower level of complexity, based on simple and basic interchange of information, and on the local dynamic of parts, who, by self-organizing mechanisms tend to form an lived whole, innovative and adapting, allowing for emergent open-ended creative and distributed production. KEYWORDS: ArtSBots Project, Swarm Intelligence, Stigmergy, UnManned Art, Symbiotic Art, Swarm Paintings, Robot Paintings, Non-Human Art, Painting Emergence and Cooperation, Art and Complexity, ArtBots: The Robot Talent Show.


title: Threats of Human Error in a High-Performance Storage System: Problem Statement and Case Study

abstract: System administration is a difficult, often tedious, job requiring many skilled laborers. The data that is protected by system administrators is often valued at or above the value of the institution maintaining that data. A number of ethnographic studies have confirmed the skill of these operators, and the difficulty of providing adequate tools. In an effort to minimize the maintenance costs, an increasing portion of system administration is subject to automation - particularly simple, routine tasks such as data backup. While such tools reduce the risk of errors from carelessness, the same tools may result in reduced skill and system familiarity in experienced workers. Care should be taken to ensure that operators maintain system awareness without placing the operator in a passive, monitoring role.


title: Self-Organized Stigmergic Document Maps: Environment as a Mechanism for Context Learning

abstract: Social insect societies and more specifically ant colonies, are distributed systems that, in spite of the simplicity of their individuals, present a highly structured social organization. As a result of this organization, ant colonies can accomplish complex tasks that in some cases exceed the individual capabilities of a single ant. The study of ant colonies behavior and of their self-organizing capabilities is of interest to knowledge retrieval/management and decision support systems sciences, because it provides models of distributed adaptive organization which are useful to solve difficult optimization, classification, and distributed control problems, among others. In the present work we overview some models derived from the observation of real ants, emphasizing the role played by stigmergy as distributed communication paradigm, and we present a novel strategy to tackle unsupervised clustering as well as data retrieval problems. The present ant clustering system (ACLUSTER) avoids not only short-term memory based strategies, as well as the use of several artificial ant types (using different speeds), present in some recent approaches. Moreover and according to our knowledge, this is also the first application of ant systems into textual document clustering. KEYWORDS: Swarm Intelligence, Ant Systems, Unsupervised Clustering, Data Retrieval, Data Mining, Distributed Computing, Document Maps, Textual Document Clustering.


title: Clustering Techniques for Marbles Classification

abstract: Automatic marbles classification based on their visual appearance is an important industrial issue. However, there is no definitive solution to the problem mainly due to the presence of randomly distributed high number of different colours and its subjective evaluation by the human expert. In this paper we present a study of segmentation techniques, we evaluate they overall performance using a training set and standard quality measures and finally we apply different clustering techniques to automatically classify the marbles. KEYWORDS: Segmentation, Clustering, Quadtrees, Learning Vector Quantization (LVQ), Simulated Annealing (SA).


title: On the Implicit and on the Artificial - Morphogenesis and Emergent Aesthetics in Autonomous Collective Systems

abstract: Imagine a "machine" where there is no pre-commitment to any particular representational scheme: the desired behaviour is distributed and roughly specified simultaneously among many parts, but there is minimal specification of the mechanism required to generate that behaviour, i.e. the global behaviour evolves from the many relations of multiple simple behaviours. A machine that lives to and from/with Synergy. An artificial super-organism that avoids specific constraints and emerges within multiple low-level implicit bio-inspired mechanisms. KEYWORDS: Complex Science, ArtSBots Project, Swarm Intelligence, Stigmergy, UnManned Art, Symbiotic Art, Swarm Paintings, Robot Paintings, Non-Human Art, Painting Emergence and Cooperation, Art and Complexity, ArtBots: The Robot Talent Show.


title: The vertex-transitive TLF-planar graphs

abstract: We consider the class of the topologically locally finite (in short TLF) planar vertex-transitive graphs, a class containing in particular all the one-ended planar Cayley graphs and the normal transitive tilings. We characterize these graphs with a finite local representation and a special kind of finite state automaton named labeling scheme. As a result, we are able to enumerate and describe all TLF-planar vertex-transitive graphs of any given degree. Also, we are able decide to whether any TLF-planar transitive graph is Cayley or not.


title: The MC2 Project [Machines of Collective Conscience]: A possible walk, up to Life-like Complexity and Behaviour, from bottom, basic and simple bio-inspired heuristics - a walk, up into the morphogenesis of information

abstract: Synergy (from the Greek word synergos), broadly defined, refers to combined or co-operative effects produced by two or more elements (parts or individuals). The definition is often associated with the holistic conviction quote that "the whole is greater than the sum of its parts" (Aristotle, in Metaphysics), or the whole cannot exceed the sum of the energies invested in each of its parts (e.g. first law of thermodynamics) even if it is more accurate to say that the functional effects produced by wholes are different from what the parts can produce alone. Synergy is a ubiquitous phenomena in nature and human societies alike. One well know example is provided by the emergence of self-organization in social insects, via direct or indirect interactions. The latter types are more subtle and defined as stigmergy to explain task coordination and regulation in the context of nest reconstruction in termites. An example, could be provided by two individuals, who interact indirectly when one of them modifies the environment and the other responds to the new environment at a later time. In other words, stigmergy could be defined as a particular case of environmental or spatial synergy. The system is purely holistic, and their properties are intrinsically emergent and autocatalytic. On the present work we present a "machine" where there is no precommitment to any particular representational scheme: the desired behaviour is distributed and roughly specified simultaneously among many parts, but there is minimal specification of the mechanism required to generate that behaviour, i.e. the global behaviour evolves from the many relations of multiple simple behaviours.


title: The Biological Concept of Neoteny in Evolutionary Colour Image Segmentation - Simple Experiments in Simple Non-Memetic Genetic Algorithms

abstract: Neoteny, also spelled Paedomorphosis, can be defined in biological terms as the retention by an organism of juvenile or even larval traits into later life. In some species, all morphological development is retarded; the organism is juvenilized but sexually mature. Such shifts of reproductive capability would appear to have adaptive significance to organisms that exhibit it. In terms of evolutionary theory, the process of paedomorphosis suggests that larval stages and developmental phases of existing organisms may give rise, under certain circumstances, to wholly new organisms. Although the present work does not pretend to model or simulate the biological details of such a concept in any way, these ideas were incorporated by a rather simple abstract computational strategy, in order to allow (if possible) for faster convergence into simple non-memetic Genetic Algorithms, i.e. without using local improvement procedures (e.g. via Baldwin or Lamarckian learning). As a case-study, the Genetic Algorithm was used for colour image segmentation purposes by using K-mean unsupervised clustering methods, namely for guiding the evolutionary algorithm in his search for finding the optimal or sub-optimal data partition. Average results suggest that the use of neotonic strategies by employing juvenile genotypes into the later generations and the use of linear-dynamic mutation rates instead of constant, can increase fitness values by 58% comparing to classical Genetic Algorithms, independently from the starting population characteristics on the search space. KEYWORDS: Genetic Algorithms, Artificial Neoteny, Dynamic Mutation Rates, Faster Convergence, Colour Image Segmentation, Classification, Clustering.


title: Artificial Neoteny in Evolutionary Image Segmentation


title: Line and Word Matching in Old Documents

abstract: This paper is concerned with the problem of establishing an index based on word matching. It is assumed that the book was digitised as better as possible and some pre-processing techniques were already applied as line orientation correction and some noise removal. However two main factor are responsible for being not possible to apply ordinary optical character recognition techniques (OCR): the presence of antique fonts and the degraded state of many characters due to unrecoverable original time degradation. In this paper we make a short introduction to word segmentation that involves finding the lines that characterise a word. After we discuss different approaches for word matching and how they can be combined to obtain an ordered list for candidate words for the matching. This discussion will be illustrated by examples.


title: Map Segmentation by Colour Cube Genetic K-Mean Clustering

abstract: Segmentation of a colour image composed of different kinds of texture regions can be a hard problem, namely to compute for an exact texture fields and a decision of the optimum number of segmentation areas in an image when it contains similar and/or unstationary texture fields. In this work, a method is described for evolving adaptive procedures for these problems. In many real world applications data clustering constitutes a fundamental issue whenever behavioural or feature domains can be mapped into topological domains. We formulate the segmentation problem upon such images as an optimisation problem and adopt evolutionary strategy of Genetic Algorithms for the clustering of small regions in colour feature space. The present approach uses k-Means unsupervised clustering methods into Genetic Algorithms, namely for guiding this last Evolutionary Algorithm in his search for finding the optimal or sub-optimal data partition, task that as we know, requires a non-trivial search because of its NP-complete nature. To solve this task, the appropriate genetic coding is also discussed, since this is a key aspect in the implementation. Our purpose is to demonstrate the efficiency of Genetic Algorithms to automatic and unsupervised texture segmentation. Some examples in Colour Maps are presented and overall results discussed. KEYWORDS: Genetic Algorithms, Artificial Neoteny, Dynamic Mutation Rates, Faster Convergence, Colour Image Segmentation, Classification, Clustering.


title: A class of one-dimensional MDS convolutional codes

abstract: A class of one-dimensional convolutional codes will be presented. They are all MDS codes, i. e., have the largest distance among all one-dimensional codes of the same length n and overall constraint length delta. Furthermore, their extended row distances are computed, and they increase with slope n-delta. In certain cases of the algebraic parameters, we will also derive parity check matrices of Vandermonde type for these codes. Finally, cyclicity in the convolutional sense will be discussed for our class of codes. It will turn out that they are cyclic if and only if the field element used in the generator matrix has order n. This can be regarded as a generalization of the block code case.


title: Artificial Ant Colonies in Digital Image Habitats - A Mass Behaviour Effect Study on Pattern Recognition

abstract: Some recent studies have pointed that, the self-organization of neurons into brain-like structures, and the self-organization of ants into a swarm are similar in many respects. If possible to implement, these features could lead to important developments in pattern recognition systems, where perceptive capabilities can emerge and evolve from the interaction of many simple local rules. The principle of the method is inspired by the work of Chialvo and Millonas who developed the first numerical simulation in which swarm cognitive map formation could be explained. From this point, an extended model is presented in order to deal with digital image habitats, in which artificial ants could be able to react to the environment and perceive it. Evolution of pheromone fields point that artificial ant colonies could react and adapt appropriately to any type of digital habitat. KEYWORDS: Swarm Intelligence, Self-Organization, Stigmergy, Artificial Ant Systems, Pattern Recognition and Perception, Image Segmentation, Gestalt Perception Theory, Distributed Computation.


title: Image Colour Segmentation by Genetic Algorithms

abstract: Segmentation of a colour image composed of different kinds of texture regions can be a hard problem, namely to compute for an exact texture fields and a decision of the optimum number of segmentation areas in an image when it contains similar and/or unstationary texture fields. In this work, a method is described for evolving adaptive procedures for these problems. In many real world applications data clustering constitutes a fundamental issue whenever behavioural or feature domains can be mapped into topological domains. We formulate the segmentation problem upon such images as an optimisation problem and adopt evolutionary strategy of Genetic Algorithms for the clustering of small regions in colour feature space. The present approach uses k-Means unsupervised clustering methods into Genetic Algorithms, namely for guiding this last Evolutionary Algorithm in his search for finding the optimal or sub-optimal data partition, task that as we know, requires a non-trivial search because of its intrinsic NP-complete nature. To solve this task, the appropriate genetic coding is also discussed, since this is a key aspect in the implementation. Our purpose is to demonstrate the efficiency of Genetic Algorithms to automatic and unsupervised texture segmentation. Some examples in Colour Maps, Ornamental Stones and in Human Skin Mark segmentation are presented and overall results discussed. KEYWORDS: Genetic Algorithms, Colour Image Segmentation, Classification, Clustering.


title: On Image Filtering, Noise and Morphological Size Intensity Diagrams

abstract: In the absence of a pure noise-free image it is hard to define what noise is, in any original noisy image, and as a consequence also where it is, and in what amount. In fact, the definition of noise depends largely on our own aim in the whole image analysis process, and (perhaps more important) in our self-perception of noise. For instance, when we perceive noise as disconnected and small it is normal to use MM-ASF filters to treat it. There is two evidences of this. First, in many instances there is no ideal and pure noise-free image to compare our filtering process (nothing but our self-perception of its pure image); second, and related with this first point, MM transformations that we chose are only based on our self - and perhaps - fuzzy notion. The present proposal combines the results of two MM filtering transformations (FT1, FT2) and makes use of some measures and quantitative relations on their Size/Intensity Diagrams to find the most appropriate noise removal process. Results can also be used for finding the most appropriate stop criteria, and the right sequence of MM operators combination on Alternating Sequential Filters (ASF), if these measures are applied, for instance, on a Genetic Algorithm's target function.


title: Evolving Categories: Consistent Framework for Representation of Data and Algorithms

abstract: A concept of "evolving categories" is suggested to build a simple, scalable, mathematically consistent framework for representing in uniform way both data and algorithms. A state machine for executing algorithms becomes clear, rich and powerful semantics, based on category theory, and still allows easy implementation. Moreover, it gives an original insight into the nature and semantics of algorithms.


title: Real Time Models of the Asynchronous Circuits: The Delay Theory

abstract: The chapter from the book introduces the delay theory, whose purpose is the modeling of the asynchronous circuits from digital electrical engineering with ordinary and differential pseudo-boolean equations.


title: The Combination of Paradoxical, Uncertain, and Imprecise Sources of Information based on DSmT and Neutro-Fuzzy Inference

abstract: The management and combination of uncertain, imprecise, fuzzy and even paradoxical or high conflicting sources of information has always been, and still remains today, of primal importance for the development of reliable modern information systems involving artificial reasoning. In this chapter, we present a survey of our recent theory of plausible and paradoxical reasoning, known as Dezert-Smarandache Theory (DSmT) in the literature, developed for dealing with imprecise, uncertain and paradoxical sources of information. We focus our presentation here rather on the foundations of DSmT, and on the two important new rules of combination, than on browsing specific applications of DSmT available in literature. Several simple examples are given throughout the presentation to show the efficiency and the generality of this new approach. The last part of this chapter concerns the presentation of the neutrosophic logic, the neutro-fuzzy inference and its connection with DSmT. Fuzzy logic and neutrosophic logic are useful tools in decision making after fusioning the information using the DSm hybrid rule of combination of masses.


title: Mass Storage Management and the Grid

abstract: The University of Edinburgh has a significant interest in mass storage systems as it is one of the core groups tasked with the roll out of storage software for the UK's particle physics grid, GridPP. We present the results of a development project to provide software interfaces between the SDSC Storage Resource Broker, the EU DataGrid and the Storage Resource Manager. This project was undertaken in association with the eDikt group at the National eScience Centre, the Universities of Bristol and Glasgow, Rutherford Appleton Laboratory and the San Diego Supercomputing Center.