OpenRaiser/Intern-Atlas huggingface dataset:
Symbolic model checking of tense logics on rational Kripke models
Venue: arXiv cs.LO 2008
Year: 2008

We introduce the class of rational Kripke models and study symbolic model checking of the basic tense logic Kt and some extensions of it in models from that class. Rational Kripke models are based on (generally infinite) rational graphs, with vertices labeled by the words in some regular language and transitions recognized by asynchronous two-head finite automata, also known as rational transducers. Every atomic proposition in a rational Kripke model is evaluated in a regular set of states. We show that every formula of Kt has an effectively computable regular extension in every rational Kripke model, and therefore local model checking and global model checking of Kt in rational Kripke models are decidable. These results are lifted to a number of extensions of Kt. We study and partly determine the complexity of the model checking procedures.
Anonymizing Graphs
Venue: arXiv cs.DB 2008
Year: 2008

Motivated by recently discovered privacy attacks on social networks, we study the problem of anonymizing the underlying graph of interactions in a social network. We call a graph (k,l)-anonymous if for every node in the graph there exist at least k other nodes that share at least l of its neighbors. We consider two combinatorial problems arising from this notion of anonymity in graphs. More specifically, given an input graph we ask for the minimum number of edges to be added so that the graph becomes (k,l)-anonymous. We define two variants of this minimization problem and study their properties. We show that for certain values of k and l the problems are polynomial-time solvable, while for others they become NP-hard. Approximation algorithms for the latter cases are also given.
Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation
Venue: arXiv cs.SC 2008
Year: 2008

Kaltofen has proposed a new approach in 1992 for computing matrix determinants without divisions. The algorithm is based on a baby steps/giant steps construction of Krylov subspaces, and computes the determinant as the constant term of a characteristic polynomial. For matrices over an abstract ring, by the results of Baur and Strassen, the determinant algorithm, actually a straight-line program, leads to an algorithm with the same complexity for computing the adjoint of a matrix. However, the latter adjoint algorithm is obtained by the reverse mode of automatic differentiation, hence somehow is not "explicit". We present an alternative (still closely related) algorithm for the adjoint thatcan be implemented directly, we mean without resorting to an automatic transformation. The algorithm is deduced by applying program differentiation techniques "by hand" to Kaltofen's method, and is completely decribed. As subproblem, we study the differentiation of programs that compute minimum polynomials of lineraly generated sequences, and we use a lazy polynomial evaluation mechanism for reducing the cost of Strassen's avoidance of divisions in our case.
A triangle-based logic for affine-invariant querying of spatial and spatio-temporal data
Venue: arXiv cs.LO 2008
Year: 2008

In spatial databases, incompatibilities often arise due to different choices of origin or unit of measurement (e.g., centimeters versus inches). By representing and querying the data in an affine-invariant manner, we can avoid these incompatibilities. In practice, spatial (resp., spatio-temporal) data is often represented as a finite union of triangles (resp., moving triangles). As two arbitrary triangles are equal up to a unique affinity of the plane, they seem perfect candidates as basic units for an affine-invariant query language. We propose a so-called "triangle logic", a query language that is affine-generic and has triangles as basic elements. We show that this language has the same expressive power as the affine-generic fragment of first-order logic over the reals on triangle databases. We illustrate that the proposed language is simple and intuitive. It can also serve as a first step towards a "moving-triangle logic" for spatio-temporal data.
Practical language based on systems of definitions
Venue: arXiv cs.DC 2008
Year: 2008

The article suggests a description of a system of tables with a set of special lists absorbing a semantics of data and reflects a fullness of data. It shows how their parallel processing can be constructed based on the descriptions. The approach also might be used for definition intermediate targets for data mining and unstructured data processing.
A Swarm Intelligence Based Scheme for Complete and Fault-tolerant Identification of a Dynamical Fractional Order Process
Venue: arXiv cs.OH 2008
Year: 2008

System identification refers to estimation of process parameters and is a necessity in control theory. Physical systems usually have varying parameters. For such processes, accurate identification is particularly important. Online identification schemes are also needed for designing adaptive controllers. Real processes are usually of fractional order as opposed to the ideal integral order models. In this paper, we propose a simple and elegant scheme of estimating the parameters for such a fractional order process. A population of process models is generated and updated by particle swarm optimization (PSO) technique, the fitness function being the sum of squared deviations from the actual set of observations. Results show that the proposed scheme offers a high degree of accuracy even when the observations are corrupted to a significant degree. Additional schemes to improve the accuracy still further are also proposed and analyzed.
Reduced-Complexity Reed--Solomon Decoders Based on Cyclotomic FFTs
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we reduce the computational complexities of partial and dual partial cyclotomic FFTs (CFFTs), which are discrete Fourier transforms where spectral and temporal components are constrained, based on their properties as well as a common subexpression elimination algorithm. Our partial CFFTs achieve smaller computational complexities than previously proposed partial CFFTs. Utilizing our CFFTs in both transform- and time-domain Reed--Solomon decoders, we achieve significant complexity reductions.
CoZo+ - A Content Zoning Engine for textual documents
Venue: arXiv cs.CL 2008
Year: 2008

Content zoning can be understood as a segmentation of textual documents into zones. This is inspired by [6] who initially proposed an approach for the argumentative zoning of textual documents. With the prototypical CoZo+ engine, we focus on content zoning towards an automatic processing of textual streams while considering only the actors as the zones. We gain information that can be used to realize an automatic recognition of content for pre-defined actors. We understand CoZo+ as a necessary pre-step towards an automatic generation of summaries and to make intellectual ownership of documents detectable.
Classification dynamique d'un flux documentaire : une évaluation statique préalable de l'algorithme GERMEN
Venue: arXiv cs.AI 2008
Year: 2008

Data-stream clustering is an ever-expanding subdomain of knowledge extraction. Most of the past and present research effort aims at efficient scaling up for the huge data repositories. Our approach focuses on qualitative improvement, mainly for "weak signals" detection and precise tracking of topical evolutions in the framework of information watch - though scalability is intrinsically guaranteed in a possibly distributed implementation. Our GERMEN algorithm exhaustively picks up the whole set of density peaks of the data at time t, by identifying the local perturbations induced by the current document vector, such as changing cluster borders, or new/vanishing clusters. Optimality yields from the uniqueness 1) of the density landscape for any value of our zoom parameter, 2) of the cluster allocation operated by our border propagation rule. This results in a rigorous independence from the data presentation ranking or any initialization parameter. We present here as a first step the only assessment of a static view resulting from one year of the CNRS/INIST Pascal database in the field of geotechnics.
Web Usage Analysis: New Science Indicators and Co-usage
Venue: arXiv cs.IR 2008
Year: 2008

A new type of statistical analysis of the science and technical information (STI) in the Web context is produced. We propose a set of indicators about Web users, visualized bibliographic records, and e-commercial transactions. In addition, we introduce two Web usage factors. Finally, we give an overview of the co-usage analysis. For these tasks, we introduce a computer based system, called Miri@d, which produces descriptive statistical information about the Web users' searching behaviour, and what is effectively used from a free access digital bibliographical database. The system is conceived as a server of statistical data which are carried out beforehand, and as an interactive server for online statistical work. The results will be made available to analysts, who can use this descriptive statistical information as raw data for their indicator design tasks, and as input for multivariate data analysis, clustering analysis, and mapping. Managers also can exploit the results in order to improve management and decision-making.
Data Mining-based Fragmentation of XML Data Warehouses
Venue: arXiv cs.DB 2008
Year: 2008

With the multiplication of XML data sources, many XML data warehouse models have been proposed to handle data heterogeneity and complexity in a way relational data warehouses fail to achieve. However, XML-native database systems currently suffer from limited performances, both in terms of manageable data volume and response time. Fragmentation helps address both these issues. Derived horizontal fragmentation is typically used in relational data warehouses and can definitely be adapted to the XML context. However, the number of fragments produced by classical algorithms is difficult to control. In this paper, we propose the use of a k-means-based fragmentation approach that allows to master the number of fragments through its $k$ parameter. We experimentally compare its efficiency to classical derived horizontal fragmentation algorithms adapted to XML data warehouses and show its superiority.
When are two algorithms the same?
Venue: arXiv cs.GL 2008
Year: 2008

People usually regard algorithms as more abstract than the programs that implement them. The natural way to formalize this idea is that algorithms are equivalence classes of programs with respect to a suitable equivalence relation. We argue that no such equivalence relation exists.
Persistent Queries
Venue: arXiv cs.PL 2008
Year: 2008

We propose a syntax and semantics for interactive abstract state machines to deal with the following situation. A query is issued during a certain step, but the step ends before any reply is received. Later, a reply arrives, and later yet the algorithm makes use of this reply. By a persistent query, we mean a query for which a late reply might be used. Syntactically, our proposal involves issuing, along with a persistent query, a location where a late reply is to be stored. Semantically, it involves only a minor modification of the existing theory of interactive small-step abstract state machines.
Adaptive Base Class Boost for Multi-class Classification
Venue: arXiv cs.LG 2008
Year: 2008

We develop the concept of ABC-Boost (Adaptive Base Class Boost) for multi-class classification and present ABC-MART, a concrete implementation of ABC-Boost. The original MART (Multiple Additive Regression Trees) algorithm has been very successful in large-scale applications. For binary classification, ABC-MART recovers MART. For multi-class classification, ABC-MART considerably improves MART, as evaluated on several public data sets.
Algorithmic Techniques for Several Optimization Problems Regarding Distributed Systems with Tree Topologies
Venue: arXiv cs.DS 2008
Year: 2008

As the development of distributed systems progresses, more and more challenges arise and the need for developing optimized systems and for optimizing existing systems from multiple perspectives becomes more stringent. In this paper I present novel algorithmic techniques for solving several optimization problems regarding distributed systems with tree topologies. I address topics like: reliability improvement, partitioning, coloring, content delivery, optimal matchings, as well as some tree counting aspects. Some of the presented techniques are only of theoretical interest, while others can be used in practical settings.
Pilotage des processus collaboratifs dans les systèmes PLM. Quels indicateurs pour quelle évaluation des performances ?
Venue: arXiv cs.SE 2008
Year: 2008

Les entreprises qui collaborent dans un processus de développement de produit ont besoin de mettre en oeuvre une gestion efficace des activités collaborative. Malgré la mise en place d'un PLM, les activités collaborative sont loin d'être aussi efficace que l'on pourrait s'y attendre. Cet article propose une analyse des problématiques de la collaboration avec un système PLM. A partir de ces analyses, nous proposons la mise en place d'indicateurs et d'actions sur les processus visant à identifier puis atténuer les freins dans le travail collaboratif. ----- Companies that collaborate within the product development processes need to implement an effective management of their collaborative activities. Despite the implementation of a PLM system, the collaborative activities are not efficient as it might be expected. This paper presents an analysis of the problems related to the collaborative work using a PLM system, identified through a survey. From this analysis, we propose an approach for improving collaborative processes within a PLM system, based on monitoring indicators. This approach leads to identify and therefore to mitigate the brakes of the collaborative work.
Fast Maximum-Likelihood Decoding of the Golden Code
Venue: arXiv cs.IT 2008
Year: 2008

The golden code is a full-rate full-diversity space-time code for two transmit antennas that has a maximal coding gain. Because each codeword conveys four information symbols from an M-ary quadrature-amplitude modulation alphabet, the complexity of an exhaustive search decoder is proportional to M^2. In this paper we present a new fast algorithm for maximum-likelihood decoding of the golden code that has a worst-case complexity of only O(2M^2.5). We also present an efficient implementation of the fast decoder that exhibits a low average complexity. Finally, in contrast to the overlaid Alamouti codes, which lose their fast decodability property on time-varying channels, we show that the golden code is fast decodable on both quasistatic and rapid time-varying channels.
The Design of Compressive Sensing Filter
Venue: arXiv cs.CE 2008
Year: 2008

In this paper, the design of universal compressive sensing filter based on normal filters including the lowpass, highpass, bandpass, and bandstop filters with different cutoff frequencies (or bandwidth) has been developed to enable signal acquisition with sub-Nyquist sampling. Moreover, to control flexibly the size and the coherence of the compressive sensing filter, as an example, the microstrip filter based on defected ground structure (DGS) has been employed to realize the compressive sensing filter. Of course, the compressive sensing filter also can be constructed along the identical idea by many other structures, for example, the man-made electromagnetic materials, the plasma with different electron density, and so on. By the proposed architecture, the n-dimensional signals of S-sparse in arbitrary orthogonal frame can be exactly reconstructed with measurements on the order of Slog(n) with overwhelming probability, which is consistent with the bonds estimated by theoretical analysis.
Geometric properties of satisfying assignments of random $ε$-1-in-k SAT
Venue: arXiv cs.CC 2008
Year: 2008

We study the geometric structure of the set of solutions of random $ε$-1-in-k SAT problem. For $l\geq 1$, two satisfying assignments $A$ and $B$ are $l$-connected if there exists a sequence of satisfying assignments connecting them by changing at most $l$ bits at a time. We first prove that w.h.p. two assignments of a random $ε$-1-in-$k$ SAT instance are $O(\log n)$-connected, conditional on being satisfying assignments. Also, there exists $ε_{0}\in (0,\frac{1}{k-2})$ such that w.h.p. no two satisfying assignments at distance at least $ε_{0}\cdot n$ form a "hole" in the set of assignments. We believe that this is true for all $ε>0$, and thus satisfying assignments of a random 1-in-$k$ SAT instance form a single cluster.
Desynched channels on IRCnet
Venue: arXiv cs.NI 2008
Year: 2008

In this paper we describe what a desynchronised channel on IRC is. We give procedures on how to create such a channel and how to remove desynchronisation. We explain which types of desynchronisation there are, what properties desynchronised channels have, and which properties can be exploited.
Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems
Venue: arXiv cs.DS 2008
Year: 2008

We design a linear time approximation scheme for the Gale-Berlekamp Switching Game and generalize it to a wider class of dense fragile minimization problems including the Nearest Codeword Problem (NCP) and Unique Games Problem. Further applications include, among other things, finding a constrained form of matrix rigidity and maximum likelihood decoding of an error correcting code. As another application of our method we give the first linear time approximation schemes for correlation clustering with a fixed number of clusters and its hierarchical generalization. Our results depend on a new technique for dealing with small objective function values of optimization problems and could be of independent interest.
SINR Diagrams: Towards Algorithmically Usable SINR Models of Wireless Networks
Venue: arXiv cs.NI 2008
Year: 2008

The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model. For a collection of simultaneously transmitting stations in the plane, it is possible to identify a reception zone for each station, consisting of the points where its transmission is received correctly. The resulting SINR diagram partitions the plane into a reception zone per station and the remaining plane where no station can be heard. SINR diagrams appear to be fundamental to understanding the behavior of wireless networks, and may play a key role in the development of suitable algorithms for such networks, analogous perhaps to the role played by Voronoi diagrams in the study of proximity queries and related issues in computational geometry. So far, however, the properties of SINR diagrams have not been studied systematically, and most algorithmic studies in wireless networking rely on simplified graph-based models such as the unit disk graph (UDG) model, which conveniently abstract away interference-related complications, and make it easier to handle algorithmic issues, but consequently fail to capture accurately some important aspects of wireless networks. The current paper focuses on obtaining some basic understanding of SINR diagrams, their properties and their usability in algorithmic applications. Specifically, based on some algebraic properties of the polynomials defining the reception zones we show that assuming uniform power transmissions, the reception zones are convex and relatively well-rounded. These results are then used to develop an efficient approximation algorithm for a fundamental point location problem in wireless networks.
Dynamic System Adaptation by Constraint Orchestration
Venue: arXiv cs.SE 2008
Year: 2008

For Paradigm models, evolution is just-in-time specified coordination conducted by a special reusable component McPal. Evolution can be treated consistently and on-the-fly through Paradigm's constraint orchestration, also for originally unforeseen evolution. UML-like diagrams visually supplement such migration, as is illustrated for the case of a critical section solution evolving into a pipeline architecture.
Analyse de la rigidité des machines outils 3 axes d'architecture parallèle hyperstatique
Venue: arXiv cs.RO 2008
Year: 2008

The paper presents a new stiffness modelling method for overconstrained parallel manipulators, which is applied to 3-d.o.f. translational mechanisms. It is based on a multidimensional lumped-parameter model that replaces the link flexibility by localized 6-d.o.f. virtual springs. In contrast to other works, the method includes a FEA-based link stiffness evaluation and employs a new solution strategy of the kinetostatic equations, which allows computing the stiffness matrix for the overconstrained architectures and for the singular manipulator postures. The advantages of the developed technique are confirmed by application examples, which deal with comparative stiffness analysis of two translational parallel manipulators.
Description of the CUDF Format
Venue: arXiv cs.SE 2008
Year: 2008

This document contains several related specifications, together they describe the document formats related to the solver competition which will be organized by Mancoosi. In particular, this document describes: - DUDF (Distribution Upgradeability Description Format), the document format to be used to submit upgrade problem instances from user machines to a (distribution-specific) database of upgrade problems; - CUDF (Common Upgradeability Description Format), the document format used to encode upgrade problems, abstracting over distribution-specific details. Solvers taking part in the competition will be fed with input in CUDF format.
Highly Undecidable Problems about Recognizability by Tiling Systems
Venue: arXiv cs.CC 2008
Year: 2008

Altenbernd, Thomas and Wöhrle have considered acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with usual acceptance conditions, such as the Büchi and Muller ones [1]. It was proved in [9] that it is undecidable whether a Büchi-recognizable language of infinite pictures is E-recognizable (respectively, A-recognizable). We show here that these two decision problems are actually $Π_2^1$-complete, hence located at the second level of the analytical hierarchy, and "highly undecidable". We give the exact degree of numerous other undecidable problems for Büchi-recognizable languages of infinite pictures. In particular, the non-emptiness and the infiniteness problems are $Σ^1_1$-complete, and the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, are all $Π^1_2$-complete. It is also $Π^1_2$-complete to determine whether a given Büchi recognizable language of infinite pictures can be accepted row by row using an automaton model over ordinal words of length $ω^2$.
Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem
Venue: arXiv cs.DS 2008
Year: 2008

For an edge-weighted connected undirected graph, the minimum $k$-way cut problem is to find a subset of edges of minimum total weight whose removal separates the graph into $k$ connected components. The problem is NP-hard when $k$ is part of the input and W[1]-hard when $k$ is taken as a parameter. A simple algorithm for approximating a minimum $k$-way cut is to iteratively increase the number of components of the graph by $h-1$, where $2 \le h \le k$, until the graph has $k$ components. The approximation ratio of this algorithm is known for $h \le 3$ but is open for $h \ge 4$. In this paper, we consider a general algorithm that iteratively increases the number of components of the graph by $h_i-1$, where $h_1 \le h_2 \le ... \le h_q$ and $\sum_{i=1}^q (h_i-1) = k-1$. We prove that the approximation ratio of this general algorithm is $2 - (\sum_{i=1}^q {h_i \choose 2})/{k \choose 2}$, which is tight. Our result implies that the approximation ratio of the simple algorithm is $2-h/k + O(h^2/k^2)$ in general and $2-h/k$ if $k-1$ is a multiple of $h-1$.