title: A Tree Search Method for Iterative Decoding of Underdetermined Multiuser Systems

abstract: Application of the turbo principle to multiuser decoding results in an exchange of probability distributions between two sets of constraints. Firstly, constraints imposed by the multiple-access channel, and secondly, individual constraints imposed by each users' error control code. A-posteriori probability computation for the first set of constraints is prohibitively complex for all but a small number of users. Several lower complexity approaches have been proposed in the literature. One class of methods is based on linear filtering (e.g. LMMSE). A more recent approach is to compute approximations to the posterior probabilities by marginalising over a subset of sequences (list detection). Most of the list detection methods are restricted to non-singular systems. In this paper, we introduce a transformation that permits application of standard tree-search methods to underdetermined systems. We find that the resulting tree-search based receiver outperforms existing methods.


title: A Group-Theoretic Approach to the WSSUS Pulse Design Problem

abstract: We consider the pulse design problem in multicarrier transmission where the pulse shapes are adapted to the second order statistics of the WSSUS channel. Even though the problem has been addressed by many authors analytical insights are rather limited. First we show that the problem is equivalent to the pure state channel fidelity in quantum information theory. Next we present a new approach where the original optimization functional is related to an eigenvalue problem for a pseudo differential operator by utilizing unitary representations of the Weyl--Heisenberg group.A local approximation of the operator for underspread channels is derived which implicitly covers the concepts of pulse scaling and optimal phase space displacement. The problem is reformulated as a differential equation and the optimal pulses occur as eigenstates of the harmonic oscillator Hamiltonian. Furthermore this operator--algebraic approach is extended to provide exact solutions for different classes of scattering environments.


title: Orchestrating Metadata Enhancement Services: Introducing Lenny

abstract: Harvested metadata often suffers from uneven quality to the point that utility is compromised. Although some aggregators have developed methods for evaluating and repairing specific metadata problems, it has been unclear how these methods might be scaled into services that can be used within an automated production environment. The National Science Digital Library (NSDL), as part of its work with INFOMINE, has developed a model of ser-vice interaction that enables loosely-coupled third party services to provide metadata enhancements to a central repository, with interactions orchestrated by a centralized software application.


title: Towards Automated Integration of Guess and Check Programs in Answer Set Programming: A Meta-Interpreter and Applications

abstract: Answer set programming (ASP) with disjunction offers a powerful tool for declaratively representing and solving hard problems. Many NP-complete problems can be encoded in the answer set semantics of logic programs in a very concise and intuitive way, where the encoding reflects the typical "guess and check" nature of NP problems: The property is encoded in a way such that polynomial size certificates for it correspond to stable models of a program. However, the problem-solving capacity of full disjunctive logic programs (DLPs) is beyond NP, and captures a class of problems at the second level of the polynomial hierarchy. While these problems also have a clear "guess and check" structure, finding an encoding in a DLP reflecting this structure may sometimes be a non-obvious task, in particular if the "check" itself is a coNP-complete problem; usually, such problems are solved by interleaving separate guess and check programs, where the check is expressed by inconsistency of the check program. In this paper, we present general transformations of head-cycle free (extended) disjunctive logic programs into stratified and positive (extended) disjunctive logic programs based on meta-interpretation techniques. The answer sets of the original and the transformed program are in simple correspondence, and, moreover, inconsistency of the original program is indicated by a designated answer set of the transformed program. Our transformations facilitate the integration of separate "guess" and "check" programs, which are often easy to obtain, automatically into a single disjunctive logic program. Our results complement recent results on meta-interpretation in ASP, and extend methods and techniques for a declarative "guess and check" problem solving paradigm through ASP.


title: Space Frequency Codes from Spherical Codes

abstract: A new design method for high rate, fully diverse ('spherical') space frequency codes for MIMO-OFDM systems is proposed, which works for arbitrary numbers of antennas and subcarriers. The construction exploits a differential geometric connection between spherical codes and space time codes. The former are well studied e.g. in the context of optimal sequence design in CDMA systems, while the latter serve as basic building blocks for space frequency codes. In addition a decoding algorithm with moderate complexity is presented. This is achieved by a lattice based construction of spherical codes, which permits lattice decoding algorithms and thus offers a substantial reduction of complexity.


title: Clever Search: A WordNet Based Wrapper for Internet Search Engines

abstract: This paper presents an approach to enhance search engines with information about word senses available in WordNet. The approach exploits information about the conceptual relations within the lexical-semantic net. In the wrapper for search engines presented, WordNet information is used to specify user's request or to classify the results of a publicly available web search engine, like google, yahoo, etc.


title: Faults and Improvements of an Enhanced Remote User Authentication Scheme Using Smart Cards

abstract: In 2000, Hwang and Li proposed a remote user authentication scheme using smart cards to solve the problems of Lamport scheme. Later, Chan- Chang, Shen- Lin- Hwang and then Chang-Hwang pointed out some attacks on Hwang – Li’s scheme. In 2003, Shen, Lin and Hwang also proposed a modified scheme to remove these attacks. In the same year, Leung-Cheng-Fong-Chan showed that modified scheme proposed by Shen-Lin-Hwang is still insecure. In 2004, Awasthi and Lal enhanced Shen-Lin-Hwang’s scheme to overcome its security pitfalls. This paper analyses that the user U/smart card does not provide complete information for the execution and proper running of the login phase of the Awasthi- Lal’s scheme. Furthermore, this paper also modifies the Awasthi- Lal’s scheme for the proper functioning.


title: Information estimations and analysis of structures

abstract: In this paper have written the results of the information analysis of structures. The obtained information estimation (IE) are based on an entropy measure of C. Shannon. Obtained IE is univalent both for the non-isomorphic and for the isomorphic graphs, algorithmically, it is asymptotically steady and has vector character. IE can be used for the solution of the problems ranking of structures by the preference, the evaluation of the structurization of subject area, the solution of the problems of structural optimization. Information estimations and method of the information analysis of structures it can be used in many fields of knowledge (Electrical Systems and Circuit, Image recognition, Computer technology, Databases and Bases of knowledge, Organic chemistry, Biology and others) and it can be base for the structure calculus.


title: Issues in Exploiting GermaNet as a Resource in Real Applications

abstract: This paper reports about experiments with GermaNet as a resource within domain specific document analysis. The main question to be answered is: How is the coverage of GermaNet in a specific domain? We report about results of a field test of GermaNet for analyses of autopsy protocols and present a sketch about the integration of GermaNet inside XDOC. Our remarks will contribute to a GermaNet user's wish list.


title: Stochastic Iterative Decoders

abstract: This paper presents a stochastic algorithm for iterative error control decoding. We show that the stochastic decoding algorithm is an approximation of the sum-product algorithm. When the code's factor graph is a tree, as with trellises, the algorithm approaches maximum a-posteriori decoding. We also demonstrate a stochastic approximations to the alternative update rule known as successive relaxation. Stochastic decoders have very simple digital implementations which have almost no RAM requirements. We present example stochastic decoders for a trellis-based Hamming code, and for a Block Turbo code constructed from Hamming codes.


title: A complexity-regularized quantization approach to nonlinear dimensionality reduction

abstract: We consider the problem of nonlinear dimensionality reduction: given a training set of high-dimensional data whose ``intrinsic'' low dimension is assumed known, find a feature extraction map to low-dimensional space, a reconstruction map back to high-dimensional space, and a geometric description of the dimension-reduced data as a smooth manifold. We introduce a complexity-regularized quantization approach for fitting a Gaussian mixture model to the training set via a Lloyd algorithm. Complexity regularization controls the trade-off between adaptation to the local shape of the underlying manifold and global geometric consistency. The resulting mixture model is used to design the feature extraction and reconstruction maps and to define a Riemannian metric on the low-dimensional data. We also sketch a proof of consistency of our scheme for the purposes of estimating the unknown underlying pdf of high-dimensional data.


title: Multi-Vehicle Cooperative Control Using Mixed Integer Linear Programming

abstract: We present methods to synthesize cooperative strategies for multi-vehicle control problems using mixed integer linear programming. Complex multi-vehicle control problems are expressed as mixed logical dynamical systems. Optimal strategies for these systems are then solved for using mixed integer linear programming. We motivate the methods on problems derived from an adversarial game between two teams of robots called RoboFlag. We assume the strategy for one team is fixed and governed by state machines. The strategy for the other team is generated using our methods. Finally, we perform an average case computational complexity study on our approach.


title: Transforming Business Rules Into Natural Language Text

abstract: The aim of the project presented in this paper is to design a system for an NLG architecture, which supports the documentation process of eBusiness models. A major task is to enrich the formal description of an eBusiness model with additional information needed in an NLG task.


title: Corpus based Enrichment of GermaNet Verb Frames

abstract: Lexical semantic resources, like WordNet, are often used in real applications of natural language document processing. For example, we integrated GermaNet in our document suite XDOC of processing of German forensic autopsy protocols. In addition to the hypernymy and synonymy relation, we want to adapt GermaNet's verb frames for our analysis. In this paper we outline an approach for the domain related enrichment of GermaNet verb frames by corpus based syntactic and co-occurred data analyses of real documents.


title: Context Related Derivation of Word Senses

abstract: Real applications of natural language document processing are very often confronted with domain specific lexical gaps during the analysis of documents of a new domain. This paper describes an approach for the derivation of domain specific concepts for the extension of an existing ontology. As resources we need an initial ontology and a partially processed corpus of a domain. We exploit the specific characteristic of the sublanguage in the corpus. Our approach is based on syntactical structures (noun phrases) and compound analyses to extract information required for the extension of GermaNet's lexical resources.


title: Transforming and Enriching Documents for the Semantic Web

abstract: We suggest to employ techniques from Natural Language Processing (NLP) and Knowledge Representation (KR) to transform existing documents into documents amenable for the Semantic Web. Semantic Web documents have at least part of their semantics and pragmatics marked up explicitly in both a machine processable as well as human readable manner. XML and its related standards (XSLT, RDF, Topic Maps etc.) are the unifying platform for the tools and methodologies developed for different application scenarios.


title: Some Extensions of Gallager's Method to General Sources and Channels

abstract: The Gallager bound is well known in the area of channel coding. However, most discussions about it mainly focus on its applications to memoryless channels. We show in this paper that the bounds obtained by Gallager's method are very tight even for general sources and channels that are defined in the information-spectrum theory. Our method is mainly based on the estimations of error exponents in those bounds, and by these estimations we proved the direct part of the Slepian-Wolf theorem and channel coding theorem for general sources and channels.


title: Directed Threshold Multi – Signature Scheme without SDC

abstract: In this paper, we propose a Directed threshold multisignature scheme without SDC. This signature scheme is applicable when the message is sensitive to the signature receiver; and the signatures are generated by the cooperation of a number of people from a given group of senders. In this scheme, any malicious set of signers cannot impersonate any other set of signers to forge the signatures. In case of forgery, it is possible to trace the signing set.


title: Shawn: A new approach to simulating wireless sensor networks

abstract: We consider the simulation of wireless sensor networks (WSN) using a new approach. We present Shawn, an open-source discrete-event simulator that has considerable differences to all other existing simulators. Shawn is very powerful in simulating large scale networks with an abstract point of view. It is, to the best of our knowledge, the first simulator to support generic high-level algorithms as well as distributed protocols on exactly the same underlying networks.


title: Asymptotic Log-loss of Prequential Maximum Likelihood Codes

abstract: We analyze the Dawid-Rissanen prequential maximum likelihood codes relative to one-parameter exponential family models M. If data are i.i.d. according to an (essentially) arbitrary P, then the redundancy grows at rate c/2 ln n. We show that c=v1/v2, where v1 is the variance of P, and v2 is the variance of the distribution m* in M that is closest to P in KL divergence. This shows that prequential codes behave quite differently from other important universal codes such as the 2-part MDL, Shtarkov and Bayes codes, for which c=1. This behavior is undesirable in an MDL model selection setting.


title: Model-Checking Problems as a Basis for Parameterized Intractability

abstract: Most parameterized complexity classes are defined in terms of a parameterized version of the Boolean satisfiability problem (the so-called weighted satisfiability problem). For example, Downey and Fellow's W-hierarchy is of this form. But there are also classes, for example, the A-hierarchy, that are more naturally characterised in terms of model-checking problems for certain fragments of first-order logic. Downey, Fellows, and Regan were the first to establish a connection between the two formalisms by giving a characterisation of the W-hierarchy in terms of first-order model-checking problems. We improve their result and then prove a similar correspondence between weighted satisfiability and model-checking problems for the A-hierarchy and the W^*-hierarchy. Thus we obtain very uniform characterisations of many of the most important parameterized complexity classes in both formalisms. Our results can be used to give new, simple proofs of some of the core results of structural parameterized complexity theory.


title: Neural network ensembles: Evaluation of aggregation algorithms

abstract: Ensembles of artificial neural networks show improved generalization capabilities that outperform those of single networks. However, for aggregation to be effective, the individual networks must be as accurate and diverse as possible. An important problem is, then, how to tune the aggregate members in order to have an optimal compromise between these two conflicting conditions. We present here an extensive evaluation of several algorithms for ensemble construction, including new proposals and comparing them with standard methods in the literature. We also discuss a potential problem with sequential aggregation algorithms: the non-frequent but damaging selection through their heuristics of particularly bad ensemble members. We introduce modified algorithms that cope with this problem by allowing individual weighting of aggregate members. Our algorithms and their weighted modifications are favorably tested against other methods in the literature, producing a sensible improvement in performance on most of the standard statistical databases used as benchmarks.


title: Identification of complex systems in the basis of wavelets

abstract: In this paper is proposed the method of the identification of complex dynamic systems. Method can be used for the identification of linear and nonlinear complex dynamic systems for the determined or stochastic signals at the inputs and the outputs. It is proposed to use a basis of wavelets for obtaining the impulse transient function (ITF) of system. ITF is considered in the form of surface in the 3D space. Are given the results of experiments on the identification of systems in the basis of wavelets.


title: Scientific Data Management in the Coming Decade

abstract: This is a thought piece on data-intensive science requirements for databases and science centers. It argues that peta-scale datasets will be housed by science centers that provide substantial storage and processing for scientists who access the data via smart notebooks. Next-generation science instruments and simulations will generate these peta-scale datasets. The need to publish and share data and the need for generic analysis and visualization tools will finally create a convergence on common metadata standards. Database systems will be judged by their support of these metadata standards and by their ability to manage and access peta-scale datasets. The procedural stream-of-bytes-file-centric approach to data analysis is both too cumbersome and too serial for such large datasets. Non-procedural query and analysis of schematized self-describing data is both easier to use and allows much more parallelism.


title: Performance Considerations for Gigabyte per Second Transcontinental Disk-to-Disk File Transfers

abstract: Moving data from CERN to Pasadena at a gigabyte per second using the next generation Internet requires good networking and good disk IO. Ten Gbps Ethernet and OC192 links are in place, so now it is simply a matter of programming. This report describes our preliminary work and measurements in configuring the disk subsystem for this effort. Using 24 SATA disks at each endpoint we are able to locally read and write an NTFS volume is striped across 24 disks at 1.2 GBps. A 32-disk stripe delivers 1.7 GBps. Experiments on higher performance and higher-capacity systems deliver up to 3.5 GBps.


title: TerraServer SAN-Cluster Architecture and Operations Experience

abstract: Microsoft TerraServer displays aerial, satellite, and to-pographic images of the earth in a SQL database available via the Internet. It is one of the most popular online at-lases, presenting seventeen terabytes of image data from the United States Geological Survey (USGS). Initially de-ployed in 1998, the system demonstrated the scalability of PC hardware and software - Windows and SQL Server - on a single, mainframe-class processor. In September 2000, the back-end database application was migrated to 4-node active/passive cluster connected to an 18 terabyte Storage Area Network (SAN). The new configuration was designed to achieve 99.99% availability for the back-end application. This paper describes the hardware and software components of the TerraServer Cluster and SAN, and describes our experience in configuring and operating this system for three years. Not surprisingly, the hardware and architecture delivered better than four-9's of availability, but operations mistakes delivered three-9's.


title: Where the Rubber Meets the Sky: Bridging the Gap between Databases and Science

abstract: Scientists in all domains face a data avalanche - both from better instruments and from improved simulations. We believe that computer science tools and computer scientists are in a position to help all the sciences by building tools and developing techniques to manage, analyze, and visualize peta-scale scientific information. This article is summarizes our experiences over the last seven years trying to bridge the gap between database technology and the needs of the astronomy community in building the World-Wide Telescope.


title: Sequential File Programming Patterns and Performance with .NET

abstract: Programming patterns for sequential file access in the .NET Framework are described and the performance is measured. The default behavior provides excellent performance on a single disk - 50 MBps both reading and writing. Using large request sizes and doing file pre-allocation when possible have quantifiable benefits. When one considers disk arrays, .NET unbuffered IO delivers 800 MBps on a 16-disk array, but buffered IO delivers about 12% of that performance. Consequently, high-performance file and database utilities are still forced to use unbuffered IO for maximum sequential performance. The report is accompanied by downloadable source code that demonstrates the concepts and code that was used to obtain these measurements.


title: Amazons is PSPACE-complete

abstract: Amazons is a board game which combines elements of Chess and Go. It has become popular in recent years, and has served as a useful platform for both game-theoretic study and AI games research. Buro showed that simple Amazons endgames are NP-equivalent, leaving the complexity of the general case as an open problem. We settle this problem, by showing that deciding the outcome of an n x n Amazons position is PSPACE-hard. We give a reduction from one of the PSPACE-complete two-player formula games described by Schaefer. Since the number of moves in an Amazons game is polynomially bounded (unlike Chess and Go), Amazons is in PSPACE. It is thus on a par with other two-player, bounded-move, perfect-information games such as Hex, Othello, and Kayles. Our construction also provides an alternate proof that simple Amazons endgames are NP-equivalent. Our reduction uses a number of amazons polynomial in the input formula length; a remaining open problem is the complexity of Amazons when only a constant number of amazons is used.


title: On the asymptotic behavior of some Algorithms

abstract: A simple approach is presented to study the asymptotic behavior of some algorithms with an underlying tree structure. It is shown that some asymptotic oscillating behaviors can be precisely analyzed without resorting to complex analysis techniques as it is usually done in this context. A new explicit representation of periodic functions involved is obtained at the same time.


title: Can Computer Algebra be Liberated from its Algebraic Yoke ?

abstract: So far, the scope of computer algebra has been needlessly restricted to exact algebraic methods. Its possible extension to approximate analytical methods is discussed. The entangled roles of functional analysis and symbolic programming, especially the functional and transformational paradigms, are put forward. In the future, algebraic algorithms could constitute the core of extended symbolic manipulation systems including primitives for symbolic approximations.


title: Stability Analysis for Regularized Least Squares Regression

abstract: We discuss stability for a class of learning algorithms with respect to noisy labels. The algorithms we consider are for regression, and they involve the minimization of regularized risk functionals, such as L(f) := 1/N sum_i (f(x_i)-y_i)^2+ lambda ||f||_H^2. We shall call the algorithm `stable' if, when y_i is a noisy version of f*(x_i) for some function f* in H, the output of the algorithm converges to f* as the regularization term and noise simultaneously vanish. We consider two flavors of this problem, one where a data set of N points remains fixed, and the other where N -> infinity. For the case where N -> infinity, we give conditions for convergence to f_E (the function which is the expectation of y(x) for each x), as lambda -> 0. For the fixed N case, we describe the limiting 'non-noisy', 'non-regularized' function f*, and give conditions for convergence. In the process, we develop a set of tools for dealing with functionals such as L(f), which are applicable to many other problems in learning theory.


title: Estimating mutual information and multi--information in large networks

abstract: We address the practical problems of estimating the information relations that characterize large networks. Building on methods developed for analysis of the neural code, we show that reliable estimates of mutual information can be obtained with manageable computational effort. The same methods allow estimation of higher order, multi--information terms. These ideas are illustrated by analyses of gene expression, financial markets, and consumer preferences. In each case, information theoretic measures correlate with independent, intuitive measures of the underlying structures in the system.


title: When Database Systems Meet the Grid

abstract: We illustrate the benefits of combining database systems and Grid technologies for data-intensive applications. Using a cluster of SQL servers, we reimplemented an existing Grid application that finds galaxy clusters in a large astronomical database. The SQL implementation runs an order of magnitude faster than the earlier Tcl-C-file-based implementation. We discuss why and how Grid applications can take advantage of database systems.


title: A Price-Anticipating Resource Allocation Mechanism for Distributed Shared Clusters

abstract: In this paper we formulate the fixed budget resource allocation game to understand the performance of a distributed market-based resource allocation system. Multiple users decide how to distribute their budget (bids) among multiple machines according to their individual preferences to maximize their individual utility. We look at both the efficiency and the fairness of the allocation at the equilibrium, where fairness is evaluated through the measures of utility uniformity and envy-freeness. We show analytically and through simulations that despite being highly decentralized, such a system converges quickly to an equilibrium and unlike the social optimum that achieves high efficiency but poor fairness, the proposed allocation scheme achieves a nice balance of high degrees of efficiency and fairness at the equilibrium.


title: Population Sizing for Genetic Programming Based Upon Decision Making

abstract: This paper derives a population sizing relationship for genetic programming (GP). Following the population-sizing derivation for genetic algorithms in Goldberg, Deb, and Clark (1992), it considers building block decision making as a key facet. The analysis yields a GP-unique relationship because it has to account for bloat and for the fact that GP solutions often use subsolution multiple times. The population-sizing relationship depends upon tree size, solution complexity, problem difficulty and building block expression probability. The relationship is used to analyze and empirically investigate population sizing for three model GP problems named ORDER, ON-OFF and LOUD. These problems exhibit bloat to differing extents and differ in whether their solutions require the use of a building block multiple times.


title: Oiling the Wheels of Change: The Role of Adaptive Automatic Problem Decomposition in Non--Stationary Environments

abstract: Genetic algorithms (GAs) that solve hard problems quickly, reliably and accurately are called competent GAs. When the fitness landscape of a problem changes overtime, the problem is called non--stationary, dynamic or time--variant problem. This paper investigates the use of competent GAs for optimizing non--stationary optimization problems. More specifically, we use an information theoretic approach based on the minimum description length principle to adaptively identify regularities and substructures that can be exploited to respond quickly to changes in the environment. We also develop a special type of problems with bounded difficulties to test non--stationary optimization problems. The results provide new insights into non-stationary optimization problems and show that a search algorithm which automatically identifies and exploits possible decompositions is more robust and responds quickly to changes than a simple genetic algorithm.


title: Sub-Structural Niching in Non-Stationary Environments

abstract: Niching enables a genetic algorithm (GA) to maintain diversity in a population. It is particularly useful when the problem has multiple optima where the aim is to find all or as many as possible of these optima. When the fitness landscape of a problem changes overtime, the problem is called non--stationary, dynamic or time--variant problem. In these problems, niching can maintain useful solutions to respond quickly, reliably and accurately to a change in the environment. In this paper, we present a niching method that works on the problem substructures rather than the whole solution, therefore it has less space complexity than previously known niching mechanisms. We show that the method is responding accurately when environmental changes occur.


title: Sub-structural Niching in Estimation of Distribution Algorithms

abstract: We propose a sub-structural niching method that fully exploits the problem decomposition capability of linkage-learning methods such as the estimation of distribution algorithms and concentrate on maintaining diversity at the sub-structural level. The proposed method consists of three key components: (1) Problem decomposition and sub-structure identification, (2) sub-structure fitness estimation, and (3) sub-structural niche preservation. The sub-structural niching method is compared to restricted tournament selection (RTS)--a niching method used in hierarchical Bayesian optimization algorithm--with special emphasis on sustained preservation of multiple global solutions of a class of boundedly-difficult, additively-separable multimodal problems. The results show that sub-structural niching successfully maintains multiple global optima over large number of generations and does so with significantly less population than RTS. Additionally, the market share of each of the niche is much closer to the expected level in sub-structural niching when compared to RTS.


title: Idempotents, Mattson-Solomon Polynomials and Binary LDPC codes

abstract: We show how to construct an algorithm to search for binary idempotents which may be used to construct binary LDPC codes. The algorithm, which allows control of the key properties of sparseness, code rate and minimum distance, is constructed in the Mattson-Solomon domain. Some of the new codes, found by using this technique, are displayed.


title: EPspectra: A Formal Toolkit for Developing DSP Software Applications

abstract: The software approach to developing Digital Signal Processing (DSP) applications brings some great features such as flexibility, re-usability of resources and easy upgrading of applications. However, it requires long and tedious tests and verification phases because of the increasing complexity of the software. This implies the need of a software programming environment capable of putting together DSP modules and providing facilities to debug, verify and validate the code. The objective of the work is to provide such facilities as simulation and verification for developing DSP software applications. This led us to develop an extension toolkit, Epspectra, built upon Pspectra, one of the first toolkits available to design basic software radio applications on standard PC workstations. In this paper, we first present Epspectra, an Esterel-based extension of Pspectra that makes the design and implementation of portable DSP applications easier. It allows drastic reduction of testing and verification time while requiring relatively little expertise in formal verification methods. Second, we demonstrate the use of Epspectra, taking as an example the radio interface part of a GSM base station. We also present the verification procedures for the three safety properties of the implementation programs which have complex control-paths. These have to obey strict scheduling rules. In addition, Epspectra achieves the verification of the targeted application since the same model is used for the executable code generation and for the formal verification.


title: Quantum mechanics can provide unbiased result

abstract: Getting an unbiased result is a remarkably long standing problem of collective observation/measurement. It is pointed out that quantum coin tossing can generate unbiased result defeating dishonesty.


title: Markets are Dead, Long Live Markets

abstract: Researchers have long proposed using economic approaches to resource allocation in computer systems. However, few of these proposals became operational, let alone commercial. Questions persist about the economic approach regarding its assumptions, value, applicability, and relevance to system design. The goal of this paper is to answer these questions. We find that market-based resource allocation is useful, and more importantly, that mechanism design and system design should be integrated to produce systems that are both economically and computationally efficient.


title: aDORe: a modular, standards-based Digital Object Repository

abstract: This paper describes the aDORe repository architecture, designed and implemented for ingesting, storing, and accessing a vast collection of Digital Objects at the Research Library of the Los Alamos National Laboratory. The aDORe architecture is highly modular and standards-based. In the architecture, the MPEG-21 Digital Item Declaration Language is used as the XML-based format to represent Digital Objects that can consist of multiple datastreams as Open Archival Information System Archival Information Packages (OAIS AIPs).Through an ingestion process, these OAIS AIPs are stored in a multitude of autonomous repositories. A Repository Index keeps track of the creation and location of all the autonomous repositories, whereas an Identifier Locator registers in which autonomous repository a given Digital Object or OAIS AIP resides. A front-end to the complete environment, the OAI-PMH Federator, is introduced for requesting OAIS Dissemination Information Packages (OAIS DIPs). These OAIS DIPs can be the stored OAIS AIPs themselves, or transformations thereof. This front-end allows OAI-PMH harvesters to recurrently and selectively collect batches of OAIS DIPs from aDORe, and hence to create multiple, parallel services using the collected objects. Another front-end, the OpenURL Resolver, is introduced for requesting OAIS Result Sets. An OAIS Result Set is a dissemination of an individual Digital Object or of its constituent datastreams. Both front-ends make use of an MPEG-21 Digital Item Processing Engine to apply services to OAIS AIPs, Digital Objects, or constituent datastreams that were specified in a dissemination request.


title: Scalability of Genetic Programming and Probabilistic Incremental Program Evolution

abstract: This paper discusses scalability of standard genetic programming (GP) and the probabilistic incremental program evolution (PIPE). To investigate the need for both effective mixing and linkage learning, two test problems are considered: ORDER problem, which is rather easy for any recombination-based GP, and TRAP or the deceptive trap problem, which requires the algorithm to learn interactions among subsets of terminals. The scalability results show that both GP and PIPE scale up polynomially with problem size on the simple ORDER problem, but they both scale up exponentially on the deceptive problem. This indicates that while standard recombination is sufficient when no interactions need to be considered, for some problems linkage learning is necessary. These results are in agreement with the lessons learned in the domain of binary-string genetic algorithms (GAs). Furthermore, the paper investigates the effects of introducing utnnecessary and irrelevant primitives on the performance of GP and PIPE.


title: Fixed Type Theorems

abstract: This submission has been withdrawn at the request of the author.


title: Logic Column 11: The Finite and the Infinite in Temporal Logic

abstract: This article examines the interpretation of the LTL temporal operators over finite and infinite sequences. This is used as the basis for deriving a sound and complete axiomatization for Caret, a recent temporal logic for reasoning about programs with nested procedure calls and returns.


title: On Dynamic Range Reporting in One Dimension

abstract: We consider the problem of maintaining a dynamic set of integers and answering queries of the form: report a point (equivalently, all points) in a given interval. Range searching is a natural and fundamental variant of integer search, and can be solved using predecessor search. However, for a RAM with w-bit words, we show how to perform updates in O(lg w) time and answer queries in O(lglg w) time. The update time is identical to the van Emde Boas structure, but the query time is exponentially faster. Existing lower bounds show that achieving our query time for predecessor search requires doubly-exponentially slower updates. We present some arguments supporting the conjecture that our solution is optimal. Our solution is based on a new and interesting recursion idea which is "more extreme" that the van Emde Boas recursion. Whereas van Emde Boas uses a simple recursion (repeated halving) on each path in a trie, we use a nontrivial, van Emde Boas-like recursion on every such path. Despite this, our algorithm is quite clean when seen from the right angle. To achieve linear space for our data structure, we solve a problem which is of independent interest. We develop the first scheme for dynamic perfect hashing requiring sublinear space. This gives a dynamic Bloomier filter (an approximate storage scheme for sparse vectors) which uses low space. We strengthen previous lower bounds to show that these results are optimal.


title: Pseudo-Codewords of Cycle Codes via Zeta Functions

abstract: Cycle codes are a special case of low-density parity-check (LDPC) codes and as such can be decoded using an iterative message-passing decoding algorithm on the associated Tanner graph. The existence of pseudo-codewords is known to cause the decoding algorithm to fail in certain instances. In this paper, we draw a connection between pseudo-codewords of cycle codes and the so-called edge zeta function of the associated normal graph and show how the Newton polyhedron of the zeta function equals the fundamental cone of the code, which plays a crucial role in characterizing the performance of iterative decoding algorithms.


title: Multiobjective hBOA, Clustering, and Scalability

abstract: This paper describes a scalable algorithm for solving multiobjective decomposable problems by combining the hierarchical Bayesian optimization algorithm (hBOA) with the nondominated sorting genetic algorithm (NSGA-II) and clustering in the objective space. It is first argued that for good scalability, clustering or some other form of niching in the objective space is necessary and the size of each niche should be approximately equal. Multiobjective hBOA (mohBOA) is then described that combines hBOA, NSGA-II and clustering in the objective space. The algorithm mohBOA differs from the multiobjective variants of BOA and hBOA proposed in the past by including clustering in the objective space and allocating an approximately equally sized portion of the population to each cluster. The algorithm mohBOA is shown to scale up well on a number of problems on which standard multiobjective evolutionary algorithms perform poorly.


title: Near Maximum-Likelihood Performance of Some New Cyclic Codes Constructed in the Finite-Field Transform Domain

abstract: It is shown that some well-known and some new cyclic codes with orthogonal parity-check equations can be constructed in the finite-field transform domain. It is also shown that, for some binary linear cyclic codes, the performance of the iterative decoder can be improved by substituting some of the dual code codewords in the parity-check matrix with other dual code codewords formed from linear combinations. This technique can bring the performance of a code closer to its maximum-likelihood performance, which can be derived from the erroneous decoded codeword whose euclidean distance with the respect to the received block is smaller than that of the correct codeword. For (63,37), (93,47) and (105,53) cyclic codes, the maximum-likelihood performance is realised with this technique.


title: Improved Iterative Decoding for Perpendicular Magnetic Recording

abstract: An algorithm of improving the performance of iterative decoding on perpendicular magnetic recording is presented. This algorithm follows on the authors' previous works on the parallel and serial concatenated turbo codes and low-density parity-check codes. The application of this algorithm with signal-to-noise ratio mismatch technique shows promising results in the presence of media noise. We also show that, compare to the standard iterative decoding algorithm, an improvement of within one order of magnitude can be achieved.


title: GF(2^m) Low-Density Parity-Check Codes Derived from Cyclotomic Cosets

abstract: Based on the ideas of cyclotomic cosets, idempotents and Mattson-Solomon polynomials, we present a new method to construct GF(2^m), where m>0 cyclic low-density parity-check codes. The construction method produces the dual code idempotent which is used to define the parity-check matrix of the low-density parity-check code. An interesting feature of this construction method is the ability to increment the code dimension by adding more idempotents and so steadily decrease the sparseness of the parity-check matrix. We show that the constructed codes can achieve performance very close to the sphere-packing-bound constrained for binary transmission.


title: The Number of Spanning Trees in Kn-complements of Quasi-threshold Graphs

abstract: In this paper we examine the classes of graphs whose $K_n$-complements are trees and quasi-threshold graphs and derive formulas for their number of spanning trees; for a subgraph $H$ of $K_n$, the $K_n$-complement of $H$ is the graph $K_n-H$ which is obtained from $K_n$ by removing the edges of $H$. Our proofs are based on the complement spanning-tree matrix theorem, which expresses the number of spanning trees of a graph as a function of the determinant of a matrix that can be easily constructed from the adjacency relation of the graph. Our results generalize previous results and extend the family of graphs of the form $K_n-H$ admitting formulas for the number of their spanning trees.


title: Efficient Parallel Simulations of Asynchronous Cellular Arrays

abstract: A definition for a class of asynchronous cellular arrays is proposed. An example of such asynchrony would be independent Poisson arrivals of cell iterations. The Ising model in the continuous time formulation of Glauber falls into this class. Also proposed are efficient parallel algorithms for simulating these asynchronous cellular arrays. In the algorithms, one or several cells are assigned to a processing element (PE), local times for different PEs can be different. Although the standard serial algorithm by Metropolis, Rosenbluth, Rosenbluth, Teller, and Teller can simulate such arrays, it is usually believed to be without an efficient parallel counterpart. However, the proposed parallel algorithms contradict this belief proving to be both efficient and able to perform the same task as the standard algorithm. The results of experiments with the new algorithms are encouraging: the speed-up is greater than 16 using 25 PEs on a shared memory MIMD bus computer, and greater than 1900 using 2**14 PEs on a SIMD computer. The algorithm by Bortz, Kalos, and Lebowitz can be incorporated in the proposed parallel algorithms, further contributing to speed-up. [In this paper I invented the update-cites-of-local-time-minima parallel simulation scheme. Now the scheme is becoming popular. Many misprints of the original 1987 Complex Systems publication are corrected here.-B.L.]


title: Testing Systems of Concurrent Black-boxes--an Automata-Theoretic and Decompositional Approach

abstract: The global testing problem studied in this paper is to seek a definite answer to whether a system of concurrent black-boxes has an observable behavior in a given finite (but could be huge) set "Bad". We introduce a novel approach to solve the problem that does not require integration testing. Instead, in our approach, the global testing problem is reduced to testing individual black-boxes in the system one by one in some given order. Using an automata-theoretic approach, test sequences for each individual black-box are generated from the system's description as well as the test results of black-boxes prior to this black-box in the given order. In contrast to the conventional compositional/modular verification/testing approaches, our approach is essentially decompositional. Also, our technique is complete, sound, and can be carried out automatically. Our experiment results show that the total number of tests needed to solve the global testing problem is substantially small even for an extremely large "Bad".


title: Logarithmic Lower Bounds in the Cell-Probe Model

abstract: We develop a new technique for proving cell-probe lower bounds on dynamic data structures. This technique enables us to prove an amortized randomized Omega(lg n) lower bound per operation for several data structural problems on n elements, including partial sums, dynamic connectivity among disjoint paths (or a forest or a graph), and several other dynamic graph problems (by simple reductions). Such a lower bound breaks a long-standing barrier of Omega(lg n / lglg n) for any dynamic language membership problem. It also establishes the optimality of several existing data structures, such as Sleator and Tarjan's dynamic trees. We also prove the first Omega(log_B n) lower bound in the external-memory model without assumptions on the data structure (such as the comparison model). Our lower bounds also give a query-update trade-off curve matched, e.g., by several data structures for dynamic connectivity in graphs. We also prove matching upper and lower bounds for partial sums when parameterized by the word size and the maximum additive change in an update.


title: Unified Large System Analysis of MMSE and Adaptive Least Squares Receivers for a class of Random Matrix Channels

abstract: We present a unified large system analysis of linear receivers for a class of random matrix channels. The technique unifies the analysis of both the minimum-mean-squared-error (MMSE) receiver and the adaptive least-squares (ALS) receiver, and also uses a common approach for both random i.i.d. and random orthogonal precoding. We derive expressions for the asymptotic signal-to-interference-plus-noise (SINR) of the MMSE receiver, and both the transient and steady-state SINR of the ALS receiver, trained using either i.i.d. data sequences or orthogonal training sequences. The results are in terms of key system parameters, and allow for arbitrary distributions of the power of each of the data streams and the eigenvalues of the channel correlation matrix. In the case of the ALS receiver, we allow a diagonal loading constant and an arbitrary data windowing function. For i.i.d. training sequences and no diagonal loading, we give a fundamental relationship between the transient/steady-state SINR of the ALS and the MMSE receivers. We demonstrate that for a particular ratio of receive to transmit dimensions and window shape, all channels which have the same MMSE SINR have an identical transient ALS SINR response. We demonstrate several applications of the results, including an optimization of information throughput with respect to training sequence length in coded block transmission.


title: Compatible Triangulations and Point Partitions by Series-Triangular Graphs

abstract: We introduce series-triangular graph embeddings and show how to partition point sets with them. This result is then used to improve the upper bound on the number of Steiner points needed to obtain compatible triangulations of point sets. The problem is generalized to finding compatible triangulations for more than two point sets and we show that such triangulations can be constructed with only a linear number of Steiner points added to each point set.


title: The complexity of computing the Hilbert polynomial of smooth equidimensional complex projective varieties

abstract: We continue the study of counting complexity begun in [Buergisser, Cucker 04] and [Buergisser, Cucker, Lotz 05] by proving upper and lower bounds on the complexity of computing the Hilbert polynomial of a homogeneous ideal. We show that the problem of computing the Hilbert polynomial of a smooth equidimensional complex projective variety can be reduced in polynomial time to the problem of counting the number of complex common zeros of a finite set of multivariate polynomials. Moreover, we prove that the more general problem of computing the Hilbert polynomial of a homogeneous ideal is polynomial space hard. This implies polynomial space lower bounds for both the problems of computing the rank and the Euler characteristic of cohomology groups of coherent sheaves on projective space, improving the #P-lower bound of Bach (JSC 1999).


title: Adaptive grids as parametrized scale-free networks

abstract: In this paper we present a possible model of adaptive grids for numerical resolution of differential problems, using physical or geometrical properties, as viscosity or velocity gradient of a moving fluid. The relation between the values of grid step and these entities is based on the mathematical scheme offered by the model of scale-free networks, due to Barabasi, so that the step can be connected to the other variables by a constitutive relation. Some examples and an application are discussed, showing that this approach can be further developed for treatment of more complex situations.

categories: cs.NA math-ph math.AP math.MP physics.flu-dyn


title: Proof obligations for specification and refinement of liveness properties under weak fairness

abstract: In this report, we present a formal model of fair iteration of events for B event systems. The model is used to justify proof obligations for basic liveness properties and preservation under refinement of general liveness properties. The model of fair iteration of events uses the dovetail operator, an operator proposed by Broy and Nelson to model fair choice. The proofs are mainly founded in fixpoint calculations of fair iteration of events and weakest precondition calculus.


title: The succinctness of first-order logic on linear orders

abstract: Succinctness is a natural measure for comparing the strength of different logics. Intuitively, a logic L_1 is more succinct than another logic L_2 if all properties that can be expressed in L_2 can be expressed in L_1 by formulas of (approximately) the same size, but some properties can be expressed in L_1 by (significantly) smaller formulas. We study the succinctness of logics on linear orders. Our first theorem is concerned with the finite variable fragments of first-order logic. We prove that: (i) Up to a polynomial factor, the 2- and the 3-variable fragments of first-order logic on linear orders have the same succinctness. (ii) The 4-variable fragment is exponentially more succinct than the 3-variable fragment. Our second main result compares the succinctness of first-order logic on linear orders with that of monadic second-order logic. We prove that the fragment of monadic second-order logic that has the same expressiveness as first-order logic on linear orders is non-elementarily more succinct than first-order logic.


title: An Automated Analysis of the Security of Quantum Key Distribution

abstract: This paper discusses the use of computer-aided verification as a practical means for analysing quantum information systems; specifically, the BB84 protocol for quantum key distribution is examined using this method. This protocol has been shown to be unconditionally secure against all attacks in an information-theoretic setting, but the relevant security proof requires a thorough understanding of the formalism of quantum mechanics and is not easily adaptable to practical scenarios. Our approach is based on probabilistic model-checking; we have used the PRISM model-checker to show that, as the number of qubits transmitted in BB84 is increased, the equivocation of the eavesdropper with respect to the channel decreases exponentially. We have also shown that the probability of detecting the presence of an eavesdropper increases exponentially with the number of qubits. The results presented here are a testament to the effectiveness of the model-checking approach for systems where analytical solutions may not be possible or plausible.


title: Generalised Bent Criteria for Boolean Functions (I)

abstract: Generalisations of the bent property of a boolean function are presented, by proposing spectral analysis with respect to a well-chosen set of local unitary transforms. Quadratic boolean functions are related to simple graphs and it is shown that the orbit generated by successive Local Complementations on a graph can be found within the transform spectra under investigation. The flat spectra of a quadratic boolean function are related to modified versions of its associated adjacency matrix.


title: Generalised Bent Criteria for Boolean Functions (II)

abstract: In the first part of this paper [16], some results on how to compute the flat spectra of Boolean constructions w.r.t. the transforms {I,H}^n, {H,N}^n and {I,H,N}^n were presented, and the relevance of Local Complementation to the quadratic case was indicated. In this second part, the results are applied to develop recursive formulae for the numbers of flat spectra of some structural quadratics. Observations are made as to the generalised Bent properties of boolean functions of algebraic degree greater than two, and the number of flat spectra w.r.t. {I,H,N}^n are computed for some of them.


title: A Semantic Grid-based E-Learning Framework (SELF)

abstract: E-learning can be loosely defined as a wide set of applications and processes, which uses available electronic media (and tools) to deliver vocational education and training. With its increasing recognition as an ubiquitous mode of instruction and interaction in the academic as well as corporate world, the need for a scaleable and realistic model is becoming important. In this paper we introduce SELF; a Semantic grid-based E-Learning Framework. SELF aims to identify the key-enablers in a practical grid-based E-learning environment and to minimize technological reworking by proposing a well-defined interaction plan among currently available tools and technologies. We define a dichotomy with E-learning specific application layers on top and semantic grid-based support layers underneath. We also map the latest open and freeware technologies with various components in SELF.


title: Log Analysis Case Study Using LoGS

abstract: A very useful technique a network administrator can use to identify problematic network behavior is careful analysis of logs of incoming and outgoing network flows. The challenge one faces when attempting to undertake this course of action, though, is that large networks tend to generate an extremely large quantity of network traffic in a very short period of time, resulting in very large traffic logs which must be analyzed post-generation with an eye for contextual information which may reveal symptoms of problematic traffic. A better technique is to perform real-time log analysis using a real-time context-generating tool such as LoGS.


title: A low-cost time-hopping impulse radio system for high data rate transmission

abstract: We present an efficient, low-cost implementation of time-hopping impulse radio that fulfills the spectral mask mandated by the FCC and is suitable for high-data-rate, short-range communications. Key features are: (i) all-baseband implementation that obviates the need for passband components, (ii) symbol-rate (not chip rate) sampling, A/D conversion, and digital signal processing, (iii) fast acquisition due to novel search algorithms, (iv) spectral shaping that can be adapted to accommodate different spectrum regulations and interference environments. Computer simulations show that this system can provide 110Mbit/s at 7-10m distance, as well as higher data rates at shorter distances under FCC emissions limits. Due to the spreading concept of time-hopping impulse radio, the system can sustain multiple simultaneous users, and can suppress narrowband interference effectively.


title: Improved Tag Set Design and Multiplexing Algorithms for Universal Arrays

abstract: In this paper we address two optimization problems arising in the design of genomic assays based on universal tag arrays. First, we address the universal array tag set design problem. For this problem, we extend previous formulations to incorporate antitag-to-antitag hybridization constraints in addition to constraints on antitag-to-tag hybridization specificity, establish a constructive upper bound on the maximum number of tags satisfying the extended constraints, and propose a simple greedy tag selection algorithm. Second, we give methods for improving the multiplexing rate in large-scale genomic assays by combining primer selection with tag assignment. Experimental results on simulated data show that this integrated optimization leads to reductions of up to 50% in the number of required arrays.


title: On quasi-cyclic interleavers for parallel turbo codes

abstract: We present an interleaving scheme that yields quasi-cyclic turbo codes. We prove that randomly chosen members of this family yield with probability almost 1 turbo codes with asymptotically optimum minimum distance, i.e. growing as a logarithm of the interleaver size. These interleavers are also very practical in terms of memory requirements and their decoding error probabilities for small block lengths compare favorably with previous interleaving schemes.


title: Co-Authorship Networks in the Digital Library Research Community

abstract: The field of digital libraries (DLs) coalesced in 1994: the first digital library conferences were held that year, awareness of the World Wide Web was accelerating, and the National Science Foundation awarded $24 Million (U.S.) for the Digital Library Initiative (DLI). In this paper we examine the state of the DL domain after a decade of activity by applying social network analysis to the co-authorship network of the past ACM, IEEE, and joint ACM/IEEE digital library conferences. We base our analysis on a common binary undirectional network model to represent the co-authorship network, and from it we extract several established network measures. We also introduce a weighted directional network model to represent the co-authorship network, for which we define $AuthorRank$ as an indicator of the impact of an individual author in the network. The results are validated against conference program committee members in the same period. The results show clear advantages of PageRank and AuthorRank over degree, closeness and betweenness centrality metrics. We also investigate the amount and nature of international participation in Joint Conference on Digital Libraries (JCDL).


title: Decomposable Problems, Niching, and Scalability of Multiobjective Estimation of Distribution Algorithms

abstract: The paper analyzes the scalability of multiobjective estimation of distribution algorithms (MOEDAs) on a class of boundedly-difficult additively-separable multiobjective optimization problems. The paper illustrates that even if the linkage is correctly identified, massive multimodality of the search problems can easily overwhelm the nicher and lead to exponential scale-up. Facetwise models are subsequently used to propose a growth rate of the number of differing substructures between the two objectives to avoid the niching method from being overwhelmed and lead to polynomial scalability of MOEDAs.


title: The Complexity of Computing the Size of an Interval

abstract: Given a p-order A over a universe of strings (i.e., a transitive, reflexive, antisymmetric relation such that if (x, y) is an element of A then |x| is polynomially bounded by |y|), an interval size function of A returns, for each string x in the universe, the number of strings in the interval between strings b(x) and t(x) (with respect to A), where b(x) and t(x) are functions that are polynomial-time computable in the length of x. By choosing sets of interval size functions based on feasibility requirements for their underlying p-orders, we obtain new characterizations of complexity classes. We prove that the set of all interval size functions whose underlying p-orders are polynomial-time decidable is exactly #P. We show that the interval size functions for orders with polynomial-time adjacency checks are closely related to the class FPSPACE(poly). Indeed, FPSPACE(poly) is exactly the class of all nonnegative functions that are an interval size function minus a polynomial-time computable function. We study two important functions in relation to interval size functions. The function #DIV maps each natural number n to the number of nontrivial divisors of n. We show that #DIV is an interval size function of a polynomial-time decidable partial p-order with polynomial-time adjacency checks. The function #MONSAT maps each monotone boolean formula F to the number of satisfying assignments of F. We show that #MONSAT is an interval size function of a polynomial-time decidable total p-order with polynomial-time adjacency checks. Finally, we explore the related notion of cluster computation.


title: New approach for Finite Difference Method for Thermal Analysis of Passive Solar Systems

abstract: Mathematical treatment of massive wall systems is a useful tool for investigation of these solar applications. The objectives of this work are to develop (and validate) a numerical solution model for predication the thermal behaviour of passive solar systems with massive wall, to improve knowledge of using indirect passive solar systems and assess its energy efficiency according to climatic conditions in Bulgaria. The problem of passive solar systems with massive walls is modelled by thermal and mass transfer equations. As a boundary conditions for the mathematical problem are used equations, which describe influence of weather data and constructive parameters of building on the thermal performance of the passive system. The mathematical model is solved by means of finite differences method and improved solution procedure. In article are presented results of theoretical and experimental study for developing and validating a numerical solution model for predication the thermal behaviour of passive solar systems with massive wall.


title: Perspectives for Strong Artificial Life

abstract: This text introduces the twin deadlocks of strong artificial life. Conceptualization of life is a deadlock both because of the existence of a continuum between the inert and the living, and because we only know one instance of life. Computationalism is a second deadlock since it remains a matter of faith. Nevertheless, artificial life realizations quickly progress and recent constructions embed an always growing set of the intuitive properties of life. This growing gap between theory and realizations should sooner or later crystallize in some kind of paradigm shift and then give clues to break the twin deadlocks.


title: A Geographic Directed Preferential Internet Topology Model

abstract: The goal of this work is to model the peering arrangements between Autonomous Systems (ASes). Most existing models of the AS-graph assume an undirected graph. However, peering arrangements are mostly asymmetric Customer-Provider arrangements, which are better modeled as directed edges. Furthermore, it is well known that the AS-graph, and in particular its clustering structure, is influenced by geography. We introduce a new model that describes the AS-graph as a directed graph, with an edge going from the customer to the provider, but also models symmetric peer-to-peer arrangements, and takes geography into account. We are able to mathematically analyze its power-law exponent and number of leaves. Beyond the analysis we have implemented our model as a synthetic network generator we call GdTang. Experimentation with GdTang shows that the networks it produces are more realistic than those generated by other network generators, in terms of its power-law exponent, fractions of customer-provider and symmetric peering arrangements, and the size of its dense core. We believe that our model is the first to manifest realistic regional dense cores that have a clear geographic flavor. Our synthetic networks also exhibit path inflation effects that are similar to those observed in the real AS graph.


title: Tree Parity Machine Rekeying Architectures

abstract: The necessity to secure the communication between hardware components in embedded systems becomes increasingly important with regard to the secrecy of data and particularly its commercial use. We suggest a low-cost (i.e. small logic-area) solution for flexible security levels and short key lifetimes. The basis is an approach for symmetric key exchange using the synchronisation of Tree Parity Machines. Fast successive key generation enables a key exchange within a few milliseconds, given realistic communication channels with a limited bandwidth. For demonstration we evaluate characteristics of a standard-cell ASIC design realisation as IP-core in 0.18-micrometer CMOS-technology.


title: Nonlinear MMSE Multiuser Detection Based on Multivariate Gaussian Approximation

abstract: In this paper, a class of nonlinear MMSE multiuser detectors are derived based on a multivariate Gaussian approximation of the multiple access interference. This approach leads to expressions identical to those describing the probabilistic data association (PDA) detector, thus providing an alternative analytical justification for this structure. A simplification to the PDA detector based on approximating the covariance matrix of the multivariate Gaussian distribution is suggested, resulting in a soft interference cancellation scheme. Corresponding multiuser soft-input, soft-output detectors delivering extrinsic log-likelihood ratios are derived for application in iterative multiuser decoders. Finally, a large system performance analysis is conducted for the simplified PDA, showing that the bit error rate performance of this detector can be accurately predicted and related to the replica method analysis for the optimal detector. Methods from statistical neuro-dynamics are shown to provide a closely related alternative large system prediction. Numerical results demonstrate that for large systems, the bit error rate is accurately predicted by the analysis and found to be close to optimal performance.


title: The Lattice of Machine Invariant Sets and Subword Complexity

abstract: We investigate the lattice of machine invariant classes. This is an infinite completely distributive lattice but it is not a Boolean lattice. We show the subword complexity and the growth function create machine invariant classes. So the lattice would serve as a measure of words cryptographic quality if we like to identify new stream ciphers suitable for widespread adoption.


title: Highly Scalable Algorithms for Robust String Barcoding

abstract: String barcoding is a recently introduced technique for genomic-based identification of microorganisms. In this paper we describe the engineering of highly scalable algorithms for robust string barcoding. Our methods enable distinguisher selection based on whole genomic sequences of hundreds of microorganisms of up to bacterial size on a well-equipped workstation, and can be easily parallelized to further extend the applicability range to thousands of bacterial size genomes. Experimental results on both randomly generated and NCBI genomic data show that whole-genome based selection results in a number of distinguishers nearly matching the information theoretic lower bounds for the problem.


title: On the Complexity of Real Functions

abstract: We develop a notion of computability and complexity of functions over the reals, which seems to be very natural when one tries to determine just how "difficult" a certain function is. This notion can be viewed as an extension of both BSS computability [Blum, Cucker, Shub, Smale 1998], and bit computability in the tradition of computable analysis [Weihrauch 2000] as it relies on the latter but allows some discontinuities and multiple values.


title: Master Algorithms for Active Experts Problems based on Increasing Loss Values

abstract: We specify an experts algorithm with the following characteristics: (a) it uses only feedback from the actions actually chosen (bandit setup), (b) it can be applied with countably infinite expert classes, and (c) it copes with losses that may grow in time appropriately slowly. We prove loss bounds against an adaptive adversary. From this, we obtain master algorithms for "active experts problems", which means that the master's actions may influence the behavior of the adversary. Our algorithm can significantly outperform standard experts algorithms on such problems. Finally, we combine it with a universal expert class. This results in a (computationally infeasible) universal master algorithm which performs - in a certain sense - almost as well as any computable strategy, for any online problem.


title: Limits of Rush Hour Logic Complexity

abstract: Rush Hour Logic was introduced in [Flake&Baum99] as a model of computation inspired by the ``Rush Hour'' toy puzzle, in which cars can move horizontally or vertically within a parking lot. The authors show how the model supports polynomial space computation, using certain car configurations as building blocks to construct boolean circuits for a cpu and memory. They consider the use of cars of length 3 crucial to their construction, and conjecture that cars of size 2 only, which we'll call `Size 2 Rush Hour', do not support polynomial space computation. We settle this conjecture by showing that the required building blocks are constructible in Size 2 Rush Hour. Furthermore, we consider Unit Rush Hour, which was hitherto believed to be trivial, show its relation to maze puzzles, and provide empirical support for its hardness.


title: Koordinatenfreies Lokationsbewusstsein (Localization without Coordinates)

abstract: Localization is one of the fundamental issues in sensor networks. It is almost always assumed that it must be solved by assigning coordinates to the nodes. This article discusses positioning algorithms from a theoretical, practical and simulative point of view, and identifies difficulties and limitations. Ideas for more abstract means of location awareness are presented and the resulting possible improvements for applications are shown. Nodes with certain topological or environmental properties are clustered, and the neighborhood structure of the clusters is modeled as a graph. Eines der fundamentalen Probleme in Sensornetzwerken besteht darin, ein Bewusstsein fuer die Position eines Knotens im Netz zu entwickeln. Dabei wird fast immer davon ausgegangen, dass dies durch die Zuweisung von Koordinaten zu erfolgen hat. In diesem Artikel wird auf theoretischer, praktischer und simulativer Ebene ein kritischer Blick auf entsprechende Verfahren geworfen, und es werden Grenzen aufgezeigt. Es wird ein Ansatz vorgestellt, mit dem in der Zukunft eine abstrakte Form von Lokationsbewusstsein etabliert werden kann, und es wird gezeigt, wie Anwendungen dadurch verbessert werden koennen. Er basiert auf einer graphenbasierten Modellierung des Netzes: Knoten mit bestimmten topologischen oder Umwelteigenschaften werden zu Clustern zusammengefasst, und Clusternachbarschaften dann als Graphen modelliert.


title: Bidimensionality, Map Graphs, and Grid Minors

abstract: In this paper we extend the theory of bidimensionality to two families of graphs that do not exclude fixed minors: map graphs and power graphs. In both cases we prove a polynomial relation between the treewidth of a graph in the family and the size of the largest grid minor. These bounds improve the running times of a broad class of fixed-parameter algorithms. Our novel technique of using approximate max-min relations between treewidth and size of grid minors is powerful, and we show how it can also be used, e.g., to prove a linear relation between the treewidth of a bounded-genus graph and the treewidth of its dual.


title: Analysis of Second-order Statistics Based Semi-blind Channel Estimation in CDMA Channels

abstract: The performance of second order statistics (SOS) based semi-blind channel estimation in long-code DS-CDMA systems is analyzed. The covariance matrix of SOS estimates is obtained in the large system limit, and is used to analyze the large-sample performance of two SOS based semi-blind channel estimation algorithms. A notion of blind estimation efficiency is also defined and is examined via simulation results.


title: Batch is back: CasJobs, serving multi-TB data on the Web

abstract: The Sloan Digital Sky Survey (SDSS) science database describes over 140 million objects and is over 1.5 TB in size. The SDSS Catalog Archive Server (CAS) provides several levels of query interface to the SDSS data via the SkyServer website. Most queries execute in seconds or minutes. However, some queries can take hours or days, either because they require non-index scans of the largest tables, or because they request very large result sets, or because they represent very complex aggregations of the data. These "monster queries" not only take a long time, they also affect response times for everyone else - one or more of them can clog the entire system. To ameliorate this problem, we developed a multi-server multi-queue batch job submission and tracking system for the CAS called CasJobs. The transfer of very large result sets from queries over the network is another serious problem. Statistics suggested that much of this data transfer is unnecessary; users would prefer to store results locally in order to allow further joins and filtering. To allow local analysis, a system was developed that gives users their own personal databases (MyDB) at the server side. Users may transfer data to their MyDB, and then perform further analysis before extracting it to their own machine. MyDB tables also provide a convenient way to share results of queries with collaborators without downloading them. CasJobs is built using SOAP XML Web services and has been in operation since May 2004.


title: A note on the Burrows-Wheeler transformation

abstract: We relate the Burrows-Wheeler transformation with a result in combinatorics on words known as the Gessel-Reutenauer transformation.


title: On sample complexity for computational pattern recognition

abstract: In statistical setting of the pattern recognition problem the number of examples required to approximate an unknown labelling function is linear in the VC dimension of the target learning class. In this work we consider the question whether such bounds exist if we restrict our attention to computable pattern recognition methods, assuming that the unknown labelling function is also computable. We find that in this case the number of examples required for a computable method to approximate the labelling function not only is not linear, but grows faster (in the VC dimension of the class) than any computable function. No time or space constraints are put on the predictors or target functions; the only resource we consider is the training examples. The task of pattern recognition is considered in conjunction with another learning problem -- data compression. An impossibility result for the task of data compression allows us to estimate the sample complexity for pattern recognition.


title: How far will you walk to find your shortcut: Space Efficient Synopsis Construction Algorithms

abstract: In this paper we consider the wavelet synopsis construction problem without the restriction that we only choose a subset of coefficients of the original data. We provide the first near optimal algorithm. We arrive at the above algorithm by considering space efficient algorithms for the restricted version of the problem. In this context we improve previous algorithms by almost a linear factor and reduce the required space to almost linear. Our techniques also extend to histogram construction, and improve the space-running time tradeoffs for V-Opt and range query histograms. We believe the idea applies to a broad range of dynamic programs and demonstrate it by showing improvements in a knapsack-like setting seen in construction of Extended Wavelets.


title: Learning nonsingular phylogenies and hidden Markov models

abstract: In this paper we study the problem of learning phylogenies and hidden Markov models. We call a Markov model nonsingular if all transition matrices have determinants bounded away from 0 (and 1). We highlight the role of the nonsingularity condition for the learning problem. Learning hidden Markov models without the nonsingularity condition is at least as hard as learning parity with noise, a well-known learning problem conjectured to be computationally hard. On the other hand, we give a polynomial-time algorithm for learning nonsingular phylogenies and hidden Markov models.

categories: cs.LG cs.CE math.PR math.ST q-bio.PE stat.TH


title: On the Achievable Information Rates of Finite-State Input Two-Dimensional Channels with Memory

abstract: The achievable information rate of finite-state input two-dimensional (2-D) channels with memory is an open problem, which is relevant, e.g., for inter-symbol-interference (ISI) channels and cellular multiple-access channels. We propose a method for simulation-based computation of such information rates. We first draw a connection between the Shannon-theoretic information rate and the statistical mechanics notion of free energy. Since the free energy of such systems is intractable, we approximate it using the cluster variation method, implemented via generalized belief propagation. The derived, fully tractable, algorithm is shown to provide a practically accurate estimate of the information rate. In our experimental study we calculate the information rates of 2-D ISI channels and of hexagonal Wyner cellular networks with binary inputs, for which formerly only bounds were known.


title: Semantical Characterizations and Complexity of Equivalences in Answer Set Programming

abstract: In recent research on non-monotonic logic programming, repeatedly strong equivalence of logic programs P and Q has been considered, which holds if the programs P union R and Q union R have the same answer sets for any other program R. This property strengthens equivalence of P and Q with respect to answer sets (which is the particular case for R is the empty set), and has its applications in program optimization, verification, and modular logic programming. In this paper, we consider more liberal notions of strong equivalence, in which the actual form of R may be syntactically restricted. On the one hand, we consider uniform equivalence, where R is a set of facts rather than a set of rules. This notion, which is well known in the area of deductive databases, is particularly useful for assessing whether programs P and Q are equivalent as components of a logic program which is modularly structured. On the other hand, we consider relativized notions of equivalence, where R ranges over rules over a fixed alphabet, and thus generalize our results to relativized notions of strong and uniform equivalence. For all these notions, we consider disjunctive logic programs in the propositional (ground) case, as well as some restricted classes, provide semantical characterizations and analyze the computational complexity. Our results, which naturally extend to answer set semantics for programs with strong negation, complement the results on strong equivalence of logic programs and pave the way for optimizations in answer set solvers as a tool for input-based problem solving.


title: Multilevel expander codes

abstract: We define multilevel codes on bipartite graphs that have properties analogous to multilevel serial concatenations. A decoding algorithm is described that corrects a proportion of errors equal to half the Blokh-Zyablov bound on the minimum distance. The error probability of this algorithm has exponent similar to that of serially concatenated multilevel codes.


title: Sensor Configuration and Activation for Field Detection in Large Sensor Arrays

abstract: The problems of sensor configuration and activation for the detection of correlated random fields using large sensor arrays are considered. Using results that characterize the large-array performance of sensor networks in this application, the detection capabilities of different sensor configurations are analyzed and compared. The dependence of the optimal choice of configuration on parameters such as sensor signal-to-noise ratio (SNR), field correlation, etc., is examined, yielding insights into the most effective choices for sensor selection and activation in various operating regimes.


title: Tables, Memorized Semirings and Applications

abstract: We define and construct a new data structure, the tables, this structure generalizes the (finite) $k$-sets sets of Eilenberg \cite{Ei}, it is versatile (one can vary the letters, the words and the coefficients). We derive from this structure a new semiring (with several semiring structures) which can be applied to the needs of automatic processing multi-agents behaviour problems. The purpose of this account/paper is to present also the basic elements of this new structures from a combinatorial point of view. These structures present a bunch of properties. They will be endowed with several laws namely : Sum, Hadamard product, Cauchy product, Fuzzy operations (min, max, complemented product) Two groups of applications are presented. The first group is linked to the process of "forgetting" information in the tables. The second, linked to multi-agent systems, is announced by showing a methodology to manage emergent organization from individual behaviour models.


title: Graphs and colorings for answer set programming

abstract: We investigate the usage of rule dependency graphs and their colorings for characterizing and computing answer sets of logic programs. This approach provides us with insights into the interplay between rules when inducing answer sets. We start with different characterizations of answer sets in terms of totally colored dependency graphs that differ in graph-theoretical aspects. We then develop a series of operational characterizations of answer sets in terms of operators on partial colorings. In analogy to the notion of a derivation in proof theory, our operational characterizations are expressed as (non-deterministically formed) sequences of colorings, turning an uncolored graph into a totally colored one. In this way, we obtain an operational framework in which different combinations of operators result in different formal properties. Among others, we identify the basic strategy employed by the noMoRe system and justify its algorithmic approach. Furthermore, we distinguish operations corresponding to Fitting's operator as well as to well-founded semantics. (To appear in Theory and Practice of Logic Programming (TPLP))


title: Impulse Radio Systems with Multiple Types of Ultra-Wideband Pulses

abstract: Spectral properties and performance of multi-pulse impulse radio ultra-wideband systems with pulse-based polarity randomization are analyzed. Instead of a single type of pulse transmitted in each frame, multiple types of pulses are considered, which is shown to reduce the effects of multiple-access interference. First, the spectral properties of a multi-pulse impulse radio system is investigated. It is shown that the power spectral density is the average of spectral contents of different pulse shapes. Then, approximate closed-form expressions for bit error probability of a multi-pulse impulse radio system are derived for RAKE receivers in asynchronous multiuser environments. The theoretical and simulation results indicate that impulse radio systems that are more robust against multiple-access interference than a "classical" impulse radio system can be designed with multiple types of ultra-wideband pulses.


title: On the Typicality of the Linear Code Among the LDPC Coset Code Ensemble

abstract: Density evolution (DE) is one of the most powerful analytical tools for low-density parity-check (LDPC) codes on memoryless binary-input/symmetric-output channels. The case of non-symmetric channels is tackled either by the LDPC coset code ensemble (a channel symmetrizing argument) or by the generalized DE for linear codes on non-symmetric channels. Existing simulations show that the bit error rate performances of these two different approaches are nearly identical. This paper explains this phenomenon by proving that as the minimum check node degree $d_c$ becomes sufficiently large, the performance discrepancy of the linear and the coset LDPC codes is theoretically indistinguishable. This typicality of linear codes among the LDPC coset code ensemble provides insight into the concentration theorem of LDPC coset codes.


title: Fast generation of random connected graphs with prescribed degrees

abstract: We address here the problem of generating random graphs uniformly from the set of simple connected graphs having a prescribed degree sequence. Our goal is to provide an algorithm designed for practical use both because of its ability to generate very large graphs (efficiency) and because it is easy to implement (simplicity). We focus on a family of heuristics for which we prove optimality conditions, and show how this optimality can be reached in practice. We then propose a different approach, specifically designed for typical real-world degree distributions, which outperforms the first one. Assuming a conjecture which we state and argue rigorously, we finally obtain an log-linear algorithm, which, in spite of being very simple, improves the best known complexity.


title: The Self-Organization of Speech Sounds

abstract: The speech code is a vehicle of language: it defines a set of forms used by a community to carry information. Such a code is necessary to support the linguistic interactions that allow humans to communicate. How then may a speech code be formed prior to the existence of linguistic interactions? Moreover, the human speech code is discrete and compositional, shared by all the individuals of a community but different across communities, and phoneme inventories are characterized by statistical regularities. How can a speech code with these properties form? We try to approach these questions in the paper, using the "methodology of the artificial". We build a society of artificial agents, and detail a mechanism that shows the formation of a discrete speech code without pre-supposing the existence of linguistic capacities or of coordinated interactions. The mechanism is based on a low-level model of sensory-motor interactions. We show that the integration of certain very simple and non language-specific neural devices leads to the formation of a speech code that has properties similar to the human speech code. This result relies on the self-organizing properties of a generic coupling between perception and production within agents, and on the interactions between agents. The artificial system helps us to develop better intuitions on how speech might have appeared, by showing how self-organization might have helped natural selection to find speech.


title: Self-Replicating Strands that Self-Assemble into User-Specified Meshes

abstract: It has been argued that a central objective of nanotechnology is to make products inexpensively, and that self-replication is an effective approach to very low-cost manufacturing. The research presented here is intended to be a step towards this vision. In previous work (JohnnyVon 1.0), we simulated machines that bonded together to form self-replicating strands. There were two types of machines (called types 0 and 1), which enabled strands to encode arbitrary bit strings. However, the information encoded in the strands had no functional role in the simulation. The information was replicated without being interpreted, which was a significant limitation for potential manufacturing applications. In the current work (JohnnyVon 2.0), the information in a strand is interpreted as instructions for assembling a polygonal mesh. There are now four types of machines and the information encoded in a strand determines how it folds. A strand may be in an unfolded state, in which the bonds are straight (although they flex slightly due to virtual forces acting on the machines), or in a folded state, in which the bond angles depend on the types of machines. By choosing the sequence of machine types in a strand, the user can specify a variety of polygonal shapes. A simulation typically begins with an initial unfolded seed strand in a soup of unbonded machines. The seed strand replicates by bonding with free machines in the soup. The child strands fold into the encoded polygonal shape, and then the polygons drift together and bond to form a mesh. We demonstrate that a variety of polygonal meshes can be manufactured in the simulation, by simply changing the sequence of machine types in the seed.


title: Towards a Systematic Account of Different Semantics for Logic Programs

abstract: In [Hitzler and Wendt 2002, 2005], a new methodology has been proposed which allows to derive uniform characterizations of different declarative semantics for logic programs with negation. One result from this work is that the well-founded semantics can formally be understood as a stratified version of the Fitting (or Kripke-Kleene) semantics. The constructions leading to this result, however, show a certain asymmetry which is not readily understood. We will study this situation here with the result that we will obtain a coherent picture of relations between different semantics for normal logic programs.


title: The QuarkNet/Grid Collaborative Learning e-Lab

abstract: We describe a case study that uses grid computing techniques to support the collaborative learning of high school students investigating cosmic rays. Students gather and upload science data to our e-Lab portal. They explore those data using techniques from the GriPhyN collaboration. These techniques include virtual data transformations, workflows, metadata cataloging and indexing, data product provenance and persistence, as well as job planners. Students use web browsers and a custom interface that extends the GriPhyN Chiron portal to perform all of these tasks. They share results in the form of online posters and ask each other questions in this asynchronous environment. Students can discover and extend the research of other students, modeling the processes of modern large-scale scientific collaborations. Also, the e-Lab portal provides tools for teachers to guide student work throughout an investigation. http://quarknet.uchicago.edu/elab/cosmic


title: UNICORE - From Project Results to Production Grids

abstract: The UNICORE Grid-technology provides a seamless, secure and intuitive access to distributed Grid resources. In this paper we present the recent evolution from project results to production Grids. At the beginning UNICORE was developed as a prototype software in two projects funded by the German research ministry (BMBF). Over the following years, in various European-funded projects, UNICORE evolved to a full-grown and well-tested Grid middleware system, which today is used in daily production at many supercomputing centers worldwide. Beyond this production usage, the UNICORE technology serves as a solid basis in many European and International research projects, which use existing UNICORE components to implement advanced features, high level services, and support for applications from a growing range of domains. In order to foster these ongoing developments, UNICORE is available as open source under BSD licence at SourceForge, where new releases are published on a regular basis. This paper is a review of the UNICORE achievements so far and gives a glimpse on the UNICORE roadmap.


title: An Audit Logic for Accountability

abstract: We describe and implement a policy language. In our system, agents can distribute data along with usage policies in a decentralized architecture. Our language supports the specification of conditions and obligations, and also the possibility to refine policies. In our framework, the compliance with usage policies is not actively enforced. However, agents are accountable for their actions, and may be audited by an authority requiring justifications.


title: Divergence-free Wavelets for Navier-Stokes

abstract: In this paper, we investigate the use of compactly supported divergence-free wavelets for the representation of the Navier-Stokes solution. After reminding the theoretical construction of divergence-free wavelet vectors, we present in detail the bases and corresponding fast algorithms for 2D and 3D incompressible flows. In order to compute the nonlinear term, we propose a new method which provides in practice with the Hodge decomposition of any flow: this decomposition enables us to separate the incompressible part of the flow from its orthogonal complement, which corresponds to the gradient component of the flow. Finally we show numerical tests to validate our approach.


title: Online Permutation Routing in Partitioned Optical Passive Star Networks

abstract: This paper establishes the state of the art in both deterministic and randomized online permutation routing in the POPS network. Indeed, we show that any permutation can be routed online on a POPS network either with $O(\frac{d}{g}\log g)$ deterministic slots, or, with high probability, with $5c\lceil d/g\rceil+o(d/g)+O(\log\log g)$ randomized slots, where constant $c=\exp (1+e^{-1})\approx 3.927$. When $d=\Theta(g)$, that we claim to be the "interesting" case, the randomized algorithm is exponentially faster than any other algorithm in the literature, both deterministic and randomized ones. This is true in practice as well. Indeed, experiments show that it outperforms its rivals even starting from as small a network as a POPS(2,2), and the gap grows exponentially with the size of the network. We can also show that, under proper hypothesis, no deterministic algorithm can asymptotically match its performance.


title: Coalition Formation: Concessions, Task Relationships and Complexity Reduction

abstract: Solutions to the coalition formation problem commonly assume agent rationality and, correspondingly, utility maximization. This in turn may prevent agents from making compromises. As shown in recent studies, compromise may facilitate coalition formation and increase agent utilities. In this study we leverage on those new results. We devise a novel coalition formation mechanism that enhances compromise. Our mechanism can utilize information on task dependencies to reduce formation complexity. Further, it works well with both cardinal and ordinal task values. Via experiments we show that the use of the suggested compromise-based coalition formation mechanism provides significant savings in the computation and communication complexity of coalition formation. Our results also show that when information on task dependencies is used, the complexity of coalition formation is further reduced. We demonstrate successful use of the mechanism for collaborative information filtering, where agents combine linguistic rules to analyze documents' contents.


title: Gradient Vector Flow Models for Boundary Extraction in 2D Images

abstract: The Gradient Vector Flow (GVF) is a vector diffusion approach based on Partial Differential Equations (PDEs). This method has been applied together with snake models for boundary extraction medical images segmentation. The key idea is to use a diffusion-reaction PDE to generate a new external force field that makes snake models less sensitivity to initialization as well as improves the snake's ability to move into boundary concavities. In this paper, we firstly review basic results about convergence and numerical analysis of usual GVF schemes. We point out that GVF presents numerical problems due to discontinuities image intensity. This point is considered from a practical viewpoint from which the GVF parameters must follow a relationship in order to improve numerical convergence. Besides, we present an analytical analysis of the GVF dependency from the parameters values. Also, we observe that the method can be used for multiply connected domains by just imposing the suitable boundary condition. In the experimental results we verify these theoretical points and demonstrate the utility of GVF on a segmentation approach that we have developed based on snakes.


title: Property analysis of symmetric travelling salesman problem instances acquired through evolution

abstract: We show how an evolutionary algorithm can successfully be used to evolve a set of difficult to solve symmetric travelling salesman problem instances for two variants of the Lin-Kernighan algorithm. Then we analyse the instances in those sets to guide us towards deferring general knowledge about the efficiency of the two variants in relation to structural properties of the symmetric travelling sale sman problem.