OpenRaiser/Intern-Atlas huggingface dataset:
On the Feedback Capacity of Power Constrained Gaussian Noise Channels with Memory
Venue: arXiv cs.IT 2007
Year: 2007

For a stationary additive Gaussian-noise channel with a rational noise power spectrum of a finite-order $L$, we derive two new results for the feedback capacity under an average channel input power constraint. First, we show that a very simple feedback-dependent Gauss-Markov source achieves the feedback capacity, and that Kalman-Bucy filtering is optimal for processing the feedback. Based on these results, we develop a new method for optimizing the channel inputs for achieving the Cover-Pombra block-length-$n$ feedback capacity by using a dynamic programming approach that decomposes the computation into $n$ sequentially identical optimization problems where each stage involves optimizing $O(L^2)$ variables. Second, we derive the explicit maximal information rate for stationary feedback-dependent sources. In general, evaluating the maximal information rate for stationary sources requires solving only a few equations by simple non-linear programming. For first-order autoregressive and/or moving average (ARMA) noise channels, this optimization admits a closed form maximal information rate formula. The maximal information rate for stationary sources is a lower bound on the feedback capacity, and it equals the feedback capacity if the long-standing conjecture, that stationary sources achieve the feedback capacity, holds.
Why is a new Journal of Informetrics needed?
Venue: arXiv cs.DL 2007
Year: 2007

In our study we analysed 3.889 records which were indexed in the Library and Information Science Abstracts (LISA) database in the research field of informetrics. We can show the core journals of the field via a Bradford (power law) distribution and corroborate on the basis of the restricted LISA data set that it was the appropriate time to found a new specialized journal dedicated to informetrics. According to Bradford's Law of scattering (pure quantitative calculation), Egghe's Journal of Informetrics (JOI) first issue to appear in 2007, comes most probable at the right time.
A Delta Debugger for ILP Query Execution
Venue: arXiv cs.PL 2007
Year: 2007

Because query execution is the most crucial part of Inductive Logic Programming (ILP) algorithms, a lot of effort is invested in developing faster execution mechanisms. These execution mechanisms typically have a low-level implementation, making them hard to debug. Moreover, other factors such as the complexity of the problems handled by ILP algorithms and size of the code base of ILP data mining systems make debugging at this level a very difficult job. In this work, we present the trace-based debugging approach currently used in the development of new execution mechanisms in hipP, the engine underlying the ACE Data Mining system. This debugger uses the delta debugging algorithm to automatically reduce the total time needed to expose bugs in ILP execution, thus making manual debugging step much lighter.
A Web-based Tool Combining Different Type Analyses
Venue: arXiv cs.PL 2007
Year: 2007

There are various kinds of type analysis of logic programs. These include for example inference of types that describe an over-approximation of the success set of a program, inference of well-typings, and abstractions based on given types. Analyses can be descriptive or prescriptive or a mixture of both, and they can be goal-dependent or goal-independent. We describe a prototype tool that can be accessed from a web browser, allowing various type analyses to be run. The first goal of the tool is to allow the analysis results to be examined conveniently by clicking on points in the original program clauses, and to highlight ill-typed program constructs, empty types or other type anomalies. Secondly the tool allows combination of the various styles of analysis. For example, a descriptive regular type can be automatically inferred for a given program, and then that type can be used to generate the minimal "domain model" of the program with respect to the corresponding pre-interpretation, which can give more precise information than the original descriptive type.
(l,s)-Extension of Linear Codes
Venue: arXiv cs.IT 2007
Year: 2007

We construct new linear codes with high minimum distance d. In at least 12 cases these codes improve the minimum distance of the previously known best linear codes for fixed parameters n,k. Among these new codes there is an optimal ternary [88,8,54] code. We develop an algorithm, which starts with already good codes C, i.e. codes with high minimum distance d for given length n and dimension k over the field GF(q). The algorithm is based on the newly defined (l,s)-extension. This is a generalization of the well-known method of adding a parity bit in the case of a binary linear code of odd minimum weight. (l,s)-extension tries to extend the generator matrix of C by adding l columns with the property that at least s of the l letters added to each of the codewords of minimum weight in C are different from 0. If one finds such columns the minimum distance of the extended code is d+s provided that the second smallest weight in C was at least d+s. The question whether such columns exist can be settled using a Diophantine system of equations.
On factorisation forests
Venue: arXiv cs.LO 2007
Year: 2007

The theorem of factorisation forests shows the existence of nested factorisations -- a la Ramsey -- for finite words. This theorem has important applications in semigroup theory, and beyond. The purpose of this paper is to illustrate the importance of this approach in the context of automata over infinite words and trees. We extend the theorem of factorisation forest in two directions: we show that it is still valid for any word indexed by a linear ordering; and we show that it admits a deterministic variant for words indexed by well-orderings. A byproduct of this work is also an improvement on the known bounds for the original result. We apply the first variant for giving a simplified proof of the closure under complementation of rational sets of words indexed by countable scattered linear orderings. We apply the second variant in the analysis of monadic second-order logic over trees, yielding new results on monadic interpretations over trees. Consequences of it are new caracterisations of prefix-recognizable structures and of the Caucal hierarchy.
Browser-based distributed evolutionary computation: performance and scaling behavior
Venue: arXiv cs.DC 2007
Year: 2007

The challenge of ad-hoc computing is to find the way of taking advantage of spare cycles in an efficient way that takes into account all capabilities of the devices and interconnections available to them. In this paper we explore distributed evolutionary computation based on the Ruby on Rails framework, which overlays a Model-View-Controller on evolutionary computation. It allows anybody with a web browser (that is, mostly everybody connected to the Internet) to participate in an evolutionary computation experiment. Using a straightforward farming model, we consider different factors, such as the size of the population used. We are mostly interested in how they impact on performance, but also the scaling behavior when a non-trivial number of computers is applied to the problem. Experiments show the impact of different packet sizes on performance, as well as a quite limited scaling behavior, due to the characteristics of the server. Several solutions for that problem are proposed.
Feasible Depth
Venue: arXiv cs.CC 2007
Year: 2007

This paper introduces two complexity-theoretic formulations of Bennett's logical depth: finite-state depth and polynomial-time depth. It is shown that for both formulations, trivial and random infinite sequences are shallow, and a slow growth law holds, implying that deep sequences cannot be created easily from shallow sequences. Furthermore, the E analogue of the halting language is shown to be polynomial-time deep, by proving a more general result: every language to which a nonnegligible subset of E can be reduced in uniform exponential time is polynomial-time deep.
Certifying controls and systems software
Venue: arXiv cs.SE 2007
Year: 2007

Software system certification presents itself with many challenges, including the necessity to certify the system at the level of functional requirements, code and binary levels, the need to chase down run-time errors, and the need for proving timing properties of the eventual, compiled system. This paper illustrates possible approaches for certifying code that arises from control systems requirements as far as stability properties are concerned. The relative simplicity of the certification process should encourage the development of systematic procedures for certifying control system codes for more complex environments.
Predicate Abstraction with Under-approximation Refinement
Venue: arXiv cs.GT 2007
Year: 2007

We propose an abstraction-based model checking method which relies on refinement of an under-approximation of the feasible behaviors of the system under analysis. The method preserves errors to safety properties, since all analyzed behaviors are feasible by definition. The method does not require an abstract transition relation to be generated, but instead executes the concrete transitions while storing abstract versions of the concrete states, as specified by a set of abstraction predicates. For each explored transition the method checks, with the help of a theorem prover, whether there is any loss of precision introduced by abstraction. The results of these checks are used to decide termination or to refine the abstraction by generating new abstraction predicates. If the (possibly infinite) concrete system under analysis has a finite bisimulation quotient, then the method is guaranteed to eventually explore an equivalent finite bisimilar structure. We illustrate the application of the approach for checking concurrent programs.
A Generic Analysis Environment for Curry Programs
Venue: arXiv cs.PL 2007
Year: 2007

We present CurryBrowser, a generic analysis environment for the declarative multi-paradigm language Curry. CurryBrowser supports browsing through the program code of an application written in Curry, i.e., the main module and all directly or indirectly imported modules. Each module can be shown in different formats (e.g., source code, interface, intermediate code) and, inside each module, various properties of functions defined in this module can be analyzed. In order to support the integration of various program analyses, CurryBrowser has a generic interface to connect local and global analyses implemented in Curry. CurryBrowser is completely implemented in Curry using libraries for GUI programming and meta-programming.
Time- and Space-Efficient Evaluation of Some Hypergeometric Constants
Venue: arXiv cs.SC 2007
Year: 2007

The currently best known algorithms for the numerical evaluation of hypergeometric constants such as $ζ(3)$ to $d$ decimal digits have time complexity $O(M(d) \log^2 d)$ and space complexity of $O(d \log d)$ or $O(d)$. Following work from Cheng, Gergel, Kim and Zima, we present a new algorithm with the same asymptotic complexity, but more efficient in practice. Our implementation of this algorithm improves slightly over existing programs for the computation of $π$, and we announce a new record of 2 billion digits for $ζ(3)$.
Queues Are Databases
Venue: arXiv cs.DB 2007
Year: 2007

Message-oriented-middleware (MOM) has become an small industry. MOM offers queued transaction processing as an advance over pure client-server transaction processing. This note makes four points: Queued transaction processing is less general than direct transaction processing. Queued systems are built on top of direct systems. You cannot build a direct system atop a queued system. It is difficult to build direct, conversational, or distributed transactions atop a queued system. Queues are interesting databases with interesting concurrency control. It is best to build these mechanisms into a standard database system so other applications can use these interesting features. Queue systems need DBMS functionality. Queues need security, configuration, performance monitoring, recovery, and reorganization utilities. Database systems already have these features. A full-function MOM system duplicates these database features. Queue managers are simple TP-monitors managing server pools driven by queues. Database systems are encompassing many server pool features as they evolve to TP-lite systems.
A Measure of Transaction Processing 20 Years Later
Venue: arXiv cs.DB 2007
Year: 2007

This provides a retrospective of the paper "A Measure of Transaction Processing" published in 1985. It shows that transaction processing peak performance and price-peformance have improved about 100,000x respectively and that sort/sequential performance has approximately doubled each year (so a million fold improvement) even though processor performance plateaued in 1995.
Petascale Computational Systems
Venue: arXiv cs.DB 2007
Year: 2007

Computational science is changing to be data intensive. Super-Computers must be balanced systems; not just CPU farms but also petascale IO and networking arrays. Anyone building CyberInfrastructure should allocate resources to support a balanced Tier-1 through Tier-3 design.
The Zones Algorithm for Finding Points-Near-a-Point or Cross-Matching Spatial Datasets
Venue: arXiv cs.DB 2007
Year: 2007

Zones index an N-dimensional Euclidian or metric space to efficiently support points-near-a-point queries either within a dataset or between two datasets. The approach uses relational algebra and the B-Tree mechanism found in almost all relational database systems. Hence, the Zones Algorithm gives a portable-relational implementation of points-near-point, spatial cross-match, and self-match queries. This article corrects some mistakes in an earlier article we wrote on the Zones Algorithm and describes some algorithmic improvements. The Appendix includes an implementation of point-near-point, self-match, and cross-match using the USGS city and stream gauge database.
SkyServer Traffic Report - The First Five Years
Venue: arXiv cs.DB 2007
Year: 2007

The SkyServer is an Internet portal to the Sloan Digital Sky Survey Catalog Archive Server. From 2001 to 2006, there were a million visitors in 3 million sessions generating 170 million Web hits, 16 million ad-hoc SQL queries, and 62 million page views. The site currently averages 35 thousand visitors and 400 thousand sessions per month. The Web and SQL logs are public. We analyzed traffic and sessions by duration, usage pattern, data product, and client type (mortal or bot) over time. The analysis shows (1) the site's popularity, (2) the educational website that delivered nearly fifty thousand hours of interactive instruction, (3) the relative use of interactive, programmatic, and batch-local access, (4) the success of offering ad-hoc SQL, personal database, and batch job access to scientists as part of the data publication, (5) the continuing interest in "old" datasets, (6) the usage of SQL constructs, and (7) a novel approach of using the corpus of correct SQL queries to suggest similar but correct statements when a user presents an incorrect SQL statement.
Measuring Cognitive Activities in Software Engineering
Venue: arXiv cs.HC 2007
Year: 2007

This paper presents an approach to the study of cognitive activities in collaborative software development. This approach has been developed by a multidisciplinary team made up of software engineers and cognitive psychologists. The basis of this approach is to improve our understanding of software development by observing professionals at work. The goal is to derive lines of conduct or good practices based on observations and analyses of the processes that are naturally used by software engineers. The strategy involved is derived from a standard approach in cognitive science. It is based on the videotaping of the activities of software engineers, transcription of the videos, coding of the transcription, defining categories from the coded episodes and defining cognitive behaviors or dialogs from the categories. This project presents two original contributions that make this approach generic in software engineering. The first contribution is the introduction of a formal hierarchical coding scheme, which will enable comparison of various types of observations. The second is the merging of psychological and statistical analysis approaches to build a cognitive model. The details of this new approach are illustrated with the initial data obtained from the analysis of technical review meetings.
A canonical form for some piecewise defined functions
Venue: arXiv cs.SC 2007
Year: 2007

We define a canonical form for piecewise defined functions. We show that this has a wider range of application as well as better complexity properties than previous work.
New Models for the Correlation in Sensor Data
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, we propose two new models of spatial correlations in sensor data in a data-gathering sensor network. A particular property of these models is that if a sensor node knows in \textit{how many} bits it needs to transmit its data, then it also knows \textit{which} bits of its data it needs to transmit.
Evolutionary Approaches to Minimizing Network Coding Resources
Venue: arXiv cs.NI 2007
Year: 2007

We wish to minimize the resources used for network coding while achieving the desired throughput in a multicast scenario. We employ evolutionary approaches, based on a genetic algorithm, that avoid the computational complexity that makes the problem NP-hard. Our experiments show great improvements over the sub-optimal solutions of prior methods. Our new algorithms improve over our previously proposed algorithm in three ways. First, whereas the previous algorithm can be applied only to acyclic networks, our new method works also with networks with cycles. Second, we enrich the set of components used in the genetic algorithm, which improves the performance. Third, we develop a novel distributed framework. Combining distributed random network coding with our distributed optimization yields a network coding protocol where the resources used for coding are optimized in the setup phase by running our evolutionary algorithm at each node of the network. We demonstrate the effectiveness of our approach by carrying out simulations on a number of different sets of network topologies.
Polygraphs for termination of left-linear term rewriting systems
Venue: arXiv cs.LO 2007
Year: 2007

We present a methodology for proving termination of left-linear term rewriting systems (TRSs) by using Albert Burroni's polygraphs, a kind of rewriting systems on algebraic circuits. We translate the considered TRS into a polygraph of minimal size whose termination is proven with a polygraphic interpretation, then we get back the property on the TRS. We recall Yves Lafont's general translation of TRSs into polygraphs and known links between their termination properties. We give several conditions on the original TRS, including being a first-order functional program, that ensure that we can reduce the size of the polygraphic translation. We also prove sufficient conditions on the polygraphic interpretations of a minimal translation to imply termination of the original TRS. Examples are given to compare this method with usual polynomial interpretations.
A Formal Model for Programming Wireless Sensor Networks
Venue: arXiv cs.DC 2007
Year: 2007

In this paper we present new developments in the expressiveness and in the theory of a Calculus for Sensor Networks (CSN). We combine a network layer of sensor devices with a local object model to describe sensor devices with state. The resulting calculus is quite small and yet very expressive. We also present a type system and a type invariance result for the calculus. These results provide the fundamental framework for the development of programming languages and run-time environments.
Finding Community Structure in Mega-scale Social Networks
Venue: arXiv cs.CY 2007
Year: 2007

Community analysis algorithm proposed by Clauset, Newman, and Moore (CNM algorithm) finds community structure in social networks. Unfortunately, CNM algorithm does not scale well and its use is practically limited to networks whose sizes are up to 500,000 nodes. The paper identifies that this inefficiency is caused from merging communities in unbalanced manner. The paper introduces three kinds of metrics (consolidation ratio) to control the process of community analysis trying to balance the sizes of the communities being merged. Three flavors of CNM algorithms are built incorporating those metrics. The proposed techniques are tested using data sets obtained from existing social networking service that hosts 5.5 million users. All the methods exhibit dramatic improvement of execution efficiency in comparison with the original CNM algorithm and shows high scalability. The fastest method processes a network with 1 million nodes in 5 minutes and a network with 4 million nodes in 35 minutes, respectively. Another one processes a network with 500,000 nodes in 50 minutes (7 times faster than the original algorithm), finds community structures that has improved modularity, and scales to a network with 5.5 million.
An Efficient Algorithm to Recognize Locally Equivalent Graphs in Non-Binary Case
Venue: arXiv cs.DS 2007
Year: 2007

Let $v$ be a vertex of a graph $G$. By the local complementation of $G$ at $v$ we mean to complement the subgraph induced by the neighbors of $v$. This operator can be generalized as follows. Assume that, each edge of $G$ has a label in the finite field $\mathbf{F}_q$. Let $(g_{ij})$ be set of labels ($g_{ij}$ is the label of edge $ij$). We define two types of operators. For the first one, let $v$ be a vertex of $G$ and $a\in \mathbf{F}_q$, and obtain the graph with labels $g'_{ij}=g_{ij}+ag_{vi}g_{vj}$. For the second, if $0\neq b\in \mathbf{F}_q$ the resulted graph is a graph with labels $g''_{vi}=bg_{vi}$ and $g''_{ij}=g_{ij}$, for $i,j$ unequal to $v$. It is clear that if the field is binary, the operators are just local complementations that we described. The problem of whether two graphs are equivalent under local complementations has been studied, \cite{bouchalg}. Here we consider the general case and assuming that $q$ is odd, present the first known efficient algorithm to verify whether two graphs are locally equivalent or not.
Sudo-Lyndon
Venue: arXiv cs.DM 2007
Year: 2007

Based on Lyndon words, a new Sudoku-like puzzle is presented and some relative theoretical questions are proposed.
Entropy vectors and network codes
Venue: arXiv cs.IT 2007
Year: 2007

We consider a network multicast example that relates the solvability of the multicast problem with the existence of an entropy function. As a result, we provide an alternative approach to the proving of the insufficiency of linear (and abelian) network codes and demonstrate the utility of non-Shannon inequalities to tighten outer bounds on network coding capacity regions.