Search results for "Theoretical Computer Science"
showing 10 items of 1151 documents
Fast nonstationary preconditioned iterative methods for ill-posed problems, with application to image deblurring
2013
We introduce a new iterative scheme for solving linear ill-posed problems, similar to nonstationary iterated Tikhonov regularization, but with an approximation of the underlying operator to be used for the Tikhonov equations. For image deblurring problems, such an approximation can be a discrete deconvolution that operates entirely in the Fourier domain. We provide a theoretical analysis of the new scheme, using regularization parameters that are chosen by a certain adaptive strategy. The numerical performance of this method turns out to be superior to state-of-the-art iterative methods, including the conjugate gradient iteration for the normal equation, with and without additional precondi…
Distance measures for biological sequences: Some recent approaches
2008
AbstractSequence comparison has become a very essential tool in modern molecular biology. In fact, in biomolecular sequences high similarity usually implies significant functional or structural similarity. Traditional approaches use techniques that are based on sequence alignment able to measure character level differences. However, the recent developments of whole genome sequencing technology give rise to need of similarity measures able to capture the rearrangements involving large segments contained in the sequences. This paper is devoted to illustrate different methods recently introduced for the alignment-free comparison of biological sequences. Goal of the paper is both to highlight t…
Domain Specific Knowledge Representation for an Intelligent Tutoring System to Teach Algebraic Reasoning
2012
Translation of word problems into symbolic notation is one of the most challenging steps in learning the algebraic method. This paper describes a domain-specific knowledge representation mechanism to support Intelligent Tutoring Systems (ITS) which focus on this stage of the problem solving process. The description language proposed is based on the concept of a hypergraph and makes it possible to simultaneously a) represent all potential algebraic solutions to a given word problem; b) keep track of the student's actions; c) provide automatic remediation; and d) unequivocally determine the current state of the resolution process. An experimental evaluation with students at a public school su…
PTNet: An efficient and green data center network
2017
International audience; In recent years, data centers have witnessed an exponential growth for hosting hundreds of thousands of servers as well as to accommodating a very large demand for resources. To fulfill the required level of demand, some approaches tackled network aspects so to host a huge number of servers while others focused on delivering rapid services to the clients by minimizing the path length between any two servers. In general, network devices are often designed to achieve 1:1 oversubscription. Alternatively, in a realistic data center environment, the average utilization of a network could vary between 5% and 25%, and thus the energy consumed by idle devices is wasted. This…
Relating RSS News/Items
2009
Merging related RSS news (coming from one or different sources) is beneficial for end-users with different backgrounds (journalists, economists, etc.), particularly those accessing similar information. In this paper, we provide a practical approach to both: measure the relatedness, and identify relationships between RSS elements. Our approach is based on the concepts of semantic neighborhood and vector space model, and considers the content and structure of RSS news items. © 2009 Springer Berlin Heidelberg.
RDF2SPIN: Mapping Semantic Graphs to SPIN Model Checker
2011
International audience; The most frequently used language to represent the semantic graphs is the RDF (W3C standard for meta-modeling). The construction of semantic graphs is a source of numerous errors of interpretation. The processing of large semantic graphs is a limit to the use of semantics in current information systems. The work presented in this paper is part of a new research at the border between two areas: the semantic web and the model checking. For this, we developed a tool, RDF2SPIN, which converts RDF graphs into SPIN language. This conversion aims checking the semantic graphs with the model checker SPIN in order to verify the consistency of the data. To illustrate our propos…
The pure descent statistic on permutations
2017
International audience; We introduce a new statistic based on permutation descents which has a distribution given by the Stirling numbers of the first kind, i.e., with the same distribution as for the number of cycles in permutations. We study this statistic on the sets of permutations avoiding one pattern of length three by giving bivariate generating functions. As a consequence, new classes of permutations enumerated by the Motzkin numbers are obtained. Finally, we deduce results about the popularity of the pure descents in all these restricted sets. (C) 2017 Elsevier B.V. All rights reserved.
The dual and the double of a Hopf algebroid are Hopf algebroids
2017
Let $H$ be a $\times$-bialgebra in the sense of Takeuchi. We show that if $H$ is $\times$-Hopf, and if $H$ fulfills the finiteness condition necessary to define its skew dual $H^\vee$, then the coopposite of the latter is $\times$-Hopf as well. If in addition the coopposite $\times$-bialgebra of $H$ is $\times$-Hopf, then the coopposite of the Drinfeld double of $H$ is $\times$-Hopf, as is the Drinfeld double itself, under an additional finiteness condition.
Quantum Cellular Automata: a Short Overview of Molecular Problem
2018
International audience
Some Computational Aspects of DISTANCE-SAT
2007
In many AI fields, one must face the problem of finding a solution that is as close as possible to a given configuration. This paper addresses this problem in a propositional framework. We introduce the decision problem distance-sat, which consists in determining whether a propositional formula admits a model that disagrees with a given partial interpretation on at most d variables. The complexity of distance-sat and of several restrictions of it are identified. Two algorithms based on the well-known Davis/Logemann/Loveland search procedure for the satisfiability problem sat are presented so as to solve distance-sat for CNF formulas. Their computational behaviors are compared with the ones …