OpenRaiser/Intern-Atlas huggingface dataset:
Lp Computable Functions and Fourier Series
Venue: arXiv cs.CC 2007
Year: 2007

This paper studies how well computable functions can be approximated by their Fourier series. To this end, we equip the space of Lp-computable functions (computable Lebesgue integrable functions) with a size notion, by introducing Lp-computable Baire categories. We show that Lp-computable Baire categories satisfy the following three basic properties. Singleton sets {f} (where f is Lp-computable) are meager, suitable infinite unions of meager sets are meager, and the whole space of Lp-computable functions is not meager. We give an alternative characterization of meager sets via Banach Mazur games. We study the convergence of Fourier series for Lp-computable functions and show that whereas for every p>1, the Fourier series of every Lp-computable function f converges to f in the Lp norm, the set of L1-computable functions whose Fourier series does not diverge almost everywhere is meager.
Higher-Order Termination: from Kruskal to Computability
Venue: arXiv cs.LO 2007
Year: 2007

Termination is a major question in both logic and computer science. In logic, termination is at the heart of proof theory where it is usually called strong normalization (of cut elimination). In computer science, termination has always been an important issue for showing programs correct. In the early days of logic, strong normalization was usually shown by assigning ordinals to expressions in such a way that eliminating a cut would yield an expression with a smaller ordinal. In the early days of verification, computer scientists used similar ideas, interpreting the arguments of a program call by a natural number, such as their size. Showing the size of the arguments to decrease for each recursive call gives a termination proof of the program, which is however rather weak since it can only yield quite small ordinals. In the sixties, Tait invented a new method for showing cut elimination of natural deduction, based on a predicate over the set of terms, such that the membership of an expression to the predicate implied the strong normalization property for that expression. The predicate being defined by induction on types, or even as a fixpoint, this method could yield much larger ordinals. Later generalized by Girard under the name of reducibility or computability candidates, it showed very effective in proving the strong normalization property of typed lambda-calculi...
Scanning and Sequential Decision Making for Multi-Dimensional Data - Part I: the Noiseless Case
Venue: arXiv cs.IT 2007
Year: 2007

We investigate the problem of scanning and prediction ("scandiction", for short) of multidimensional data arrays. This problem arises in several aspects of image and video processing, such as predictive coding, for example, where an image is compressed by coding the error sequence resulting from scandicting it. Thus, it is natural to ask what is the optimal method to scan and predict a given image, what is the resulting minimum prediction loss, and whether there exist specific scandiction schemes which are universal in some sense. Specifically, we investigate the following problems: First, modeling the data array as a random field, we wish to examine whether there exists a scandiction scheme which is independent of the field's distribution, yet asymptotically achieves the same performance as if this distribution was known. This question is answered in the affirmative for the set of all spatially stationary random fields and under mild conditions on the loss function. We then discuss the scenario where a non-optimal scanning order is used, yet accompanied by an optimal predictor, and derive bounds on the excess loss compared to optimal scanning and prediction. This paper is the first part of a two-part paper on sequential decision making for multi-dimensional data. It deals with clean, noiseless data arrays. The second part deals with noisy data arrays, namely, with the case where the decision maker observes only a noisy version of the data, yet it is judged with respect to the original, clean data.
A Typed Hybrid Description Logic Programming Language with Polymorphic Order-Sorted DL-Typed Unification for Semantic Web Type Systems
Venue: arXiv cs.AI 2007
Year: 2007

In this paper we elaborate on a specific application in the context of hybrid description logic programs (hybrid DLPs), namely description logic Semantic Web type systems (DL-types) which are used for term typing of LP rules based on a polymorphic, order-sorted, hybrid DL-typed unification as procedural semantics of hybrid DLPs. Using Semantic Web ontologies as type systems facilitates interchange of domain-independent rules over domain boundaries via dynamically typing and mapping of explicitly defined type ontologies.
Low Correlation Sequences over the QAM Constellation
Venue: arXiv cs.IT 2007
Year: 2007

This paper presents the first concerted look at low correlation sequence families over QAM constellations of size M^2=4^m and their potential applicability as spreading sequences in a CDMA setting. Five constructions are presented, and it is shown how such sequence families have the ability to transport a larger amount of data as well as enable variable-rate signalling on the reverse link. Canonical family CQ has period N, normalized maximum-correlation parameter theta_max bounded above by A sqrt(N), where 'A' ranges from 1.8 in the 16-QAM case to 3.0 for large M. In a CDMA setting, each user is enabled to transfer 2m bits of data per period of the spreading sequence which can be increased to 3m bits of data by halving the size of the sequence family. The technique used to construct CQ is easily extended to produce larger sequence families and an example is provided. Selected family SQ has a lower value of theta_max but permits only (m+1)-bit data modulation. The interleaved 16-QAM sequence family IQ has theta_max <= sqrt(2) sqrt(N) and supports 3-bit data modulation. The remaining two families are over a quadrature-PAM (Q-PAM) subset of size 2M of the M^2-QAM constellation. Family P has a lower value of theta_max in comparison with Family SQ, while still permitting (m+1)-bit data modulation. Interleaved family IP, over the 8-ary Q-PAM constellation, permits 3-bit data modulation and interestingly, achieves the Welch lower bound on theta_max.
Rapid Prototyping over IEEE 802.11
Venue: arXiv cs.NI 2007
Year: 2007

This paper introduces Prawn, a tool for prototyping communication protocols over IEEE 802.11 networks. Prawn allows researchers to conduct both functional assessment and performance evaluation as an inherent part of the protocol design process. Since Prawn runs on real IEEE 802.11 nodes, prototypes can be evaluated and adjusted under realistic conditions. Once the prototype has been extensively tested and thoroughly validated, and its functional design tuned accordingly, it is then ready for implementation. Prawn facilitates prototype development by providing: (i) a set of building blocks that implement common functions needed by a wide range of wireless protocols (e.g., neighbor discovery, link quality assessment, message transmission and reception), and (ii) an API that allows protocol designers to access Prawn primitives. We show through a number of case studies how Prawn supports prototyping as part of protocol design and, as a result of enabling deployment and testing under real-world scenarios, how Prawn provides useful feedback on protocol operation and performance.
Migrating Multi-page Web Applications to Single-page AJAX Interfaces
Venue: arXiv cs.SE 2007
Year: 2007

Recently, a new web development technique for creating interactive web applications, dubbed AJAX, has emerged. In this new model, the single-page web interface is composed of individual components which can be updated/replaced independently. With the rise of AJAX web applications classical multi-page web applications are becoming legacy systems. If until a year ago, the concern revolved around migrating legacy systems to web-based settings, today we have a new challenge of migrating web applications to single-page AJAX applications. Gaining an understanding of the navigational model and user interface structure of the source application is the first step in the migration process. In this paper, we explore how reverse engineering techniques can help analyze classic web applications for this purpose. Our approach, using a schema-based clustering technique, extracts a navigational model of web applications, and identifies candidate user interface components to be migrated to a single-page AJAX interface. Additionally, results of a case study, conducted to evaluate our tool, are presented.
Why block length and delay behave differently if feedback is present
Venue: arXiv cs.IT 2007
Year: 2007

For output-symmetric DMCs at even moderately high rates, fixed-block-length communication systems show no improvements in their error exponents with feedback. In this paper, we study systems with fixed end-to-end delay and show that feedback generally provides dramatic gains in the error exponents. A new upper bound (the uncertainty-focusing bound) is given on the probability of symbol error in a fixed-delay communication system with feedback. This bound turns out to have a similar form to Viterbi's bound used for the block error probability of convolutional codes as a function of the fixed constraint length. The uncertainty-focusing bound is shown to be asymptotically achievable with noiseless feedback for erasure channels as well as any output-symmetric DMC that has strictly positive zero-error capacity. Furthermore, it can be achieved in a delay-universal (anytime) fashion even if the feedback itself is delayed by a small amount. Finally, it is shown that for end-to-end delay, it is generally possible at high rates to beat the sphere-packing bound for general DMCs -- thereby providing a counterexample to a conjecture of Pinsker.
On the Complexity of Processing Massive, Unordered, Distributed Data
Venue: arXiv cs.CC 2007
Year: 2007

An existing approach for dealing with massive data sets is to stream over the input in few passes and perform computations with sublinear resources. This method does not work for truly massive data where even making a single pass over the data with a processor is prohibitive. Successful log processing systems in practice such as Google's MapReduce and Apache's Hadoop use multiple machines. They efficiently perform a certain class of highly distributable computations defined by local computations that can be applied in any order to the input. Motivated by the success of these systems, we introduce a simple algorithmic model for massive, unordered, distributed (mud) computation. We initiate the study of understanding its computational complexity. Our main result is a positive one: any unordered function that can be computed by a streaming algorithm can also be computed with a mud algorithm, with comparable space and communication complexity. We extend this result to some useful classes of approximate and randomized streaming algorithms. We also give negative results, using communication complexity arguments to prove that extensions to private randomness, promise problems and indeterminate functions are impossible. We believe that the line of research we introduce in this paper has the potential for tremendous impact. The distributed systems that motivate our work successfully process data at an unprecedented scale, distributed over hundreds or even thousands of machines, and perform hundreds of such analyses each day. The mud model (and its generalizations) inspire a set of complexity-theoretic questions that lie at their heart.
Articulation entre élaboration de solutions et argumentation polyphonique
Venue: arXiv cs.HC 2007
Year: 2007

In this paper, we propose an analytical framework that aims to bring out the nature of participants' contributions to co-design meetings, in a way that synthesises content and function dimensions, together with the dimension of dialogicality. We term the resulting global vision of contribution, the "interactive profile".
Design Strategies and Knowledge in Object-Oriented Programming: Effects of Experience
Venue: arXiv cs.HC 2007
Year: 2007

An empirical study was conducted to analyse design strategies and knowledge used in object-oriented software design. Eight professional programmers experienced with procedural programming languages and either experienced or not experienced in object-oriented design strategies related to two central aspects of the object-oriented paradigm: (1) associating actions, i.e., execution steps, of a complex plan to different objects and revising a complex plan, and (2) defining simple plans at different levels in the class hierarchy. As regards the development of complex plans elements attached to different objects, our results show that, for beginners in OOP, the description of objects and the description of actions are not always integrated in an early design phase, particularly for the declarative problem whereas, for the programmers experienced in OOP, the description of objects and the description of actions tend to be integrated in their first drafts of solutions whichever the problem type. The analysis of design strategies reveal the use of different knowledge according to subjects' language experience: (1) schemas related to procedural languages; actions are organized in an execution order, or (2) schemas related to object-oriented languages; actions and objects are integrated, and actions are organised around objects.
Reusing processes and documenting processes: toward an integrated framework
Venue: arXiv cs.HC 2007
Year: 2007

This paper presents a cognitive typology of reuse processes, and a cognitive typology of documenting processes. Empirical studies on design with reuse and on software documenting provide evidence for a generalized cognitive model. First, these studies emphasize the cyclical nature of design: cycles of planning, writing and revising occur. Second, natural language documentation follows the hierarchy of cognitive entities manipulated during design. Similarly software reuse involves exploiting various types of knowledge depending on the phase of design in which reuse is involved. We suggest that these observations can be explained based on cognitive models of text processing: the van Dijk and Kintsch (1983) model of text comprehension, and the Hayes and Flower (1980) model of text production. Based on our generalized cognitive model, we suggest a framework for documenting reusable components.
Trustworthy content push
Venue: arXiv cs.CR 2007
Year: 2007

Delivery of content to mobile devices gains increasing importance in industrial environments to support employees in the field. An important application are e-mail push services like the fashionable Blackberry. These systems are facing security challenges regarding data transport to, and storage of the data on the end user equipment. The emerging Trusted Computing technology offers new answers to these open questions.
Effect of Finite Rate Feedback on CDMA Signature Optimization and MIMO Beamforming Vector Selection
Venue: arXiv cs.IT 2007
Year: 2007

We analyze the effect of finite rate feedback on CDMA (code-division multiple access) signature optimization and MIMO (multi-input-multi-output) beamforming vector selection. In CDMA signature optimization, for a particular user, the receiver selects a signature vector from a codebook to best avoid interference from other users, and then feeds the corresponding index back to the specified user. For MIMO beamforming vector selection, the receiver chooses a beamforming vector from a given codebook to maximize throughput, and feeds back the corresponding index to the transmitter. These two problems are dual: both can be modeled as selecting a unit norm vector from a finite size codebook to "match" a randomly generated Gaussian matrix. In signature optimization, the least match is required while the maximum match is preferred for beamforming selection. Assuming that the feedback link is rate limited, our main result is an exact asymptotic performance formulae where the length of the signature/beamforming vector, the dimensions of interference/channel matrix, and the feedback rate approach infinity with constant ratios. The proof rests on a large deviation principle over a random matrix ensemble. Further, we show that random codebooks generated from the isotropic distritution are asymptotically optimal not only on average, but also with probability one.
A Byzantine Fault Tolerant Distributed Commit Protocol
Venue: arXiv cs.DC 2007
Year: 2007

In this paper, we present a Byzantine fault tolerant distributed commit protocol for transactions running over untrusted networks. The traditional two-phase commit protocol is enhanced by replicating the coordinator and by running a Byzantine agreement algorithm among the coordinator replicas. Our protocol can tolerate Byzantine faults at the coordinator replicas and a subset of malicious faults at the participants. A decision certificate, which includes a set of registration records and a set of votes from participants, is used to facilitate the coordinator replicas to reach a Byzantine agreement on the outcome of each transaction. The certificate also limits the ways a faulty replica can use towards non-atomic termination of transactions, or semantically incorrect transaction outcomes.
Symmetric Subresultants and Applications
Venue: arXiv cs.SC 2007
Year: 2007

Schur's transforms of a polynomial are used to count its roots in the unit disk. These are generalized them by introducing the sequence of symmetric sub-resultants of two polynomials. Although they do have a determinantal definition, we show that they satisfy a structure theorem which allows us to compute them with a type of Euclidean division. As a consequence, a fast algorithm based on a dichotomic process and FFT is designed. We prove also that these symmetric sub-resultants have a deep link with Toeplitz matrices. Finally, we propose a new algorithm of inversion for such matrices. It has the same cost as those already known, however it is fraction-free and consequently well adapted to computer algebra.
Attribute Value Weighting in K-Modes Clustering
Venue: arXiv cs.AI 2007
Year: 2007

In this paper, the traditional k-modes clustering algorithm is extended by weighting attribute value matches in dissimilarity computation. The use of attribute value weighting technique makes it possible to generate clusters with stronger intra-similarities, and therefore achieve better clustering performance. Experimental results on real life datasets show that these value weighting based k-modes algorithms are superior to the standard k-modes algorithm with respect to clustering accuracy.
The Second Law and Informatics
Venue: arXiv cs.IT 2007
Year: 2007

A unification of thermodynamics and information theory is proposed. It is argued that similarly to the randomness due to collisions in thermal systems, the quenched randomness that exists in data files in informatics systems contributes to entropy. Therefore, it is possible to define equilibrium and to calculate temperature for informatics systems. The obtained temperature yields correctly the Shannon information balance in informatics systems and is consistent with the Clausius inequality and the Carnot cycle.
Free deconvolution for signal processing applications
Venue: arXiv cs.IT 2007
Year: 2007

Situations in many fields of research, such as digital communications, nuclear physics and mathematical finance, can be modelled with random matrices. When the matrices get large, free probability theory is an invaluable tool for describing the asymptotic behaviour of many systems. It will be shown how free probability can be used to aid in source detection for certain systems. Sample covariance matrices for systems with noise are the starting point in our source detection problem. Multiplicative free deconvolution is shown to be a method which can aid in expressing limit eigenvalue distributions for sample covariance matrices, and to simplify estimators for eigenvalue distributions of covariance matrices.
Finding Astronomical Communities Through Co-readership Analysis
Venue: arXiv cs.DL 2007
Year: 2007

Whenever a large group of people are engaged in an activity, communities will form. The nature of these communities depends on the relationship considered. In the group of people who regularly use scholarly literature, a relationship like ``person i and person j have cited the same paper'' might reveal communities of people working in a particular field. On this poster, we will investigate the relationship ``person i and person j have read the same paper''. Using the data logs of the NASA/Smithsonian Astrophysics Data System (ADS), we first determine the population that will participate by requiring that a user queries the ADS at a certain rate. Next, we apply the relationship to this population. The result of this will be an abstract ``relationship space'', which we will describe in terms of various ``representations''. Examples of such ``representations'' are the projection of co-read vectors onto Principal Components and the spectral density of the co-read network. We will show that the co-read relationship results in structure, we will describe this structure and we will provide a first attempt in the classification of this structure in terms of astronomical communities. The ADS is funded by NASA Grant NNG06GG68G.
Compression-based methods for nonparametric density estimation, on-line prediction, regression and classification for time series
Venue: arXiv cs.IT 2007
Year: 2007

We address the problem of nonparametric estimation of characteristics for stationary and ergodic time series. We consider finite-alphabet time series and real-valued ones and the following four problems: i) estimation of the (limiting) probability (or estimation of the density for real-valued time series), ii) on-line prediction, iii) regression and iv) classification (or so-called problems with side information). We show that so-called archivers (or data compressors) can be used as a tool for solving these problems. In particular, firstly, it is proven that any so-called universal code (or universal data compressor) can be used as a basis for constructing asymptotically optimal methods for the above problems. (By definition, a universal code can "compress" any sequence generated by a stationary and ergodic source asymptotically till the Shannon entropy of the source.) And, secondly, we show experimentally that estimates, which are based on practically used methods of data compression, have a reasonable precision.
Approximate Eigenstructure of LTV Channels with Compactly Supported Spreading
Venue: arXiv cs.IT 2007
Year: 2007

In this article we obtain estimates on the approximate eigenstructure of channels with a spreading function supported only on a set of finite measure $|U|$.Because in typical application like wireless communication the spreading function is a random process corresponding to a random Hilbert--Schmidt channel operator $\BH$ we measure this approximation in terms of the ratio of the $p$--norm of the deviation from variants of the Weyl symbol calculus to the $a$--norm of the spreading function itself. This generalizes recent results obtained for the case $p=2$ and $a=1$. We provide a general approach to this topic and consider then operators with $|U|<\infty$ in more detail. We show the relation to pulse shaping and weighted norms of ambiguity functions. Finally we derive several necessary conditions on $|U|$, such that the approximation error is below certain levels.