OpenRaiser/Intern-Atlas huggingface dataset:
An Architecture for the Aggregation and Analysis of Scholarly Usage Data
Venue: arXiv cs.DL 2006
Year: 2006

Although recording of usage data is common in scholarly information services, its exploitation for the creation of value-added services remains limited due to concerns regarding, among others, user privacy, data validity, and the lack of accepted standards for the representation, sharing and aggregation of usage data. This paper presents a technical, standards-based architecture for sharing usage information, which we have designed and implemented. In this architecture, OpenURL-compliant linking servers aggregate usage information of a specific user community as it navigates the distributed information environment that it has access to. This usage information is made OAI-PMH harvestable so that usage information exposed by many linking servers can be aggregated to facilitate the creation of value-added services with a reach beyond that of a single community or a single information service. This paper also discusses issues that were encountered when implementing the proposed approach, and it presents preliminary results obtained from analyzing a usage data set containing about 3,500,000 requests aggregated by a federation of linking servers at the California State University system over a 20 month period.
Optimal Distortion-Power Tradeoffs in Gaussian Sensor Networks
Venue: arXiv cs.IT 2006
Year: 2006

We investigate the optimal performance of dense sensor networks by studying the joint source-channel coding problem. The overall goal of the sensor network is to take measurements from an underlying random process, code and transmit those measurement samples to a collector node in a cooperative multiple access channel with imperfect feedback, and reconstruct the entire random process at the collector node. We provide lower and upper bounds for the minimum achievable expected distortion when the underlying random process is Gaussian. In the case where the random process satisfies some general conditions, we evaluate the lower and upper bounds explicitly and show that they are of the same order for a wide range of sum power constraints. Thus, for these random processes, under these sum power constraints, we determine the achievability scheme that is order-optimal, and express the minimum achievable expected distortion as a function of the sum power constraint.
An Internet-enabled technology to support Evolutionary Design
Venue: arXiv cs.CE 2006
Year: 2006

This paper discusses the systematic use of product feedback information to support life-cycle design approaches and provides guidelines for developing a design at both the product and the system levels. Design activities are surveyed in the light of the product life cycle, and the design information flow is interpreted from a semiotic perspective. The natural evolution of a design is considered, the notion of design expectations is introduced, and the importance of evaluation of these expectations in dynamic environments is argued. Possible strategies for reconciliation of the expectations and environmental factors are described. An Internet-enabled technology is proposed to monitor product functionality, usage, and operational environment and supply the designer with relevant information. A pilot study of assessing design expectations of a refrigerator is outlined, and conclusions are drawn.
Classification of Ordinal Data
Venue: arXiv cs.AI 2006
Year: 2006

Classification of ordinal data is one of the most important tasks of relation learning. In this thesis a novel framework for ordered classes is proposed. The technique reduces the problem of classifying ordered classes to the standard two-class problem. The introduced method is then mapped into support vector machines and neural networks. Compared with a well-known approach using pairwise objects as training samples, the new algorithm has a reduced complexity and training time. A second novel model, the unimodal model, is also introduced and a parametric version is mapped into neural networks. Several case studies are presented to assert the validity of the proposed models.
Analyzing Large Collections of Electronic Text Using OLAP
Venue: arXiv cs.DB 2006
Year: 2006

Computer-assisted reading and analysis of text has various applications in the humanities and social sciences. The increasing size of many electronic text archives has the advantage of a more complete analysis but the disadvantage of taking longer to obtain results. On-Line Analytical Processing is a method used to store and quickly analyze multidimensional data. By storing text analysis information in an OLAP system, a user can obtain solutions to inquiries in a matter of seconds as opposed to minutes, hours, or even days. This analysis is user-driven allowing various users the freedom to pursue their own direction of research.
Logic Column 15: Coalgebras and Their Logics
Venue: arXiv cs.LO 2006
Year: 2006

This article describes recent work on the topic of specifying properties of transition systems. By giving a suitably abstract description of transition systems as coalgebras, it is possible to derive logics for capturing properties of these transition systems in an elegant way.
Capacity Results for Block-Stationary Gaussian Fading Channels with a Peak Power Constraint
Venue: arXiv cs.IT 2006
Year: 2006

We consider a peak-power-limited single-antenna block-stationary Gaussian fading channel where neither the transmitter nor the receiver knows the channel state information, but both know the channel statistics. This model subsumes most previously studied Gaussian fading models. We first compute the asymptotic channel capacity in the high SNR regime and show that the behavior of channel capacity depends critically on the channel model. For the special case where the fading process is symbol-by-symbol stationary, we also reveal a fundamental interplay between the codeword length, communication rate, and decoding error probability. Specifically, we show that the codeword length must scale with SNR in order to guarantee that the communication rate can grow logarithmically with SNR with bounded decoding error probability, and we find a necessary condition for the growth rate of the codeword length. We also derive an expression for the capacity per unit energy. Furthermore, we show that the capacity per unit energy is achievable using temporal ON-OFF signaling with optimally allocated ON symbols, where the optimal ON-symbol allocation scheme may depend on the peak power constraint.
High-level synthesis under I/O Timing and Memory constraints
Venue: arXiv cs.AR 2006
Year: 2006

The design of complex Systems-on-Chips implies to take into account communication and memory access constraints for the integration of dedicated hardware accelerator. In this paper, we present a methodology and a tool that allow the High-Level Synthesis of DSP algorithm, under both I/O timing and memory constraints. Based on formal models and a generic architecture, this tool helps the designer to find a reasonable trade-off between both the required I/O timing behavior and the internal memory access parallelism of the circuit. The interest of our approach is demonstrated on the case study of a FFT algorithm.
A Memory Aware High Level Synthesis Too
Venue: arXiv cs.AR 2006
Year: 2006

We introduce a new approach to take into account the memory architecture and the memory mapping in High- Level Synthesis for data intensive applications. We formalize the memory mapping as a set of constraints for the synthesis, and defined a Memory Constraint Graph and an accessibility criterion to be used in the scheduling step. We use a memory mapping file to include those memory constraints in our HLS tool GAUT. It is possible, with the help of GAUT, to explore a wide range of solutions, and to reach a good tradeoff between time, power-consumption, and area.
Tight Bounds for the Min-Max Boundary Decomposition Cost of Weighted Graphs
Venue: arXiv cs.DS 2006
Year: 2006

Many load balancing problems that arise in scientific computing applications ask to partition a graph with weights on the vertices and costs on the edges into a given number of almost equally-weighted parts such that the maximum boundary cost over all parts is small. Here, this partitioning problem is considered for bounded-degree graphs G=(V,E) with edge costs c: E->R+ that have a p-separator theorem for some p>1, i.e., any (arbitrarily weighted) subgraph of G can be separated into two parts of roughly the same weight by removing a vertex set S such that the edges incident to S in the subgraph have total cost at most proportional to (SUM_e c^p_e)^(1/p), where the sum is over all edges e in the subgraph. We show for all positive integers k and weights w that the vertices of G can be partitioned into k parts such that the weight of each part differs from the average weight by less than MAX{w_v; v in V}, and the boundary edges of each part have cost at most proportional to (SUM_e c_e^p/k)^(1/p) + MAX_e c_e. The partition can be computed in time nearly proportional to the time for computing a separator S of G. Our upper bound on the boundary costs is shown to be tight up to a constant factor for infinitely many instances with a broad range of parameters. Previous results achieved this bound only if one has c=1, w=1, and one allows parts with weight exceeding the average by a constant fraction.
The Consequences of Eliminating NP Solutions
Venue: arXiv cs.CC 2006
Year: 2006

Given a function based on the computation of an NP machine, can one in general eliminate some solutions? That is, can one in general decrease the ambiguity? This simple question remains, even after extensive study by many researchers over many years, mostly unanswered. However, complexity-theoretic consequences and enabling conditions are known. In this tutorial-style article we look at some of those, focusing on the most natural framings: reducing the number of solutions of NP functions, refining the solutions of NP functions, and subtracting from or otherwise shrinking #P functions. We will see how small advice strings are important here, but we also will see how increasing advice size to achieve robustness is central to the proof of a key ambiguity-reduction result for NP functions.
A Decision-Making Support System Based on Know-How
Venue: arXiv cs.CE 2006
Year: 2006

The research results described are concerned with: - developing a domain modeling method and tools to provide the design and implementation of decision-making support systems for computer integrated manufacturing; - building a decision-making support system based on know-how and its software environment. The research is funded by NEDO, Japan.
A simulation engine to support production scheduling using genetics-based machine learning
Venue: arXiv cs.CE 2006
Year: 2006

The ever higher complexity of manufacturing systems, continually shortening life cycles of products and their increasing variety, as well as the unstable market situation of the recent years require introducing grater flexibility and responsiveness to manufacturing processes. From this perspective, one of the critical manufacturing tasks, which traditionally attract significant attention in both academia and the industry, but which have no satisfactory universal solution, is production scheduling. This paper proposes an approach based on genetics-based machine learning (GBML) to treat the problem of flow shop scheduling. By the approach, a set of scheduling rules is represented as an individual of genetic algorithms, and the fitness of the individual is estimated based on the makespan of the schedule generated by using the rule-set. A concept of the interactive software environment consisting of a simulator and a GBML simulation engine is introduced to support human decision-making during scheduling. A pilot study is underway to evaluate the performance of the GBML technique in comparison with other methods (such as Johnson's algorithm and simulated annealing) while completing test examples.
A Chaotic Cipher Mmohocc and Its Security Analysis
Venue: arXiv cs.CR 2006
Year: 2006

In this paper we introduce a new chaotic stream cipher Mmohocc which utilizes the fundamental chaos characteristics. The designs of the major components of the cipher are given. Its cryptographic properties of period, auto- and cross-correlations, and the mixture of Markov processes and spatiotemporal effects are investigated. The cipher is resistant to the related-key-IV attacks, Time/Memory/Data tradeoff attacks, algebraic attacks, and chosen-text attacks. The keystreams successfully passed two batteries of statistical tests and the encryption speed is comparable with RC4.
Complexity of Resolution of Parametric Systems of Polynomial Equations and Inequations
Venue: arXiv cs.SC 2006
Year: 2006

Consider a system of n polynomial equations and r polynomial inequations in n indeterminates of degree bounded by d with coefficients in a polynomial ring of s parameters with rational coefficients of bit-size at most $σ$. From the real viewpoint, solving such a system often means describing some semi-algebraic sets in the parameter space over which the number of real solutions of the considered parametric system is constant. Following the works of Lazard and Rouillier, this can be done by the computation of a discriminant variety. In this report we focus on the case where for a generic specialization of the parameters the system of equations generates a radical zero-dimensional ideal, which is usual in the applications. In this case, we provide a deterministic method computing the minimal discriminant variety reducing the problem to a problem of elimination. Moreover, we prove that the degree of the computed minimal discriminant variety is bounded by $D:=(n+r)d^{(n+1)}$ and that the complexity of our method is $σ^{\mathcal{O}(1)} D^{\mathcal{O}(n+s)}$ bit-operations on a deterministic Turing machine.
Computational Euclid
Venue: arXiv cs.CG 2006
Year: 2006

We analyse the axioms of Euclidean geometry according to standard object-oriented software development methodology. We find a perfect match: the main undefined concepts of the axioms translate to object classes. The result is a suite of C++ classes that efficiently supports the construction of complex geometric configurations. Although all computations are performed in floating-point arithmetic, they correctly implement as semi-decision algorithms the tests for equality of points, a point being on a line or in a plane, a line being in a plane, parallelness of lines, of a line and a plane, and of planes. That is, in accordance to the fundamental limitations to computability requiring that only negative outcomes are given with certainty, while positive outcomes only imply possibility of these conditions being true.
Trusted Computing in Mobile Action
Venue: arXiv cs.CR 2006
Year: 2006

Due to the convergence of various mobile access technologies like UMTS, WLAN, and WiMax the need for a new supporting infrastructure arises. This infrastructure should be able to support more efficient ways to authenticate users and devices, potentially enabling novel services based on the security provided by the infrastructure. In this paper we exhibit some usage scenarios from the mobile domain integrating trusted computing, which show that trusted computing offers new paradigms for implementing trust and by this enables new technical applications and business scenarios. The scenarios show how the traditional boundaries between technical and authentication domains become permeable while a high security level is maintained.
Threshold-Controlled Global Cascading in Wireless Sensor Networks
Venue: arXiv cs.NI 2006
Year: 2006

We investigate cascade dynamics in threshold-controlled (multiplex) propagation on random geometric networks. We find that such local dynamics can serve as an efficient, robust, and reliable prototypical activation protocol in sensor networks in responding to various alarm scenarios. We also consider the same dynamics on a modified network by adding a few long-range communication links, resulting in a small-world network. We find that such construction can further enhance and optimize the speed of the network's response, while keeping energy consumption at a manageable level.
Complex Networks: New Concepts and Tools for Real-Time Imaging and Vision
Venue: arXiv cs.CV 2006
Year: 2006

This article discusses how concepts and methods of complex networks can be applied to real-time imaging and computer vision. After a brief introduction of complex networks basic concepts, their use as means to represent and characterize images, as well as for modeling visual saliency, are briefly described. The possibility to apply complex networks in order to model and simulate the performance of parallel and distributed computing systems for performance of visual methods is also proposed.
On the Efficiency of Strategies for Subdividing Polynomial Triangular Surface Patches
Venue: arXiv cs.CG 2006
Year: 2006

In this paper, we investigate the efficiency of various strategies for subdividing polynomial triangular surface patches. We give a simple algorithm performing a regular subdivision in four calls to the standard de Casteljau algorithm (in its subdivision version). A naive version uses twelve calls. We also show that any method for obtaining a regular subdivision using the standard de Casteljau algorithm requires at least 4 calls. Thus, our method is optimal. We give another subdivision algorithm using only three calls to the de Casteljau algorithm. Instead of being regular, the subdivision pattern is diamond-like. Finally, we present a ``spider-like'' subdivision scheme producing six subtriangles in four calls to the de Casteljau algorithm.
Improved Exponential Time Lower Bound of Knapsack Problem under BT model
Venue: arXiv cs.CC 2006
Year: 2006

M.Alekhnovich et al. recently have proposed a model of algorithms, called BT model, which covers Greedy, Backtrack and Simple Dynamic Programming methods and can be further divided into fixed, adaptive and fully adaptive three kinds, and have proved exponential time lower bounds of exact and approximation algorithms under adaptive BT model for Knapsack problem which are $Ω(2^{n/2}/\sqrt n)=Ω(2^{0.5n}/\sqrt n)$ and $Ω((1/ε)^{1/3.17})\approxΩ((1/ε)^{0.315})$(for approximation ratio $1-ε$) respectively (M. Alekhovich, A. Borodin, J. Buresh-Oppenheim, R. Impagliazzo, A. Magen, and T. Pitassi, Toward a Model for Backtracking and Dynamic Programming, \emph{Proceedings of Twentieth Annual IEEE Conference on Computational Complexity}, pp308-322, 2005). In this note, we slightly improved their lower bounds to $Ω(2^{(2-ε)n/3}/\sqrt{n})\approx Ω(2^{0.66n}/\sqrt{n})$ and $Ω((1/ε)^{1/2.38})\approxΩ((1/ε)^{0.420})$, and proposed as an open question what is the best achievable lower bounds for knapsack under adaptive BT models.
Relational Parametricity and Control
Venue: arXiv cs.PL 2006
Year: 2006

We study the equational theory of Parigot's second-order λμ-calculus in connection with a call-by-name continuation-passing style (CPS) translation into a fragment of the second-order λ-calculus. It is observed that the relational parametricity on the target calculus induces a natural notion of equivalence on the λμ-terms. On the other hand, the unconstrained relational parametricity on the λμ-calculus turns out to be inconsistent with this CPS semantics. Following these facts, we propose to formulate the relational parametricity on the λμ-calculus in a constrained way, which might be called ``focal parametricity''.
On the structure of linear-time reducibility
Venue: arXiv cs.CC 2006
Year: 2006

In 1975, Ladner showed that under the hypothesis that P is not equal to NP, there exists a language which is neither in P, nor NP-complete. This result was latter generalized by Schoning and several authors to various polynomial-time complexity classes. We show here that such results also apply to linear-time reductions on RAMs (resp. Turing machines), and hence allow for separation results in linear-time classes similar to Ladner's ones for polynomial time.
On computing fixpoints in well-structured regular model checking, with applications to lossy channel systems
Venue: arXiv cs.SC 2006
Year: 2006

We prove a general finite convergence theorem for "upward-guarded" fixpoint expressions over a well-quasi-ordered set. This has immediate applications in regular model checking of well-structured systems, where a main issue is the eventual convergence of fixpoint computations. In particular, we are able to directly obtain several new decidability results on lossy channel systems.
An information-spectrum approach to large deviation theorems
Venue: arXiv cs.IT 2006
Year: 2006

In this paper we show a some new look at large deviation theorems from the viewpoint of the information-spectrum (IS) methods, which has been first exploited in information theory, and also demonstrate a new basic formula for the large deviation rate function in general, which is a pair of the lower and upper IS rate functions. In particular, we are interested in establishing the general large deviation rate functions that can be derivable as the Fenchel-Legendre transform of the cumulant generating function. The final goal is to show a necessary and sufficient condition for the rate function to be of Cramér-Gärtner-Ellis type.
Product Centric Holons for Synchronisation and Interoperability in Manufacturing Environments
Venue: arXiv cs.SE 2006
Year: 2006

In the last few years, lot of work has been done in order to ensure enterprise applications interoperability; however, proposed solutions focus mainly on enterprise processes. Indeed, throughout product lifecycle coordination needs to be established between reality in the physical world (physical view) and the virtual world handled by manufacturing information systems (informational view). This paper presents a holonic approach that enables synchronisation of both physical and informational views. A model driven approach for interoperability is proposed to ensure interoperability of holon based models with other applications in the enterprise.
Evaluating Variable Length Markov Chain Models for Analysis of User Web Navigation Sessions
Venue: arXiv cs.AI 2006
Year: 2006

Markov models have been widely used to represent and analyse user web navigation data. In previous work we have proposed a method to dynamically extend the order of a Markov chain model and a complimentary method for assessing the predictive power of such a variable length Markov chain. Herein, we review these two methods and propose a novel method for measuring the ability of a variable length Markov model to summarise user web navigation sessions up to a given length. While the summarisation ability of a model is important to enable the identification of user navigation patterns, the ability to make predictions is important in order to foresee the next link choice of a user after following a given trail so as, for example, to personalise a web site. We present an extensive experimental evaluation providing strong evidence that prediction accuracy increases linearly with summarisation ability.
New Algorithms for Regular Expression Matching
Venue: arXiv cs.DS 2006
Year: 2006

In this paper we revisit the classical regular expression matching problem, namely, given a regular expression $R$ and a string $Q$, decide if $Q$ matches one of the strings specified by $R$. Let $m$ and $n$ be the length of $R$ and $Q$, respectively. On a standard unit-cost RAM with word length $w \geq \log n$, we show that the problem can be solved in $O(m)$ space with the following running times: \begin{equation*} \begin{cases} O(n\frac{m \log w}{w} + m \log w) & \text{if $m > w$} \\ O(n\log m + m\log m) & \text{if $\sqrt{w} < m \leq w$} \\ O(\min(n+ m^2, n\log m + m\log m)) & \text{if $m \leq \sqrt{w}$.} \end{cases} \end{equation*} This improves the best known time bound among algorithms using $O(m)$ space. Whenever $w \geq \log^2 n$ it improves all known time bounds regardless of how much space is used.