Search results for " Computer Science"
showing 10 items of 3983 documents
Predictive and Evolutive Cross-Referencing for Web Textual Sources
2017
International audience; One of the main challenges in the domain of competitive intelligence is to harness important volumes of information from the web, and extract the most valuable pieces of information. As the amount of information available on the web grows rapidly and is very heterogeneous, this process becomes overwhelming for experts. To leverage this challenge, this paper presents a vision for a novel process that performs cross-referencing at web scale. This process uses a focused crawler and a semantic-based classifier to cross-reference textual items without expert intervention, based on Big Data and Semantic Web technologies. The system is described thoroughly, and interests of…
Digital information receiver based on stochastic resonance
2003
International audience; An electronic receiver based on stochastic resonance is presented to rescue subthreshold modulated digital data. In real experiment, it is shown that a complete data restoration is achieved for both uniform and Gaussian white noise.
K4-free Graphs as a Free Algebra
2017
International audience; Graphs of treewidth at most two are the ones excluding the clique with four vertices (K4) as a minor, or equivalently, the graphs whose biconnected components are series-parallel. We turn those graphs into a finitely presented free algebra, answering positively a question by Courcelle and Engelfriet, in the case of treewidth two. First we propose a syntax for denoting these graphs: in addition to parallel composition and series composition, it suffices to consider the neutral elements of those operations and a unary transpose operation. Then we give a finite equational presentation and we prove it complete: two terms from the syntax are congruent if and only if they …
Learning with belief levels
2008
AbstractWe study learning of predicate logics formulas from “elementary facts,” i.e. from the values of the predicates in the given model. Several models of learning are considered, but most of our attention is paid to learning with belief levels. We propose an axiom system which describes what we consider to be a human scientist's natural behavior when trying to explore these elementary facts. It is proved that no such system can be complete. However we believe that our axiom system is “practically” complete. Theorems presented in the paper in some sense confirm our hypothesis.
On the inductive inference of recursive real-valued functions
1999
AbstractWe combine traditional studies of inductive inference and classical continuous mathematics to produce a study of learning real-valued functions. We consider two possible ways to model the learning by example of functions with domain and range the real numbers. The first approach considers functions as represented by computable analytic functions. The second considers arbitrary computable functions of recursive real numbers. In each case we find natural examples of learnable classes of functions and unlearnable classes of functions.
Boolean Functions with a Low Polynomial Degree and Quantum Query Algorithms
2005
The complexity of quantum query algorithms computing Boolean functions is strongly related to the degree of the algebraic polynomial representing this Boolean function. There are two related difficult open problems. First, Boolean functions are sought for which the complexity of exact quantum query algorithms is essentially less than the complexity of deterministic query algorithms for the same function. Second, Boolean functions are sought for which the degree of the representing polynomial is essentially less than the complexity of deterministic query algorithms. We present in this paper new techniques to solve the second problem.
Counting by Statistics on Search Trees: Application to Constraint Satisfaction Problems
1997
In 1975, Knuth proposed a simple statistical method for investigating search trees. We use this technique for estimating the number of solutions of constraint satisfaction problem CSP and boolean satisfiability problem SAT instances. We show that, depending on domain reductions, tree-based estimates have a lower variance than estimates based on uniform sampling from the search space. Nevertheless, because the variance remains extremely high in the general case, a confidence interval cannot be derived, but a lower bound of the number of solutions. These results are confirmed by many experiments.
Codification schemes and finite automata
2000
This paper is a note on how Information Theory and Codification Theory are helpful in the computational design both of communication protocols and strategy sets in the framework of finitely repeated games played by boundedly rational agents. More precisely, we show the usefulness of both theories to improve the existing automata bounds of Neyman¿s (1998) work on finitely repeated games played by finite automata.
Backbone Extraction of Weighted Modular Complex Networks based on their Component Structure
2023
This work introduces a generic backbone extraction framework exploiting the mesoscopic network structure. Indeed, numerous real-world networks are made of dense groups of nodes called communities, multi-core or local components. To deal with these groups' heterogeneity, we propose to extract the backbones independently from their various components and fuse them. Experimental investigations on real-world networks demonstrate the effectiveness of the proposed approach compared to the classical techniques' agnostic of the mesoscopic structure of real-world networks.
Linear-size suffix tries
2016
Suffix trees are highly regarded data structures for text indexing and string algorithms [MCreight 76, Weiner 73]. For any given string w of length n = | w | , a suffix tree for w takes O ( n ) nodes and links. It is often presented as a compacted version of a suffix trie for w, where the latter is the trie (or digital search tree) built on the suffixes of w. Here the compaction process replaces each maximal chain of unary nodes with a single arc. For this, the suffix tree requires that the labels of its arcs are substrings encoded as pointers to w (or equivalent information). On the contrary, the arcs of the suffix trie are labeled by single symbols but there can be Θ ( n 2 ) nodes and lin…