OpenRaiser/Intern-Atlas huggingface dataset:
Embedding Defeasible Logic into Logic Programming
Venue: arXiv cs.LO 2005
Year: 2005

Defeasible reasoning is a simple but efficient approach to nonmonotonic reasoning that has recently attracted considerable interest and that has found various applications. Defeasible logic and its variants are an important family of defeasible reasoning methods. So far no relationship has been established between defeasible logic and mainstream nonmonotonic reasoning approaches. In this paper we establish close links to known semantics of logic programs. In particular, we give a translation of a defeasible theory D into a meta-program P(D). We show that under a condition of decisiveness, the defeasible consequences of D correspond exactly to the sceptical conclusions of P(D) under the stable model semantics. Without decisiveness, the result holds only in one direction (all defeasible consequences of D are included in all stable models of P(D)). If we wish a complete embedding for the general case, we need to use the Kunen semantics of P(D), instead.
Improved Upper Bounds on Stopping Redundancy
Venue: arXiv cs.IT 2005
Year: 2005

Let C be a linear code with length n and minimum distance d. The stopping redundancy of C is defined as the minimum number of rows in a parity-check matrix for C such that the smallest stopping sets in the corresponding Tanner graph have size d. We derive new upper bounds on the stopping redundancy of linear codes in general, and of maximum distance separable (MDS) codes specifically, and show how they improve upon previously known results. For MDS codes, the new bounds are found by upper bounding the stopping redundancy by a combinatorial quantity closely related to Turan numbers. (The Turan number, T(v,k,t), is the smallest number of t-subsets of a v-set, such that every k-subset of the v-set contains at least one of the t-subsets.) We further show that the stopping redundancy of MDS codes is T(n,d-1,d-2)(1+O(n^{-1})) for fixed d, and is at most T(n,d-1,d-2)(3+O(n^{-1})) for fixed code dimension k=n-d+1. For d=3,4, we prove that the stopping redundancy of MDS codes is equal to T(n,d-1,d-2), for which exact formulas are known. For d=5, we show that the stopping redundancy of MDS codes is either T(n,4,3) or T(n,4,3)+1.
Truly On-The-Fly LTL Model Checking
Venue: arXiv cs.LO 2005
Year: 2005

We propose a novel algorithm for automata-based LTL model checking that interleaves the construction of the generalized Büchi automaton for the negation of the formula and the emptiness check. Our algorithm first converts the LTL formula into a linear weak alternating automaton; configurations of the alternating automaton correspond to the locations of a generalized Büchi automaton, and a variant of Tarjan's algorithm is used to decide the existence of an accepting run of the product of the transition system and the automaton. Because we avoid an explicit construction of the Büchi automaton, our approach can yield significant improvements in runtime and memory, for large LTL formulas. The algorithm has been implemented within the SPIN model checker, and we present experimental results for some benchmark examples.
Analytic performance comparison of routing protocols in master-slave PLC networks
Venue: arXiv cs.NI 2005
Year: 2005

In the wide area master-slave PLC (powerline communication) system, the source node cannot reach the destination node without packet relay. Due to the time-variable attenuation in the powerline, the communication distance cannot be defined. Two kind of dynamic repeater algorithms are developed, dynamic source routing and flooding based routing. In this paper, we use analytic approach to compare the performance of those two routing protocols. We give formulas to calculate the average duration of a polling cycle for each protocols. Then we present simulation results to bolster the results of our analysis. We use three metrics, which are bandwidth consumed for routing signaling, normalized routing load and average duration of a polling cycle to evaluate those routing protocols.
An Agent-based Manufacturing Management System for Production and Logistics within Cross-Company Regional and National Production Networks
Venue: arXiv cs.RO 2005
Year: 2005

The goal is the development of a simultaneous, dynamic, technological as well as logistical real-time planning and an organizational control of the production by the production units themselves, working in the production network under the use of Multi-Agent-Technology. The design of the multi-agent-based manufacturing management system, the models of the single agents, algorithms for the agent-based, decentralized dispatching of orders, strategies and data management concepts as well as their integration into the SCM, basing on the solution described, will be explained in the following. Keywords: production engineering and management, dynamic manufacturing planning and control, multi-agentsystems (MAS), supply-chain-management (SCM), e-manufacturing
Gradient Based Routing in Wireless Sensor Networks: a Mixed Strategy
Venue: arXiv cs.DC 2005
Year: 2005

We show how recent theoretical advances for data-propagation in Wireless Sensor Networks (WSNs) can be combined to improve gradient-based routing (GBR) in Wireless Sensor Networks. We propose a mixed-strategy of direct transmission and multi-hop propagation of data which improves the lifespan of WSNs by reaching better energy-load-balancing amongst sensor nodes.
Benefits of InterSite Pre-Processing and Clustering Methods in E-Commerce Domain
Venue: arXiv cs.DB 2005
Year: 2005

This paper presents our preprocessing and clustering analysis on the clickstream dataset proposed for the ECMLPKDD 2005 Discovery Challenge. The main contributions of this article are double. First, after presenting the clickstream dataset, we show how we build a rich data warehouse based an advanced preprocesing. We take into account the intersite aspects in the given ecommerce domain, which offers an interesting data structuration. A preliminary statistical analysis based on time period clickstreams is given, emphasing the importance of intersite user visits in such a context. Secondly, we describe our crossed-clustering method which is applied on data generated from our data warehouse. Our preliminary results are interesting and promising illustrating the benefits of our WUM methods, even if more investigations are needed on the same dataset.
Parameter Estimation of Hidden Diffusion Processes: Particle Filter vs. Modified Baum-Welch Algorithm
Venue: arXiv cs.DS 2005
Year: 2005

We propose a new method for the estimation of parameters of hidden diffusion processes. Based on parametrization of the transition matrix, the Baum-Welch algorithm is improved. The algorithm is compared to the particle filter in application to the noisy periodic systems. It is shown that the modified Baum-Welch algorithm is capable of estimating the system parameters with better accuracy than particle filters.
Capacity-Achieving Ensembles of Accumulate-Repeat-Accumulate Codes for the Erasure Channel with Bounded Complexity
Venue: arXiv cs.IT 2005
Year: 2005

The paper introduces ensembles of accumulate-repeat-accumulate (ARA) codes which asymptotically achieve capacity on the binary erasure channel (BEC) with {\em bounded complexity}, per information bit, of encoding and decoding. It also introduces symmetry properties which play a central role in the construction of capacity-achieving ensembles for the BEC with bounded complexity. The results here improve on the tradeoff between performance and complexity provided by previous constructions of capacity-achieving ensembles of codes defined on graphs. The superiority of ARA codes with moderate to large block length is exemplified by computer simulations which compare their performance with those of previously reported capacity-achieving ensembles of LDPC and IRA codes. The ARA codes also have the advantage of being systematic.
Amazing geometry of genetic space or are genetic algorithms convergent?
Venue: arXiv cs.NE 2005
Year: 2005

There is no proof yet of convergence of Genetic Algorithms. We do not supply it too. Instead, we present some thoughts and arguments to convince the Reader, that Genetic Algorithms are essentially bound for success. For this purpose, we consider only the crossover operators, single- or multiple-point, together with selection procedure. We also give a proof that the soft selection is superior to other selection schemes.
The Poster Session of SSS 2005
Venue: arXiv cs.DC 2005
Year: 2005

This technical report documents the poster session of SSS 2005, the Symposium on Self-Stabilizing Systems published by Springer as LNCS volume 3764. The poster session included five presentations. Two of these presentations are summarized in brief abstracts contained in this technical report.
Fat Tailed Distributions in Catastrophe Prediction
Venue: arXiv cs.OH 2005
Year: 2005

This paper discusses the use of fat-tailed distributions in catastrophe prediction as opposed to the more common use of the Normal Distribution.
Approximately universal optimality over several dynamic and non-dynamic cooperative diversity schemes for wireless networks
Venue: arXiv cs.IT 2005
Year: 2005

In this work we explicitly provide the first ever optimal, with respect to the Zheng-Tse diversity multiplexing gain (D-MG) tradeoff, cooperative diversity schemes for wireless relay networks. The schemes are based on variants of perfect space-time codes and are optimal for any number of users and all statistically symmetric (and in some cases, asymmetric) fading distributions. We deduce that, with respect to the D-MG tradeoff, channel knowledge at the intermediate relays and infinite delay are unnecessary. We also show that the non-dynamic selection decode and forward strategy, the non-dynamic amplify and forward, the non-dynamic receive and forward, the dynamic amplify and forward and the dynamic receive and forward cooperative diversity strategies allow for exactly the same D-MG optimal performance.
New model for rigorous analysis of LT-codes
Venue: arXiv cs.IT 2005
Year: 2005

We present a new model for LT codes which simplifies the analysis of the error probability of decoding by belief propagation. For any given degree distribution, we provide the first rigorous expression for the limiting error probability as the length of the code goes to infinity via recent results in random hypergraphs [Darling-Norris 2005]. For a code of finite length, we provide an algorithm for computing the probability of error of the decoder. This algorithm improves the one of [Karp-Luby-Shokrollahi 2004] by a linear factor.
A fast algorithm for determining the linear complexity of periodic sequences
Venue: arXiv cs.CR 2005
Year: 2005

A fast algorithm is presented for determining the linear complexity and the minimal polynomial of periodic sequences over GF(q) with period q n p m, where p is a prime, q is a prime and a primitive root modulo p2. The algorithm presented here generalizes both the algorithm in [4] where the period of a sequence over GF(q) is p m and the algorithm in [5] where the period of a binary sequence is 2 n p m . When m=0, the algorithm simplifies the generalized Games-Chan algorithm.
Random Walks with Anti-Correlated Steps
Venue: arXiv cs.DM 2005
Year: 2005

We conjecture the expected value of random walks with anti-correlated steps to be exactly 1. We support this conjecture with 2 plausibility arguments and experimental data. The experimental analysis includes the computation of the expected values of random walks for steps up to 22. The result shows the expected value asymptotically converging to 1.
Existence of finite test-sets for k-power-freeness of uniform morphisms
Venue: arXiv cs.DM 2005
Year: 2005

A challenging problem is to find an algorithm to decide whether a morphism is k-power-free. We provide such an algorithm when k >= 3 for uniform morphisms showing that in such a case, contrarily to the general case, there exist finite test-sets for k-power-freeness.
PURRS: Towards Computer Algebra Support for Fully Automatic Worst-Case Complexity Analysis
Venue: arXiv cs.MS 2005
Year: 2005

Fully automatic worst-case complexity analysis has a number of applications in computer-assisted program manipulation. A classical and powerful approach to complexity analysis consists in formally deriving, from the program syntax, a set of constraints expressing bounds on the resources required by the program, which are then solved, possibly applying safe approximations. In several interesting cases, these constraints take the form of recurrence relations. While techniques for solving recurrences are known and implemented in several computer algebra systems, these do not completely fulfill the needs of fully automatic complexity analysis: they only deal with a somewhat restricted class of recurrence relations, or sometimes require user intervention, or they are restricted to the computation of exact solutions that are often so complex to be unmanageable, and thus useless in practice. In this paper we briefly describe PURRS, a system and software library aimed at providing all the computer algebra services needed by applications performing or exploiting the results of worst-case complexity analyses. The capabilities of the system are illustrated by means of examples derived from the analysis of programs written in a domain-specific functional programming language for real-time embedded systems.
Evolino for recurrent support vector machines
Venue: arXiv cs.NE 2005
Year: 2005

Traditional Support Vector Machines (SVMs) need pre-wired finite time windows to predict and classify time series. They do not have an internal state necessary to deal with sequences involving arbitrary long-term dependencies. Here we introduce a new class of recurrent, truly sequential SVM-like devices with internal adaptive states, trained by a novel method called EVOlution of systems with KErnel-based outputs (Evoke), an instance of the recent Evolino class of methods. Evoke evolves recurrent neural networks to detect and represent temporal dependencies while using quadratic programming/support vector regression to produce precise outputs. Evoke is the first SVM-based mechanism learning to classify a context-sensitive language. It also outperforms recent state-of-the-art gradient-based recurrent neural networks (RNNs) on various time series prediction tasks.
"Going back to our roots": second generation biocomputing
Venue: arXiv cs.AI 2005
Year: 2005

Researchers in the field of biocomputing have, for many years, successfully "harvested and exploited" the natural world for inspiration in developing systems that are robust, adaptable and capable of generating novel and even "creative" solutions to human-defined problems. However, in this position paper we argue that the time has now come for a reassessment of how we exploit biology to generate new computational systems. Previous solutions (the "first generation" of biocomputing techniques), whilst reasonably effective, are crude analogues of actual biological systems. We believe that a new, inherently inter-disciplinary approach is needed for the development of the emerging "second generation" of bio-inspired methods. This new modus operandi will require much closer interaction between the engineering and life sciences communities, as well as a bidirectional flow of concepts, applications and expertise. We support our argument by examining, in this new light, three existing areas of biocomputing (genetic programming, artificial immune systems and evolvable hardware), as well as an emerging area (natural genetic engineering) which may provide useful pointers as to the way forward.
On Achievable Rates and Complexity of LDPC Codes for Parallel Channels: Information-Theoretic Bounds and Applications
Venue: arXiv cs.IT 2005
Year: 2005

The paper presents bounds on the achievable rates and the decoding complexity of low-density parity-check (LDPC) codes. It is assumed that the communication of these codes takes place over statistically independent parallel channels where these channels are memoryless, binary-input and output-symmetric (MBIOS). The bounds are applied to punctured LDPC codes. A diagram concludes our discussion by showing interconnections between the theorems in this paper and some previously reported results.
An invariant bayesian model selection principle for gaussian data in a sparse representation
Venue: arXiv cs.IT 2005
Year: 2005

We develop a code length principle which is invariant to the choice of parameterization on the model distributions. An invariant approximation formula for easy computation of the marginal distribution is provided for gaussian likelihood models. We provide invariant estimators of the model parameters and formulate conditions under which these estimators are essentially posteriori unbiased for gaussian models. An upper bound on the coarseness of discretization on the model parameters is deduced. We introduce a discrimination measure between probability distributions and use it to construct probability distributions on model classes. The total code length is shown to equal the NML code length of Rissanen to within an additive constant when choosing Jeffreys prior distribution on the model parameters together with a particular choice of prior distribution on the model classes. Our model selection principle is applied to a gaussian estimation problem for data in a wavelet representation and its performance is tested and compared to alternative wavelet-based estimation methods in numerical experiments
A Fixpoint Semantics of Event Systems with and without Fairness Assumptions
Venue: arXiv cs.LO 2005
Year: 2005

We present a fixpoint semantics of event systems. The semantics is presented in a general framework without concerns of fairness. Soundness and completeness of rules for deriving "leads-to" properties are proved in this general framework. The general framework is instantiated to minimal progress and weak fairness assumptions and similar results are obtained. We show the power of these results by deriving sufficient conditions for "leads-to" under minimal progress proving soundness of proof obligations without reasoning over state-traces.
Analyzing and Visualizing the Semantic Coverage of Wikipedia and Its Authors
Venue: arXiv cs.IR 2005
Year: 2005

This paper presents a novel analysis and visualization of English Wikipedia data. Our specific interest is the analysis of basic statistics, the identification of the semantic structure and age of the categories in this free online encyclopedia, and the content coverage of its highly productive authors. The paper starts with an introduction of Wikipedia and a review of related work. We then introduce a suite of measures and approaches to analyze and map the semantic structure of Wikipedia. The results show that co-occurrences of categories within individual articles have a power-law distribution, and when mapped reveal the nicely clustered semantic structure of Wikipedia. The results also reveal the content coverage of the article's authors, although the roles these authors play are as varied as the authors themselves. We conclude with a discussion of major results and planned future work.
Reversible CAM Processor Modeled After Quantum Computer Behavior
Venue: arXiv cs.AR 2005
Year: 2005

Proposed below is a reversible digital computer modeled after the natural behavior of a quantum system. Using approaches usually reserved for idealized quantum computers, the Reversible CAM, or State Vector Parallel (RSVP) processor can easily find keywords in an unstructured database (that is, it can solve a needle in a haystack problem). The RSVP processor efficiently solves a SAT (Satisfiability of Boolean Formulae) problem; also it can aid in the solution of a GP (Global Properties of Truth Table) problem. The power delay product of the RSVP processor is exponentially lower than that of a standard CAM programmed to perform similar operations.
The concept of strong and weak virtual reality
Venue: arXiv cs.LO 2006
Year: 2006

We approach the virtual reality phenomenon by studying its relationship to set theory, and we investigate the case where this is done using the wellfoundedness property of sets. Our hypothesis is that non-wellfounded sets (hypersets) give rise to a different quality of virtual reality than do familiar wellfounded sets. We initially provide an alternative approach to virtual reality based on Sommerhoff's idea of first and second order self-awareness; both categories of self-awareness are considered as necessary conditions for consciousness in terms of higher cognitive functions. We then introduce a representation of first and second order self-awareness through sets, and assume that these sets, which we call events, originally form a collection of wellfounded sets. Strong virtual reality characterizes virtual reality environments which have the limited capacity to create only events associated with wellfounded sets. In contrast, the more general concept of weak virtual reality characterizes collections of virtual reality mediated events altogether forming an entirety larger than any collection of wellfounded sets. By giving reference to Aczel's hyperset theory we indicate that this definition is not empty, because hypersets encompass wellfounded sets already. Moreover, we argue that weak virtual reality could be realized in human history through continued progress in computer technology. Finally, we reformulate our characterization into a more general framework, and use Baltag's Structural Theory of Sets (STS) to show that within this general hyperset theory Sommerhoff's first and second order self-awareness as well as both concepts of virtual reality admit a consistent mathematical representation.
Capacity and Random-Coding Exponents for Channel Coding with Side Information
Venue: arXiv cs.IT 2006
Year: 2006

Capacity formulas and random-coding exponents are derived for a generalized family of Gel'fand-Pinsker coding problems. These exponents yield asymptotic upper bounds on the achievable log probability of error. In our model, information is to be reliably transmitted through a noisy channel with finite input and output alphabets and random state sequence, and the channel is selected by a hypothetical adversary. Partial information about the state sequence is available to the encoder, adversary, and decoder. The design of the transmitter is subject to a cost constraint. Two families of channels are considered: 1) compound discrete memoryless channels (CDMC), and 2) channels with arbitrary memory, subject to an additive cost constraint, or more generally to a hard constraint on the conditional type of the channel output given the input. Both problems are closely connected. The random-coding exponent is achieved using a stacked binning scheme and a maximum penalized mutual information decoder, which may be thought of as an empirical generalized Maximum a Posteriori decoder. For channels with arbitrary memory, the random-coding exponents are larger than their CDMC counterparts. Applications of this study include watermarking, data hiding, communication in presence of partially known interferers, and problems such as broadcast channels, all of which involve the fundamental idea of binning.
Zeno machines and hypercomputation
Venue: arXiv cs.CC 2006
Year: 2006

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