OpenRaiser/Intern-Atlas huggingface dataset:
Image Colour Segmentation by Genetic Algorithms
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 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.
Complexity of Self-Assembled Shapes
Venue: arXiv cs.CC 2004
Year: 2004

The connection between self-assembly and computation suggests that a shape can be considered the output of a self-assembly ``program,'' a set of tiles that fit together to create a shape. It seems plausible that the size of the smallest self-assembly program that builds a shape and the shape's descriptional (Kolmogorov) complexity should be related. We show that when using a notion of a shape that is independent of scale, this is indeed so: in the Tile Assembly Model, the minimal number of distinct tile types necessary to self-assemble a shape, at some scale, can be bounded both above and below in terms of the shape's Kolmogorov complexity. As part of the proof of the main result, we sketch a general method for converting a program outputting a shape as a list of locations into a set of tile types that self-assembles into a scaled up version of that shape. Our result implies, somewhat counter-intuitively, that self-assembly of a scaled-up version of a shape often requires fewer tile types. Furthermore, the independence of scale in self-assembly theory appears to play the same crucial role as the independence of running time in the theory of computability. This leads to an elegant formulation of languages of shapes generated by self-assembly. Considering functions from integers to shapes, we show that the running-time complexity, with respect to Turing machines, is polynomially equivalent to the scale complexity of the same function implemented via self-assembly by a finite set of tile types. Our results also hold for shapes defined by Wang tiling -- where there is no sense of a self-assembly process -- except that here time complexity must be measured with respect to non-deterministic Turing machines.
Q-valued neural network as a system of fast identification and pattern recognition
Venue: arXiv cs.NE 2004
Year: 2004

An effective neural network algorithm of the perceptron type is proposed. The algorithm allows us to identify strongly distorted input vector reliably. It is shown that its reliability and processing speed are orders of magnitude higher than that of full connected neural networks. The processing speed of our algorithm exceeds the one of the stack fast-access retrieval algorithm that is modified for working when there are noises in the input channel.
Source Coding With Encoder Side Information
Venue: arXiv cs.IT 2004
Year: 2004

We introduce the idea of distortion side information, which does not directly depend on the source but instead affects the distortion measure. We show that such distortion side information is not only useful at the encoder, but that under certain conditions, knowing it at only the encoder is as good as knowing it at both encoder and decoder, and knowing it at only the decoder is useless. Thus distortion side information is a natural complement to the signal side information studied by Wyner and Ziv, which depends on the source but does not involve the distortion measure. Furthermore, when both types of side information are present, we characterize the penalty for deviating from the configuration of encoder-only distortion side information and decoder-only signal side information, which in many cases is as good as full side information knowledge.
Reductions in Distributed Computing Part II: k-Threshold Agreement Tasks
Venue: arXiv cs.DC 2004
Year: 2004

We extend the results of Part I by considering a new class of agreement tasks, the so-called k-Threshold Agreement tasks (previously introduced by Charron-Bost and Le Fessant). These tasks naturally interpolate between Atomic Commitment and Consensus. Moreover, they constitute a valuable tool to derive irreducibility results between Consensus tasks only. In particular, they allow us to show that (A) for a fixed set of processes, the higher the resiliency degree is, the harder the Consensus task is, and (B) for a fixed resiliency degree, the smaller the set of processes is, the harder the Consensus task is. The proofs of these results lead us to consider new oracle-based reductions, involving a weaker variant of the C-reduction introduced in Part I. We also discuss the relationship between our results and previous ones relating f-resiliency and wait-freedom.
Set Unification
Venue: arXiv cs.LO 2005
Year: 2005

The unification problem in algebras capable of describing sets has been tackled, directly or indirectly, by many researchers and it finds important applications in various research areas--e.g., deductive databases, theorem proving, static analysis, rapid software prototyping. The various solutions proposed are spread across a large literature. In this paper we provide a uniform presentation of unification of sets, formalizing it at the level of set theory. We address the problem of deciding existence of solutions at an abstract level. This provides also the ability to classify different types of set unification problems. Unification algorithms are uniformly proposed to solve the unification problem in each of such classes. The algorithms presented are partly drawn from the literature--and properly revisited and analyzed--and partly novel proposals. In particular, we present a new goal-driven algorithm for general ACI1 unification and a new simpler algorithm for general (Ab)(Cl) unification.
Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP
Venue: arXiv cs.CC 2005
Year: 2005

For both the edge deletion heuristic and the maximum-degree greedy heuristic, we study the problem of recognizing those graphs for which that heuristic can approximate the size of a minimum vertex cover within a constant factor of r, where r is a fixed rational number. Our main results are that these problems are complete for the class of problems solvable via parallel access to NP. To achieve these main results, we also show that the restriction of the vertex cover problem to those graphs for which either of these heuristics can find an optimal solution remains NP-hard.
Domain-Dependent Knowledge in Answer Set Planning
Venue: arXiv cs.AI 2005
Year: 2005

In this paper we consider three different kinds of domain-dependent control knowledge (temporal, procedural and HTN-based) that are useful in planning. Our approach is declarative and relies on the language of logic programming with answer set semantics (AnsProlog*). AnsProlog* is designed to plan without control knowledge. We show how temporal, procedural and HTN-based control knowledge can be incorporated into AnsProlog* by the modular addition of a small number of domain-dependent rules, without the need to modify the planner. We formally prove the correctness of our planner, both in the absence and presence of the control knowledge. Finally, we perform some initial experimentation that demonstrates the potential reduction in planning time that can be achieved when procedural domain knowledge is used to solve planning problems with large plan length.
Causes and Explanations: A Structural-Model Approach. Part II: Explanations
Venue: arXiv cs.AI 2005
Year: 2005

We propose new definitions of (causal) explanation, using structural equations to model counterfactuals. The definition is based on the notion of actual cause, as defined and motivated in a companion paper. Essentially, an explanation is a fact that is not known for certain but, if found to be true, would constitute an actual cause of the fact to be explained, regardless of the agent's initial uncertainty. We show that the definition handles well a number of problematic examples from the literature.
Feedforward Neural Networks with Diffused Nonlinear Weight Functions
Venue: arXiv cs.NE 2005
Year: 2005

In this paper, feedforward neural networks are presented that have nonlinear weight functions based on look--up tables, that are specially smoothed in a regularization called the diffusion. The idea of such a type of networks is based on the hypothesis that the greater number of adaptive parameters per a weight function might reduce the total number of the weight functions needed to solve a given problem. Then, if the computational complexity of a propagation through a single such a weight function would be kept low, then the introduced neural networks might possibly be relatively fast. A number of tests is performed, showing that the presented neural networks may indeed perform better in some cases than the classic neural networks and a number of other learning machines.
Optimal Free-Space Management and Routing-Conscious Dynamic Placement for Reconfigurable Devices
Venue: arXiv cs.DS 2005
Year: 2005

We describe algorithmic results for two crucial aspects of allocating resources on computational hardware devices with partial reconfigurability. By using methods from the field of computational geometry, we derive a method that allows correct maintainance of free and occupied space of a set of n rectangular modules in optimal time Theta(n log n); previous approaches needed a time of O(n^2) for correct results and O(n) for heuristic results. We also show that finding an optimal feasible communication-conscious placement (which minimizes the total weighted Manhattan distance between the new module and existing demand points) can be computed in Theta(n log n). Both resulting algorithms are practically easy to implement and show convincing experimental behavior.
Distance distribution of binary codes and the error probability of decoding
Venue: arXiv cs.IT 2005
Year: 2005

We address the problem of bounding below the probability of error under maximum likelihood decoding of a binary code with a known distance distribution used on a binary symmetric channel. An improved upper bound is given for the maximum attainable exponent of this probability (the reliability function of the channel). In particular, we prove that the ``random coding exponent'' is the true value of the channel reliability for code rate $R$ in some interval immediately below the critical rate of the channel. An analogous result is obtained for the Gaussian channel.
Resource Bounded Immunity and Simplicity
Venue: arXiv cs.CC 2005
Year: 2005

Revisiting the thirty years-old notions of resource-bounded immunity and simplicity, we investigate the structural characteristics of various immunity notions: strong immunity, almost immunity, and hyperimmunity as well as their corresponding simplicity notions. We also study limited immunity and simplicity, called k-immunity and feasible k-immunity, and their simplicity notions. Finally, we propose the k-immune hypothesis as a working hypothesis that guarantees the existence of simple sets in NP.
A New Look at Survey Propagation and its Generalizations
Venue: arXiv cs.CC 2005
Year: 2005

This paper provides a new conceptual perspective on survey propagation, which is an iterative algorithm recently introduced by the statistical physics community that is very effective in solving random k-SAT problems even with densities close to the satisfiability threshold. We first describe how any SAT formula can be associated with a novel family of Markov random fields (MRFs), parameterized by a real number ρ\in [0,1]. We then show that applying belief propagation--a well-known ``message-passing'' technique for estimating marginal probabilities--to this family of MRFs recovers a known family of algorithms, ranging from pure survey propagation at one extreme (ρ= 1) to standard belief propagation on the uniform distribution over SAT assignments at the other extreme (ρ= 0). Configurations in these MRFs have a natural interpretation as partial satisfiability assignments, on which a partial order can be defined. We isolate cores as minimal elements in this partial ordering, which are also fixed points of survey propagation and the only assignments with positive probability in the MRF for ρ=1. Our experimental results for k=3 suggest that solutions of random formulas typically do not possess non-trivial cores. This makes it necessary to study the structure of the space of partial assignments for ρ<1 and investigate the role of assignments that are very close to being cores. To that end, we investigate the associated lattice structure, and prove a weight-preserving identity that shows how any MRF with ρ>0 can be viewed as a ``smoothed'' version of the uniform distribution over satisfying assignments (ρ=0). Finally, we isolate properties of Gibbs sampling and message-passing algorithms that are typical for an ensemble of k-SAT problems.
Outflanking and securely using the PIN/TAN-System
Venue: arXiv cs.CR 2005
Year: 2005

The PIN/TAN-system is an authentication and authorization scheme used in e-business. Like other similar schemes it is successfully attacked by criminals. After shortly classifying the various kinds of attacks we accomplish malicious code attacks on real World Wide Web transaction systems. In doing so we find that it is really easy to outflank these systems. This is even supported by the users' behavior. We give a few simple behavior rules to improve this situation. But their impact is limited. Also the providers support the attacks by having implementation flaws in their installations. Finally we show that the PIN/TAN-system is not suitable for usage in highly secure applications.
Self-Organised Factorial Encoding of a Toroidal Manifold
Venue: arXiv cs.LG 2005
Year: 2005

It is shown analytically how a neural network can be used optimally to encode input data that is derived from a toroidal manifold. The case of a 2-layer network is considered, where the output is assumed to be a set of discrete neural firing events. The network objective function measures the average Euclidean error that occurs when the network attempts to reconstruct its input from its output. This optimisation problem is solved analytically for a toroidal input manifold, and two types of solution are obtained: a joint encoder in which the network acts as a soft vector quantiser, and a factorial encoder in which the network acts as a pair of soft vector quantisers (one for each of the circular subspaces of the torus). The factorial encoder is favoured for small network sizes when the number of observed firing events is large. Such self-organised factorial encoding may be used to restrict the size of network that is required to perform a given encoding task, and will decompose an input manifold into its constituent submanifolds.
An Evaluated Certification Services System for the German National Root CA - Legally Binding and Trustworthy Transactions in E-Business and E-Government
Venue: arXiv cs.CR 2005
Year: 2005

National Root CAs enable legally binding E-Business and E-Government transactions. This is a report about the development, the evaluation and the certification of the new certification services system for the German National Root CA. We illustrate why a new certification services system was necessary, and which requirements to the new system existed. Then we derive the tasks to be done from the mentioned requirements. After that we introduce the initial situation at the beginning of the project. We report about the very process and talk about some unfamiliar situations, special approaches and remarkable experiences. Finally we present the ready IT system and its impact to E-Business and E-Government.
Planning for Directory Services in Public Key Infrastructures
Venue: arXiv cs.CR 2005
Year: 2005

In this paper we provide a guide for public key infrastructure designers and administrators when planning for directory services. We concentrate on the LDAP directories and how they can be used to successfully publish PKI information. We analyse their available mechanisms and propose a best practice guide for use in PKI. We then take a look into the German Signature Act and Ordinance and discuss their part as far as directories concerning. Finally, we translate those to the LDAP directories practices.
A Tutorial on the Expectation-Maximization Algorithm Including Maximum-Likelihood Estimation and EM Training of Probabilistic Context-Free Grammars
Venue: arXiv cs.CL 2005
Year: 2005

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.
Monotonicity Results for Coherent MIMO Rician Channels
Venue: arXiv cs.IT 2005
Year: 2005

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.
Advances towards a General-Purpose Societal-Scale Human-Collective Problem-Solving Engine
Venue: arXiv cs.CY 2005
Year: 2005

Human collective intelligence has proved itself as an important factor in a society's ability to accomplish large-scale behavioral feats. As societies have grown in population-size, individuals have seen a decrease in their ability to activeily participate in the problem-solving processes of the group. Representative decision-making structures have been used as a modern solution to society's inadequate information-processing infrastructure. With computer and network technologies being further embedded within the fabric of society, the implementation of a general-purpose societal-scale human-collective problem-solving engine is envisioned as a means of furthering the collective-intelligence potential of society. This paper provides both a novel framework for creating collective intelligence systems and a method for implementing a representative and expertise system based on social-network theory.
Playful, streamlike computation
Venue: arXiv cs.LO 2005
Year: 2005

We offer a short tour into the interactive interpretation of sequential programs. We emphasize streamlike computation -- that is, computation of successive bits of information upon request. The core of the approach surveyed here dates back to the work of Berry and the author on sequential algorithms on concrete data structures in the late seventies, culminating in the design of the programming language CDS, in which the semantics of programs of any type can be explored interactively. Around one decade later, two major insights of Cartwright and Felleisen on one hand, and of Lamarche on the other hand gave new, decisive impulses to the study of sequentiality. Cartwright and Felleisen observed that sequential algorithms give a direct semantics to control operators like call-cc\" and proposed to include explicit errors both in the syntax and in the semantics of the language PCF. Lamarche (unpublished) connected sequential algorithms to linear logic and games. The successful program of games semantics has spanned over the nineties until now, starting with syntax-independent characterizations of the term model of PCF by Abramsky, Jagadeesan, and Malacaria on one hand, and by Hyland and Ong on the other hand.
Split-2 Bisimilarity has a Finite Axiomatization over CCS with<br> Hennessy's Merge
Venue: arXiv cs.LO 2005
Year: 2005

This note shows that split-2 bisimulation equivalence (also known as timed equivalence) affords a finite equational axiomatization over the process algebra obtained by adding an auxiliary operation proposed by Hennessy in 1981 to the recursion, relabelling and restriction free fragment of Milner's Calculus of Communicating Systems. Thus the addition of a single binary operation, viz. Hennessy's merge, is sufficient for the finite equational axiomatization of parallel composition modulo this non-interleaving equivalence. This result is in sharp contrast to a theorem previously obtained by the same authors to the effect that the same language is not finitely based modulo bisimulation equivalence.
Maintaining Consistency of Data on the Web
Venue: arXiv cs.DB 2005
Year: 2005

Increasingly more data is becoming available on the Web, estimates speaking of 1 billion documents in 2002. Most of the documents are Web pages whose data is considered to be in XML format, expecting it to eventually replace HTML. A common problem in designing and maintaining a Web site is that data on a Web page often replicates or derives from other data, the so-called base data, that is usually not contained in the deriving or replicating page. Consequently, replicas and derivations become inconsistent upon modifying base data in a Web page or a relational database. For example, after assigning a thesis to a student and modifying the Web page that describes it in detail, the thesis is still incorrectly contained in the list of offered thesis, missing in the list of ongoing thesis, and missing in the advisor's teaching record. The thesis presents a solution by proposing a combined approach that provides for maintaining consistency of data in Web pages that (i) replicate data in relational databases, or (ii) replicate or derive from data in Web pages. Upon modifying base data, the modification is immediately pushed to affected Web pages. There, maintenance is performed incrementally by only modifying the affected part of the page instead of re-generating the whole page from scratch.
Augmented Segmentation and Visualization for Presentation Videos
Venue: arXiv cs.MM 2005
Year: 2005

We investigate methods of segmenting, visualizing, and indexing presentation videos by separately considering audio and visual data. The audio track is segmented by speaker, and augmented with key phrases which are extracted using an Automatic Speech Recognizer (ASR). The video track is segmented by visual dissimilarities and augmented by representative key frames. An interactive user interface combines a visual representation of audio, video, text, and key frames, and allows the user to navigate a presentation video. We also explore clustering and labeling of speaker data and present preliminary results.