OpenRaiser/Intern-Atlas huggingface dataset:
A branch-and-bound feature selection algorithm for U-shaped cost functions
Venue: arXiv cs.CV 2008
Year: 2008

This paper presents the formulation of a combinatorial optimization problem with the following characteristics: i.the search space is the power set of a finite set structured as a Boolean lattice; ii.the cost function forms a U-shaped curve when applied to any lattice chain. This formulation applies for feature selection in the context of pattern recognition. The known approaches for this problem are branch-and-bound algorithms and heuristics, that explore partially the search space. Branch-and-bound algorithms are equivalent to the full search, while heuristics are not. This paper presents a branch-and-bound algorithm that differs from the others known by exploring the lattice structure and the U-shaped chain curves of the search space. The main contribution of this paper is the architecture of this algorithm that is based on the representation and exploration of the search space by new lattice properties proven here. Several experiments, with well known public data, indicate the superiority of the proposed method to SFFS, which is a popular heuristic that gives good results in very short computational time. In all experiments, the proposed method got better or equal results in similar or even smaller computational time.
Detection of parallel steps in programs with arrays
Venue: arXiv cs.PL 2008
Year: 2008

The problem of detecting of information and logically independent (DILD) steps in programs is a key for equivalent program transformations. Here we are considering the problem of independence of loop iterations, the concentration of massive data processing and hence the most challenge construction for parallelizing. We introduced a separated form of loops when loop's body is a sequence of procedures each of them are used array's elements selected in a previous procedure. We prove that any loop may be algorithmically represented in this form and number of such procedures is invariant. We show that for this form of loop the steps connections are determined with some integer equations and hence the independence problem is algorithmically unsolvable if index expressions are more complex than cubical. We suggest a modification of index semantics that made connection equations trivial and loops iterations can be executed in parallel.
Complete Identification of a Dynamic Fractional Order System Under Non-ideal Conditions Using Fractional Differintegral Definitions
Venue: arXiv cs.OH 2008
Year: 2008

This contribution deals with identification of fractional-order dynamical systems. System identification, which refers to estimation of process parameters, is a necessity in control theory. Real processes are usually of fractional order as opposed to the ideal integral order models. A simple and elegant scheme of estimating the parameters for such a fractional order process is proposed. This method employs fractional calculus theory to find equations relating the parameters that are to be estimated, and then estimates the process parameters after solving the simultaneous equations. The data used for the calculations are intentionally corrupted to simulate real-life conditions. Results show that the proposed scheme offers a very high degree of accuracy even for erroneous data.
Cooperative interface of a swarm of UAVs
Venue: arXiv cs.AI 2008
Year: 2008

After presenting the broad context of authority sharing, we outline how introducing more natural interaction in the design of the ground operator interface of UV systems should help in allowing a single operator to manage the complexity of his/her task. Introducing new modalities is one one of the means in the realization of our vision of next- generation GOI. A more fundamental aspect resides in the interaction manager which should help balance the workload of the operator between mission and interaction, notably by applying a multi-strategy approach to generation and interpretation. We intend to apply these principles to the context of the Smaart prototype, and in this perspective, we illustrate how to characterize the workload associated with a particular operational situation.
On the Cramer-Rao Lower Bound for Frequency Correlation Matrices of Doubly Selective Fading Channels for OFDM Systems
Venue: arXiv cs.IT 2008
Year: 2008

The analytic expression of CRLB and the maximum likelihood estimator for the sample frequency correlation matrices in doubly selective fading channels for OFDM systems are reported in this paper. According to the analytical and numerical results, the amount of samples affects the average mean square error dominantly while the SNR and the Doppler spread do negligibly.
Instruction sequences for the production of processes
Venue: arXiv cs.PL 2008
Year: 2008

Single-pass instruction sequences under execution are considered to produce behaviours to be controlled by some execution environment. Threads as considered in thread algebra model such behaviours: upon each action performed by a thread, a reply from its execution environment determines how the thread proceeds. Threads in turn can be looked upon as producing processes as considered in process algebra. We show that, by apposite choice of basic instructions, all processes that can only be in a finite number of states can be produced by single-pass instruction sequences.
Optimization of automatically generated multi-core code for the LTE RACH-PD algorithm
Venue: arXiv cs.MM 2008
Year: 2008

Embedded real-time applications in communication systems require high processing power. Manual scheduling devel-oped for single-processor applications is not suited to multi-core architectures. The Algorithm Architecture Matching (AAM) methodology optimizes static application implementation on multi-core architectures. The Random Access Channel Preamble Detection (RACH-PD) is an algorithm for non-synchronized access of Long Term Evolu-tion (LTE) wireless networks. LTE aims to improve the spectral efficiency of the next generation cellular system. This paper de-scribes a complete methodology for implementing the RACH-PD. AAM prototyping is applied to the RACH-PD which is modelled as a Synchronous DataFlow graph (SDF). An efficient implemen-tation of the algorithm onto a multi-core DSP, the TI C6487, is then explained. Benchmarks for the solution are given.
Query Refinement by Multi Word Term expansions and semantic synonymy
Venue: arXiv cs.IR 2008
Year: 2008

We developed a system, TermWatch (https://stid-bdd.iut.univ-metz.fr/TermWatch/index.pl), which combines a linguistic extraction of terms, their structuring into a terminological network with a clustering algorithm. In this paper we explore its ability in integrating the most promising aspects of the studies on query refinement: choice of meaningful text units to cluster (domain terms), choice of tight semantic relations with which to cluster terms, structuring of terms in a network enabling abetter perception of domain concepts. We have run this experiment on the 367 645 English abstracts of PASCAL 2005-2006 bibliographic database (http://www.inist.fr) and compared the structured terminological resource automatically build by TermWarch to the English segment of TermScience resource (http://termsciences.inist.fr/) containing 88 211 terms.
A Note on the Inversion Complexity of Boolean Functions in Boolean Formulas
Venue: arXiv cs.CC 2008
Year: 2008

In this note, we consider the minimum number of NOT operators in a Boolean formula representing a Boolean function. In circuit complexity theory, the minimum number of NOT gates in a Boolean circuit computing a Boolean function $f$ is called the inversion complexity of $f$. In 1958, Markov determined the inversion complexity of every Boolean function and particularly proved that $\lceil \log_2(n+1) \rceil$ NOT gates are sufficient to compute any Boolean function on $n$ variables. As far as we know, no result is known for inversion complexity in Boolean formulas, i.e., the minimum number of NOT operators in a Boolean formula representing a Boolean function. The aim of this note is showing that we can determine the inversion complexity of every Boolean function in Boolean formulas by arguments based on the study of circuit complexity.
Distributed Algorithms for Computing Alternate Paths Avoiding Failed Nodes and Links
Venue: arXiv cs.DC 2008
Year: 2008

A recent study characterizing failures in computer networks shows that transient single element (node/link) failures are the dominant failures in large communication networks like the Internet. Thus, having the routing paths globally recomputed on a failure does not pay off since the failed element recovers fairly quickly, and the recomputed routing paths need to be discarded. In this paper, we present the first distributed algorithm that computes the alternate paths required by some "proactive recovery schemes" for handling transient failures. Our algorithm computes paths that avoid a failed node, and provides an alternate path to a particular destination from an upstream neighbor of the failed node. With minor modifications, we can have the algorithm compute alternate paths that avoid a failed link as well. To the best of our knowledge all previous algorithms proposed for computing alternate paths are centralized, and need complete information of the network graph as input to the algorithm.
Secrecy in Cooperative Relay Broadcast Channels
Venue: arXiv cs.IT 2008
Year: 2008

We investigate the effects of user cooperation on the secrecy of broadcast channels by considering a cooperative relay broadcast channel. We show that user cooperation can increase the achievable secrecy region. We propose an achievable scheme that combines Marton's coding scheme for broadcast channels and Cover and El Gamal's compress-and-forward scheme for relay channels. We derive outer bounds for the rate-equivocation region using auxiliary random variables for single-letterization. Finally, we consider a Gaussian channel and show that both users can have positive secrecy rates, which is not possible for scalar Gaussian broadcast channels without cooperation.
The Expressive Power of Binary Submodular Functions
Venue: arXiv cs.DM 2008
Year: 2008

It has previously been an open problem whether all Boolean submodular functions can be decomposed into a sum of binary submodular functions over a possibly larger set of variables. This problem has been considered within several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. Using a connection between the expressive power of valued constraints and certain algebraic properties of functions, we answer this question negatively. Our results have several corollaries. First, we characterise precisely which submodular functions of arity 4 can be expressed by binary submodular functions. Next, we identify a novel class of submodular functions of arbitrary arities which can be expressed by binary submodular functions, and therefore minimised efficiently using a so-called expressibility reduction to the Min-Cut problem. More importantly, our results imply limitations on this kind of reduction and establish for the first time that it cannot be used in general to minimise arbitrary submodular functions. Finally, we refute a conjecture of Promislow and Young on the structure of the extreme rays of the cone of Boolean submodular functions.
Collaborative process control: Observation of tracks generated by PLM system
Venue: arXiv cs.SE 2008
Year: 2008

This paper aims at analyzing the problems related to collaborative work using a PLM system. This research is mainly focused on the organisational aspects of SMEs involved in networks composed of large companies, subcontractors and other industrial partners. From this analysis, we propose the deployment of an approach based on an observation process of tracks generated by PLM system. The specific contributions are of two fold. First is to identify the brake points of collaborative work. The second, thanks to the exploitation of generated tracks, it allows reducing risks by reacting in real time to the incidents or dysfunctions that may occur. The overall system architecture based on services technology and supporting the proposed approach is described, as well as associated prototype developed using an industrial PLM system.
Characterization and collection of information from heterogeneous multimedia sources with users' parameters for decision support
Venue: arXiv cs.MM 2008
Year: 2008

No single information source can be good enough to satisfy the divergent and dynamic needs of users all the time. Integrating information from divergent sources can be a solution to deficiencies in information content. We present how Information from multimedia document can be collected based on associating a generic database to a federated database. Information collected in this way is brought into relevance by integrating the parameters of usage and user's parameter for decision making. We identified seven different classifications of multimedia document.
Coalgebraic Automata Theory: Basic Results
Venue: arXiv cs.LO 2008
Year: 2008

We generalize some of the central results in automata theory to the abstraction level of coalgebras and thus lay out the foundations of a universal theory of automata operating on infinite objects. Let F be any set functor that preserves weak pullbacks. We show that the class of recognizable languages of F-coalgebras is closed under taking unions, intersections, and projections. We also prove that if a nondeterministic F-automaton accepts some coalgebra it accepts a finite one of the size of the automaton. Our main technical result concerns an explicit construction which transforms a given alternating F-automaton into an equivalent nondeterministic one, whose size is exponentially bound by the size of the original automaton.
Land Cover Mapping Using Ensemble Feature Selection Methods
Venue: arXiv cs.LG 2008
Year: 2008

Ensemble classification is an emerging approach to land cover mapping whereby the final classification output is a result of a consensus of classifiers. Intuitively, an ensemble system should consist of base classifiers which are diverse i.e. classifiers whose decision boundaries err differently. In this paper ensemble feature selection is used to impose diversity in ensembles. The features of the constituent base classifiers for each ensemble were created through an exhaustive search algorithm using different separability indices. For each ensemble, the classification accuracy was derived as well as a diversity measure purported to give a measure of the inensemble diversity. The correlation between ensemble classification accuracy and diversity measure was determined to establish the interplay between the two variables. From the findings of this paper, diversity measures as currently formulated do not provide an adequate means upon which to constitute ensembles for land cover mapping.
Disjunctive Databases for Representing Repairs
Venue: arXiv cs.DB 2008
Year: 2008

This paper addresses the problem of representing the set of repairs of a possibly inconsistent database by means of a disjunctive database. Specifically, the class of denial constraints is considered. We show that, given a database and a set of denial constraints, there exists a (unique) disjunctive database, called canonical, which represents the repairs of the database w.r.t. the constraints and is contained in any other disjunctive database with the same set of minimal models. We propose an algorithm for computing the canonical disjunctive database. Finally, we study the size of the canonical disjunctive database in the presence of functional dependencies for both repairs and cardinality-based repairs.
Dynamic External Hashing: The Limit of Buffering
Venue: arXiv cs.DS 2008
Year: 2008

Hash tables are one of the most fundamental data structures in computer science, in both theory and practice. They are especially useful in external memory, where their query performance approaches the ideal cost of just one disk access. Knuth gave an elegant analysis showing that with some simple collision resolution strategies such as linear probing or chaining, the expected average number of disk I/Os of a lookup is merely $1+1/2^{Ω(b)}$, where each I/O can read a disk block containing $b$ items. Inserting a new item into the hash table also costs $1+1/2^{Ω(b)}$ I/Os, which is again almost the best one can do if the hash table is entirely stored on disk. However, this assumption is unrealistic since any algorithm operating on an external hash table must have some internal memory (at least $Ω(1)$ blocks) to work with. The availability of a small internal memory buffer can dramatically reduce the amortized insertion cost to $o(1)$ I/Os for many external memory data structures. In this paper we study the inherent query-insertion tradeoff of external hash tables in the presence of a memory buffer. In particular, we show that for any constant $c>1$, if the query cost is targeted at $1+O(1/b^{c})$ I/Os, then it is not possible to support insertions in less than $1-O(1/b^{\frac{c-1}{4}})$ I/Os amortized, which means that the memory buffer is essentially useless. While if the query cost is relaxed to $1+O(1/b^{c})$ I/Os for any constant $c<1$, there is a simple dynamic hash table with $o(1)$ insertion cost. These results also answer the open question recently posed by Jensen and Pagh.
Binar Shuffle Algorithm: Shuffling Bit by Bit
Venue: arXiv cs.DS 2008
Year: 2008

Frequently, randomly organized data is needed to avoid an anomalous operation of other algorithms and computational processes. An analogy is that a deck of cards is ordered within the pack, but before a game of poker or solitaire the deck is shuffled to create a random permutation. Shuffling is used to assure that an aggregate of data elements for a sequence S is randomly arranged, but avoids an ordered or partially ordered permutation. Shuffling is the process of arranging data elements into a random permutation. The sequence S as an aggregation of N data elements, there are N! possible permutations. For the large number of possible permutations, two of the possible permutations are for a sorted or ordered placement of data elements--both an ascending and descending sorted permutation. Shuffling must avoid inadvertently creating either an ascending or descending permutation. Shuffling is frequently coupled to another algorithmic function -- pseudo-random number generation. The efficiency and quality of the shuffle is directly dependent upon the random number generation algorithm utilized. A more effective and efficient method of shuffling is to use parameterization to configure the shuffle, and to shuffle into sub-arrays by utilizing the encoding of the data elements. The binar shuffle algorithm uses the encoding of the data elements and parameterization to avoid any direct coupling to a random number generation algorithm, but still remain a linear O(N) shuffle algorithm.
Extractors and an efficient variant of Muchnik's theorem
Venue: arXiv cs.CC 2008
Year: 2008

Muchnik's theorem about simple conditional descriprion states that for all words $a$ and $b$ there exists a short program $p$ transforming $a$ to $b$ that has the least possible length and is simple conditional on $b$. This paper presents a new proof of this theorem, based on extractors. Employing the extractor technique, two new versions of Muchnik's theorem for space- and time-bounded Kolmogorov complexity are proven.
ELASTICITY: Topological Characterization of Robustness in Complex Networks
Venue: arXiv cs.NI 2008
Year: 2008

Just as a herd of animals relies on its robust social structure to survive in the wild, similarly robustness is a crucial characteristic for the survival of a complex network under attack. The capacity to measure robustness in complex networks defines the resolve of a network to maintain functionality in the advent of classical component failures and at the onset of cryptic malicious attacks. To date, robustness metrics are deficient and unfortunately the following dilemmas exist: accurate models necessitate complex analysis while conversely, simple models lack applicability to our definition of robustness. In this paper, we define robustness and present a novel metric, elasticity- a bridge between accuracy and complexity-a link in the chain of network robustness. Additionally, we explore the performance of elasticity on Internet topologies and online social networks, and articulate results.
Anti Plagiarism Application with Algorithm Karp-Rabin at Thesis in Gunadarma University
Venue: arXiv cs.IT 2008
Year: 2008

Plagiarism that is plagiarizing or composition retrieval, opinion, etcetera from other people and makes it is likely composition and opinion him-self. Plagiarism can be considered to be crime because stealing others copyrights. Like action a student copying some part of writings without valid permission from the original writer. In education world, plagiarism perpetrator can get the devil to pay from school/university. Plagiarism perpetrator conceived of plagiator. This thing is possible unable to be paid attention by the side of campus because of limitation from some interconnected factors for example student amounts Gunadarma University reaching thousands and incommensurate to tester amounts or lecturer the side of campus in charge directs problem thesis. In this paper, an application have been developed in order to check and look for 5 type percentage similarity from a thesis with other one at certain part or chapters. Percentage got that is 0%, under 15%, between 15-50%, up to 50% and 100%. So it should be expected that the results could be used by thesis advisor and also thesis examiner from the Student at Gunadarma University.
Revisiting the Core Ontology and Problem in Requirements Engineering
Venue: arXiv cs.SE 2008
Year: 2008

In their seminal paper in the ACM Transactions on Software Engineering and Methodology, Zave and Jackson established a core ontology for Requirements Engineering (RE) and used it to formulate the "requirements problem", thereby defining what it means to successfully complete RE. Given that stakeholders of the system-to-be communicate the information needed to perform RE, we show that Zave and Jackson's ontology is incomplete. It does not cover all types of basic concerns that the stakeholders communicate. These include beliefs, desires, intentions, and attitudes. In response, we propose a core ontology that covers these concerns and is grounded in sound conceptual foundations resting on a foundational ontology. The new core ontology for RE leads to a new formulation of the requirements problem that extends Zave and Jackson's formulation. We thereby establish new standards for what minimum information should be represented in RE languages and new criteria for determining whether RE has been successfully completed.