OpenRaiser/Intern-Atlas huggingface dataset:
One-Chip Solution to Intelligent Robot Control: Implementing Hexapod Subsumption Architecture Using a Contemporary Microprocessor
Venue: arXiv cs.RO 2004
Year: 2004

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.
Clustering Techniques for Marbles Classification
Venue: arXiv cs.AI 2004
Year: 2004

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).
The vertex-transitive TLF-planar graphs
Venue: arXiv cs.DM 2004
Year: 2004

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.
Line and Word Matching in Old Documents
Venue: arXiv cs.AI 2004
Year: 2004

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.
Map Segmentation by Colour Cube Genetic K-Mean Clustering
Venue: arXiv cs.AI 2004
Year: 2004

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.
On Image Filtering, Noise and Morphological Size Intensity Diagrams
Venue: arXiv cs.CV 2004
Year: 2004

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.
Quantum Interactive Proofs with Competing Provers
Venue: arXiv cs.CC 2004
Year: 2004

This paper studies quantum refereed games, which are quantum interactive proof systems with two competing provers: one that tries to convince the verifier to accept and the other that tries to convince the verifier to reject. We prove that every language having an ordinary quantum interactive proof system also has a quantum refereed game in which the verifier exchanges just one round of messages with each prover. A key part of our proof is the fact that there exists a single quantum measurement that reliably distinguishes between mixed states chosen arbitrarily from disjoint convex sets having large minimal trace distance from one another. We also show how to reduce the probability of error for some classes of quantum refereed games.
Online Learning of Aggregate Knowledge about Non-linear Preferences Applied to Negotiating Prices and Bundles
Venue: arXiv cs.MA 2004
Year: 2004

In this paper, we consider a form of multi-issue negotiation where a shop negotiates both the contents and the price of bundles of goods with his customers. We present some key insights about, as well as a procedure for, locating mutually beneficial alternatives to the bundle currently under negotiation. The essence of our approach lies in combining aggregate (anonymous) knowledge of customer preferences with current data about the ongoing negotiation process. The developed procedure either works with already obtained aggregate knowledge or, in the absence of such knowledge, learns the relevant information online. We conduct computer experiments with simulated customers that have_nonlinear_ preferences. We show how, for various types of customers, with distinct negotiation heuristics, our procedure (with and without the necessary aggregate knowledge) increases the speed with which deals are reached, as well as the number and the Pareto efficiency of the deals reached compared to a benchmark.
Reductions in Distributed Computing Part I: Consensus and Atomic Commitment Tasks
Venue: arXiv cs.DC 2004
Year: 2004

We introduce several notions of reduction in distributed computing, and investigate reduction properties of two fundamental agreement tasks, namely Consensus and Atomic Commitment. We first propose the notion of reduction "a la Karp'', an analog for distributed computing of the classical Karp reduction. We then define a weaker reduction which is the analog of Cook reduction. These two reductions are called K-reduction and C-reduction, respectively. We also introduce the notion of C*-reduction which has no counterpart in classical (namely, non distributed) systems, and which naturally arises when dealing with symmetric tasks. We establish various reducibility and irreducibility theorems with respect to these three reductions. Our main result is an incomparability statement for Consensus and Atomic Commitment tasks: we show that they are incomparable with respect to the C-reduction, except when the resiliency degree is 1, in which case Atomic Commitment is strictly harder than Consensus. A side consequence of these results is that our notion of C-reduction is strictly weaker than the one of K-reduction, even for unsolvable tasks.
A Qualitative Dynamical Modelling Approach to Capital Accumulation in Unregulated Fisheries
Venue: arXiv cs.AI 2005
Year: 2005

Capital accumulation has been a major issue in fisheries economics over the last two decades, whereby the interaction of the fish and capital stocks were of particular interest. Because bio-economic systems are intrinsically complex, previous efforts in this field have relied on a variety of simplifying assumptions. The model presented here relaxes some of these simplifications. Problems of tractability are surmounted by using the methodology of qualitative differential equations (QDE). The theory of QDEs takes into account that scientific knowledge about particular fisheries is usually limited, and facilitates an analysis of the global dynamics of systems with more than two ordinary differential equations. The model is able to trace the evolution of capital and fish stock in good agreement with observed patterns, and shows that over-capitalization is unavoidable in unregulated fisheries.
Logical Characterizations of Heap Abstractions
Venue: arXiv cs.LO 2005
Year: 2005

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

Cousot and Cousot introduced and studied a general past/future-time specification language, called mu*-calculus, featuring a natural time-symmetric trace-based semantics. The standard state-based semantics of the mu*-calculus is an abstract interpretation of its trace-based semantics, which turns out to be incomplete (i.e., trace-incomplete), even for finite systems. As a consequence, standard state-based model checking of the mu*-calculus is incomplete w.r.t. trace-based model checking. This paper shows that any refinement or abstraction of the domain of sets of states induces a corresponding semantics which is still trace-incomplete for any propositional fragment of the mu*-calculus. This derives from a number of results, one for each incomplete logical/temporal connective of the mu*-calculus, that characterize the structure of models, i.e. transition systems, whose corresponding state-based semantics of the mu*-calculus is trace-complete.
Observability and Decentralized Control of Fuzzy Discrete Event Systems
Venue: arXiv cs.DM 2005
Year: 2005

Fuzzy discrete event systems as a generalization of (crisp) discrete event systems have been introduced in order that it is possible to effectively represent uncertainty, imprecision, and vagueness arising from the dynamic of systems. A fuzzy discrete event system has been modelled by a fuzzy automaton; its behavior is described in terms of the fuzzy language generated by the automaton. In this paper, we are concerned with the supervisory control problem for fuzzy discrete event systems with partial observation. Observability, normality, and co-observability of crisp languages are extended to fuzzy languages. It is shown that the observability, together with controllability, of the desired fuzzy language is a necessary and sufficient condition for the existence of a partially observable fuzzy supervisor. When a decentralized solution is desired, it is proved that there exist local fuzzy supervisors if and only if the fuzzy language to be synthesized is controllable and co-observable. Moreover, the infimal controllable and observable fuzzy superlanguage, and the supremal controllable and normal fuzzy sublanguage are also discussed. Simple examples are provided to illustrate the theoretical development.
Communication-Aware Processor Allocation for Supercomputers
Venue: arXiv cs.DS 2005
Year: 2005

This paper gives processor-allocation algorithms for minimizing the average number of communication hops between the assigned processors for grid architectures, in the presence of occupied cells. The simpler problem of assigning processors on a free grid has been studied by Karp, McKellar, and Wong who show that the solutions have nontrivial structure; they left open the complexity of the problem. The associated clustering problem is as follows: Given n points in Re^d, find k points that minimize their average pairwise L1 distance. We present a natural approximation algorithm and show that it is a 7/4-approximation for 2D grids. For d-dimensional space, the approximation guarantee is 2-(1/2d), which is tight. We also give a polynomial-time approximation scheme (PTAS) for constant dimension d, and report on experimental results.
Fibonacci connection between Huffman codes and Wythoff array
Venue: arXiv cs.DM 2005
Year: 2005

Fibonacci connection between non-decreasing sequences of positive integers producing maximum height Huffman trees and the Wythoff array has been proved.
The state complexity of L^2 and L^k
Venue: arXiv cs.CC 2005
Year: 2005

We show that if M is a DFA with n states over an arbitrary alphabet and L = L(M), then the worst-case state complexity of L^2 is n*2^n - 2^{n-1}. If, however, M is a DFA over a unary alphabet, then the worst-case state complexity of L^k is kn-k+1 for all k >= 2.
An Efficient and Flexible Engine for Computing Fixed Points
Venue: arXiv cs.PL 2005
Year: 2005

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.
Isomorphic Implication
Venue: arXiv cs.CC 2005
Year: 2005

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.
A Survey of Fault-Tolerance and Fault-Recovery Techniques in Parallel Systems
Venue: arXiv cs.DC 2005
Year: 2005

Supercomputing systems today often come in the form of large numbers of commodity systems linked together into a computing cluster. These systems, like any distributed system, can have large numbers of independent hardware components cooperating or collaborating on a computation. Unfortunately, any of this vast number of components can fail at any time, resulting in potentially erroneous output. In order to improve the robustness of supercomputing applications in the presence of failures, many techniques have been developed to provide resilience to these kinds of system faults. This survey provides an overview of these various fault-tolerance techniques.
Portfolio selection using neural networks
Venue: arXiv cs.NE 2005
Year: 2005

In this paper we apply a heuristic method based on artificial neural networks in order to trace out the efficient frontier associated to the portfolio selection problem. We consider a generalization of the standard Markowitz mean-variance model which includes cardinality and bounding constraints. These constraints ensure the investment in a given number of different assets and limit the amount of capital to be invested in each asset. We present some experimental results obtained with the neural network heuristic and we compare them to those obtained with three previous heuristic methods.
A Cryptographic Study of Some Digital Signature Schemes
Venue: arXiv cs.CR 2005
Year: 2005

In this thesis, we propose some directed signature schemes. In addition, we have discussed their applications in different situations. In this thesis, we would like to discuss the security aspects during the design process of the proposed directed digital signature schemes. The security of the most digital signature schemes widely use in practice is based on the two difficult problems, viz; the problem of factoring integers (The RSA scheme) and the problem of finding discrete logarithms over finite fields (The ElGamal scheme). The proposed works in this thesis is divided into seven chapters.
Clustering SPIRES with EqRank
Venue: arXiv cs.DL 2005
Year: 2005

SPIRES is the largest database of scientific papers in the subject field of high energy and nuclear physics. It contains information on the citation graph of more than half a million of papers (vertexes of the citation graph). We outline the EqRank algorithm designed to cluster vertexes of directed graphs, and present the results of EqRank application to the SPIRES citation graph. The hierarchical clustering of SPIRES yielded by EqRank is used to set up a web service, which is also outlined.
On the Sensitivity of Cyclically-Invariant Boolean Functions
Venue: arXiv cs.CC 2005
Year: 2005

In this paper we construct a cyclically invariant Boolean function whose sensitivity is $Θ(n^{1/3})$. This result answers two previously published questions. Turán (1984) asked if any Boolean function, invariant under some transitive group of permutations, has sensitivity $Ω(\sqrt{n})$. Kenyon and Kutin (2004) asked whether for a ``nice'' function the product of 0-sensitivity and 1-sensitivity is $Ω(n)$. Our function answers both questions in the negative. We also prove that for minterm-transitive functions (a natural class of Boolean functions including our example) the sensitivity is $Ω(n^{1/3})$. Hence for this class of functions sensitivity and block sensitivity are polynomially related.
An Empirical Study of MDL Model Selection with Infinite Parametric Complexity
Venue: arXiv cs.LG 2005
Year: 2005

Parametric complexity is a central concept in MDL model selection. In practice it often turns out to be infinite, even for quite simple models such as the Poisson and Geometric families. In such cases, MDL model selection as based on NML and Bayesian inference based on Jeffreys' prior can not be used. Several ways to resolve this problem have been proposed. We conduct experiments to compare and evaluate their behaviour on small sample sizes. We find interestingly poor behaviour for the plug-in predictive code; a restricted NML model performs quite well but it is questionable if the results validate its theoretical motivation. The Bayesian model with the improper Jeffreys' prior is the most dependable.
On Partially Additive Kleene Algebras
Venue: arXiv cs.LO 2005
Year: 2005

We define the notion of a partially additive Kleene algebra, which is a Kleene algebra where the + operation need only be partially defined. These structures formalize a number of examples that cannot be handled directly by Kleene algebras. We relate partially additive Kleene algebras to existing algebraic structures, by exhibiting categorical connections with Kleene algebras, partially additive categories, and closed semirings.
Introduction to linear logic and ludics, part II
Venue: arXiv cs.LO 2005
Year: 2005

This paper is the second part of an introduction to linear logic and ludics, both due to Girard. It is devoted to proof nets, in the limited, yet central, framework of multiplicative linear logic and to ludics, which has been recently developped in an aim of further unveiling the fundamental interactive nature of computation and logic. We hope to offer a few computer science insights into this new theory.