OpenRaiser/Intern-Atlas huggingface dataset:
Generalizing Consistency and other Constraint Properties to Quantified Constraints
Venue: arXiv cs.LO 2007
Year: 2007

Quantified constraints and Quantified Boolean Formulae are typically much more difficult to reason with than classical constraints, because quantifier alternation makes the usual notion of solution inappropriate. As a consequence, basic properties of Constraint Satisfaction Problems (CSP), such as consistency or substitutability, are not completely understood in the quantified case. These properties are important because they are the basis of most of the reasoning methods used to solve classical (existentially quantified) constraints, and one would like to benefit from similar reasoning methods in the resolution of quantified constraints. In this paper, we show that most of the properties that are used by solvers for CSP can be generalized to quantified CSP. This requires a re-thinking of a number of basic concepts; in particular, we propose a notion of outcome that generalizes the classical notion of solution and on which all definitions are based. We propose a systematic study of the relations which hold between these properties, as well as complexity results regarding the decision of these properties. Finally, and since these problems are typically intractable, we generalize the approach used in CSP and propose weaker, easier to check notions based on locality, which allow to detect these properties incompletely but in polynomial time.
Translating a first-order modal language to relational algebra
Venue: arXiv cs.LO 2007
Year: 2007

This paper is about Kripke structures that are inside a relational database and queried with a modal language. At first the modal language that is used is introduced, followed by a definition of the database and relational algebra. Based on these definitions two things are presented: a mapping from components of the modal structure to a relational database schema and instance, and a translation from queries in the modal language to relational algebra queries.
On Term Rewriting Systems Having a Rational Derivation
Venue: arXiv cs.LO 2007
Year: 2007

Several types of term rewriting systems can be distinguished by the way their rules overlap. In particular, we define the classes of prefix, suffix, bottom-up and top-down systems, which generalize similar classes on words. Our aim is to study the derivation relation of such systems (i.e. the reflexive and transitive closure of their rewriting relation) and, if possible, to provide a finite mechanism characterizing it. Using a notion of rational relations based on finite graph grammars, we show that the derivation of any bottom-up, top-down or suffix systems is rational, while it can be non recursive for prefix systems.
The Battery-Discharge-Model: A Class of Stochastic Finite Automata to Simulate Multidimensional Continued Fraction Expansion
Venue: arXiv cs.IT 2007
Year: 2007

We define an infinite stochastic state machine, the Battery-Discharge-Model (BDM), which simulates the behaviour of linear and jump complexity of the continued fraction expansion of multidimensional formal power series, a relevant security measure in the cryptanalysis of stream ciphers. We also obtain finite approximations to the infinite BDM, where polynomially many states suffice to approximate with an exponentially small error the probabilities and averages for linear and jump complexity of M-multisequences of length n over the finite field F_q, for any M, n, q.
Defect-Tolerant CMOL Cell Assignment via Satisfiability
Venue: arXiv cs.DM 2007
Year: 2007

We present a CAD framework for CMOL, a hybrid CMOS/ molecular circuit architecture. Our framework first transforms any logically synthesized circuit based on AND/OR/NOT gates to a NOR gate circuit, and then maps the NOR gates to CMOL. We encode the CMOL cell assignment problem as boolean conditions. The boolean constraint is satisfiable if and only if there is a way to map all the NOR gates to the CMOL cells. We further investigate various types of static defects for the CMOL architecture, and propose a reconfiguration technique that can deal with these defects through our CAD framework. This is the first automated framework for CMOL cell assignment, and the first to model several different CMOL static defects. Empirical results show that our approach is efficient and scalable.
Modeling Epidemic Spread in Synthetic Populations - Virtual Plagues in Massively Multiplayer Online Games
Venue: arXiv cs.CY 2007
Year: 2007

A virtual plague is a process in which a behavior-affecting property spreads among characters in a Massively Multiplayer Online Game (MMOG). The MMOG individuals constitute a synthetic population, and the game can be seen as a form of interactive executable model for studying disease spread, albeit of a very special kind. To a game developer maintaining an MMOG, recognizing, monitoring, and ultimately controlling a virtual plague is important, regardless of how it was initiated. The prospect of using tools, methods and theory from the field of epidemiology to do this seems natural and appealing. We will address the feasibility of such a prospect, first by considering some basic measures used in epidemiology, then by pointing out the differences between real world epidemics and virtual plagues. We also suggest directions for MMOG developer control through epidemiological modeling. Our aim is understanding the properties of virtual plagues, rather than trying to eliminate them or mitigate their effects, as would be in the case of real infectious disease.
An Improved Tight Closure Algorithm for Integer Octagonal Constraints
Venue: arXiv cs.DS 2007
Year: 2007

Integer octagonal constraints (a.k.a. ``Unit Two Variables Per Inequality'' or ``UTVPI integer constraints'') constitute an interesting class of constraints for the representation and solution of integer problems in the fields of constraint programming and formal analysis and verification of software and hardware systems, since they couple algorithms having polynomial complexity with a relatively good expressive power. The main algorithms required for the manipulation of such constraints are the satisfiability check and the computation of the inferential closure of a set of constraints. The latter is called `tight' closure to mark the difference with the (incomplete) closure algorithm that does not exploit the integrality of the variables. In this paper we present and fully justify an O(n^3) algorithm to compute the tight closure of a set of UTVPI integer constraints.
Local Area Damage Detection in Composite Structures Using Piezoelectric Transducers
Venue: arXiv cs.SD 2007
Year: 2007

An integrated and automated smart structures approach for structural health monitoring is presented, utilizing an array of piezoelectric transducers attached to or embedded within the structure for both actuation and sensing. The system actively interrogates the structure via broadband excitation of multiple actuators across a desired frequency range. The structure's vibration signature is then characterized by computing the transfer functions between each actuator/sensor pair, and compared to the baseline signature. Experimental results applying the system to local area damage detection in a MD Explorer rotorcraft composite flexbeam are presented.
A Novel Model of Working Set Selection for SMO Decomposition Methods
Venue: arXiv cs.LG 2007
Year: 2007

In the process of training Support Vector Machines (SVMs) by decomposition methods, working set selection is an important technique, and some exciting schemes were employed into this field. To improve working set selection, we propose a new model for working set selection in sequential minimal optimization (SMO) decomposition methods. In this model, it selects B as working set without reselection. Some properties are given by simple proof, and experiments demonstrate that the proposed method is in general faster than existing methods.
Code spectrum and reliability function: Gaussian channel
Venue: arXiv cs.IT 2007
Year: 2007

A new approach for upper bounding the channel reliability function using the code spectrum is described. It allows to treat both low and high rate cases in a unified way. In particular, the earlier known upper bounds are improved, and a new derivation of the sphere-packing bound is presented.
Position Coding
Venue: arXiv cs.IT 2007
Year: 2007

A position coding pattern is an array of symbols in which subarrays of a certain fixed size appear at most once. So, each subarray uniquely identifies a location in the larger array, which means there is a bijection of some sort from this set of subarrays to a set of coordinates. The key to Fly Pentop Computer paper and other examples of position codes is a method to read the subarray and then convert it to coordinates. Position coding makes use of ideas from discrete mathematics and number theory. In this paper, we will describe the underlying mathematics of two position codes, one being the Anoto code that is the basis of "Fly paper". Then, we will present two new codes, one which uses binary wavelets as part of the bijection.
Inferring the Composition of a Trader Population in a Financial Market
Venue: arXiv cs.CE 2007
Year: 2007

We discuss a method for predicting financial movements and finding pockets of predictability in the price-series, which is built around inferring the heterogeneity of trading strategies in a multi-agent trader population. This work explores extensions to our previous framework (arXiv:physics/0506134). Here we allow for more intelligent agents possessing a richer strategy set, and we no longer constrain the estimate for the heterogeneity of the agents to a probability space. We also introduce a scheme which allows the incorporation of models with a wide variety of agent types, and discuss a mechanism for the removal of bias from relevant parameters.
Families of traveling impulses and fronts in some models with cross-diffusion
Venue: arXiv cs.NA 2007
Year: 2007

An analysis of traveling wave solutions of partial differential equation (PDE) systems with cross-diffusion is presented. The systems under study fall in a general class of the classical Keller-Segel models to describe chemotaxis. The analysis is conducted using the theory of the phase plane analysis of the corresponding wave systems without a priory restrictions on the boundary conditions of the initial PDE. Special attention is paid to families of traveling wave solutions. Conditions for existence of front-impulse, impulse-front, and front-front traveling wave solutions are formulated. In particular, the simplest mathematical model is presented that has an impulse-impulse solution; we also show that a non-isolated singular point in the ordinary differential equation (ODE) wave system implies existence of free-boundary fronts. The results can be used for construction and analysis of different mathematical models describing systems with chemotaxis.
Small Worlds: Strong Clustering in Wireless Networks
Venue: arXiv cs.NI 2007
Year: 2007

Small-worlds represent efficient communication networks that obey two distinguishing characteristics: a high clustering coefficient together with a small characteristic path length. This paper focuses on an interesting paradox, that removing links in a network can increase the overall clustering coefficient. Reckful Roaming, as introduced in this paper, is a 2-localized algorithm that takes advantage of this paradox in order to selectively remove superfluous links, this way optimizing the clustering coefficient while still retaining a sufficiently small characteristic path length.
Localized Support for Injection Point Election in Hybrid Networks
Venue: arXiv cs.DC 2007
Year: 2007

Ad-hoc networks, a promising trend in wireless technology, fail to work properly in a global setting. In most cases, self-organization and cost-free local communication cannot compensate the need for being connected, gathering urgent information just-in-time. Equipping mobile devices additionally with GSM or UMTS adapters in order to communicate with arbitrary remote devices or even a fixed network infrastructure provides an opportunity. Devices that operate as intermediate nodes between the ad-hoc network and a reliable backbone network are potential injection points. They allow disseminating received information within the local neighborhood. The effectiveness of different devices to serve as injection point differs substantially. For practical reasons the determination of injection points should be done locally, within the ad-hoc network partitions. We analyze different localized algorithms using at most 2-hop neighboring information. Results show that devices selected this way spread information more efficiently through the ad-hoc network. Our results can also be applied in order to support the election process for clusterheads in the field of clustering mechanisms.
A taxonomic Approach to Topology Control in Ad-hoc and Wireless Networks
Venue: arXiv cs.NI 2007
Year: 2007

Topology Control (TC) aims at tuning the topology of highly dynamic networks to provide better control over network resources and to increase the efficiency of communication. Recently, many TC protocols have been proposed. The protocols are designed for preserving connectivity, minimizing energy consumption, maximizing the overall network coverage or network capacity. Each TC protocol makes different assumptions about the network topology, environment detection resources, and control capacities. This circumstance makes it extremely difficult to comprehend the role and purpose of each protocol. To tackle this situation, a taxonomy for TC protocols is presented throughout this paper. Additionally, some TC protocols are classified based upon this taxonomy.
Opportunistic Network Coding for Video Streaming over Wireless
Venue: arXiv cs.NI 2007
Year: 2007

In this paper, we study video streaming over wireless networks with network coding capabilities. We build upon recent work, which demonstrated that network coding can increase throughput over a broadcast medium, by mixing packets from different flows into a single packet, thus increasing the information content per transmission. Our key insight is that, when the transmitted flows are video streams, network codes should be selected so as to maximize not only the network throughput but also the video quality. We propose video-aware opportunistic network coding schemes that take into account both (i) the decodability of network codes by several receivers and (ii) the importance and deadlines of video packets. Simulation results show that our schemes significantly improve both video quality and throughput.
Dualheap Selection Algorithm: Efficient, Inherently Parallel and Somewhat Mysterious
Venue: arXiv cs.DS 2007
Year: 2007

An inherently parallel algorithm is proposed that efficiently performs selection: finding the K-th largest member of a set of N members. Selection is a common component of many more complex algorithms and therefore is a widely studied problem. Not much is new in the proposed dualheap selection algorithm: the heap data structure is from J.W.J.Williams, the bottom-up heap construction is from R.W. Floyd, and the concept of a two heap data structure is from J.W.J. Williams and D.E. Knuth. The algorithm's novelty is limited to a few relatively minor implementation twists: 1) the two heaps are oriented with their roots at the partition values rather than at the minimum and maximum values, 2)the coding of one of the heaps (the heap of smaller values) employs negative indexing, and 3) the exchange phase of the algorithm is similar to a bottom-up heap construction, but navigates the heap with a post-order tree traversal. When run on a single processor, the dualheap selection algorithm's performance is competitive with quickselect with median estimation, a common variant of C.A.R. Hoare's quicksort algorithm. When run on parallel processors, the dualheap selection algorithm is superior due to its subtasks that are easily partitioned and innately balanced.
A Survey of Unix Init Schemes
Venue: arXiv cs.OS 2007
Year: 2007

In most modern operating systems, init (as in "initialization") is the program launched by the kernel at boot time. It runs as a daemon and typically has PID 1. Init is responsible for spawning all other processes and scavenging zombies. It is also responsible for reboot and shutdown operations. This document describes existing solutions that implement the init process and/or init scripts in Unix-like systems. These solutions range from the legacy and still-in-use BSD and SystemV schemes, to recent and promising schemes from Ubuntu, Apple, Sun and independent developers. Our goal is to highlight their focus and compare their sets of features.
Extraction d'entités dans des collections évolutives
Venue: arXiv cs.IR 2007
Year: 2007

The goal of our work is to use a set of reports and extract named entities, in our case the names of Industrial or Academic partners. Starting with an initial list of entities, we use a first set of documents to identify syntactic patterns that are then validated in a supervised learning phase on a set of annotated documents. The complete collection is then explored. This approach is similar to the ones used in data extraction from semi-structured documents (wrappers) and do not need any linguistic resources neither a large set for training. As our collection of documents would evolve over years, we hope that the performance of the extraction would improve with the increased size of the training set.
Hypocomputation
Venue: arXiv cs.OH 2007
Year: 2007

Hypercomputational formal theories will, clearly, be both structurally and foundationally different from the formal theories underpinning computational theories. However, many of the maps that might guide us into this strange realm have been lost. So little work has been done recently in the area of metamathematics, and so many of the previous results have been folded into other theories, that we are in danger of loosing an appreciation of the broader structure of formal theories. As an aid to those looking to develop hypercomputational theories, we will briefly survey the known landmarks both inside and outside the borders of computational theory. We will not focus in this paper on why the structure of formal theory looks the way it does. Instead we will focus on what this structure looks like, moving from hypocomputational, through traditional computational theories, and then beyond to hypercomputational theories.
Scale-sensitive Psi-dimensions: the Capacity Measures for Classifiers Taking Values in R^Q
Venue: arXiv cs.LG 2007
Year: 2007

Bounds on the risk play a crucial role in statistical learning theory. They usually involve as capacity measure of the model studied the VC dimension or one of its extensions. In classification, such "VC dimensions" exist for models taking values in {0, 1}, {1,..., Q} and R. We introduce the generalizations appropriate for the missing case, the one of models with values in R^Q. This provides us with a new guaranteed risk for M-SVMs which appears superior to the existing one.
Self-Stabilizing Wavelets and r-Hops Coordination
Venue: arXiv cs.DC 2007
Year: 2007

We introduce a simple tool called the wavelet (or, r-wavelet) scheme. Wavelets deals with coordination among processes which are at most r hops away of each other. We present a selfstabilizing solution for this scheme. Our solution requires no underlying structure and works in arbritrary anonymous networks, i.e., no process identifier is required. Moreover, our solution works under any (even unfair) daemon. Next, we use the wavelet scheme to design self-stabilizing layer clocks. We show that they provide an efficient device in the design of local coordination problems at distance r, i.e., r-barrier synchronization and r-local resource allocation (LRA) such as r-local mutual exclusion (LME), r-group mutual exclusion (GME), and r-Reader/Writers. Some solutions to the r-LRA problem (e.g., r-LME) also provide transformers to transform algorithms written assuming any r-central daemon into algorithms working with any distributed daemon.
PSPACE Bounds for Rank-1 Modal Logics
Venue: arXiv cs.LO 2007
Year: 2007

For lack of general algorithmic methods that apply to wide classes of logics, establishing a complexity bound for a given modal logic is often a laborious task. The present work is a step towards a general theory of the complexity of modal logics. Our main result is that all rank-1 logics enjoy a shallow model property and thus are, under mild assumptions on the format of their axiomatisation, in PSPACE. This leads to a unified derivation of tight PSPACE-bounds for a number of logics including K, KD, coalition logic, graded modal logic, majority logic, and probabilistic modal logic. Our generic algorithm moreover finds tableau proofs that witness pleasant proof-theoretic properties including a weak subformula property. This generality is made possible by a coalgebraic semantics, which conveniently abstracts from the details of a given model class and thus allows covering a broad range of logics in a uniform way.
Directed Feedback Vertex Set is Fixed-Parameter Tractable
Venue: arXiv cs.DS 2007
Year: 2007

We resolve positively a long standing open question regarding the fixed-parameter tractability of the parameterized Directed Feedback Vertex Set problem. In particular, we propose an algorithm which solves this problem in $O(8^kk!*poly(n))$.
Scuba Search : when selection meets innovation
Venue: arXiv cs.NE 2007
Year: 2007

We proposed a new search heuristic using the scuba diving metaphor. This approach is based on the concept of evolvability and tends to exploit neutrality in fitness landscape. Despite the fact that natural evolution does not directly select for evolvability, the basic idea behind the scuba search heuristic is to explicitly push the evolvability to increase. The search process switches between two phases: Conquest-of-the-Waters and Invasion-of-the-Land. A comparative study of the new algorithm and standard local search heuristics on the NKq-landscapes has shown advantage and limit of the scuba search. To enlighten qualitative differences between neutral search processes, the space is changed into a connected graph to visualize the pathways that the search is likely to follow.
Optimal Solutions for Sparse Principal Component Analysis
Venue: arXiv cs.AI 2007
Year: 2007

Given a sample covariance matrix, we examine the problem of maximizing the variance explained by a linear combination of the input variables while constraining the number of nonzero coefficients in this combination. This is known as sparse principal component analysis and has a wide array of applications in machine learning and engineering. We formulate a new semidefinite relaxation to this problem and derive a greedy algorithm that computes a full set of good solutions for all target numbers of non zero coefficients, with total complexity O(n^3), where n is the number of variables. We then use the same relaxation to derive sufficient conditions for global optimality of a solution, which can be tested in O(n^3) per pattern. We discuss applications in subset selection and sparse recovery and show on artificial examples and biological data that our algorithm does provide globally optimal solutions in many cases.