Search results for "Theoretical Computer Science"
showing 10 items of 1151 documents
A New Combinatorial Approach to Sequence Comparison
2008
In this paper we introduce a new alignment-free method for comparing sequences which is combinatorial by nature and does not use any compressor nor any information-theoretic notion. Such a method is based on an extension of the Burrows-Wheeler Transform, a transformation widely used in the context of Data Compression. The new extended transformation takes as input a multiset of sequences and produces as output a string obtained by a suitable rearrangement of the characters of all the input sequences. By using such a transformation we give a general method for comparing sequences that takes into account how much the characters coming from the different input sequences are mixed in the output…
MuTE: a MATLAB toolbox to compare established and novel estimators of the multivariate transfer entropy.
2014
A challenge for physiologists and neuroscientists is to map information transfer between components of the systems that they study at different scales, in order to derive important knowledge on structure and function from the analysis of the recorded dynamics. The components of physiological networks often interact in a nonlinear way and through mechanisms which are in general not completely known. It is then safer that the method of choice for analyzing these interactions does not rely on any model or assumption on the nature of the data and their interactions. Transfer entropy has emerged as a powerful tool to quantify directed dynamical interactions. In this paper we compare different ap…
A Grid Enabled Parallel Hybrid Genetic Algorithm for SPN
2004
This paper presents a combination of a parallel Genetic Algorithm (GA) and a local search methodology for the Steiner Problem in Networks (SPN). Several previous papers have proposed the adoption of GAs and others metaheuristics to solve the SPN demonstrating the validity of their approaches. This work differs from them for two main reasons: the dimension and the features of the networks adopted in the experiments and the aim from which it has been originated. The reason that aimed this work was namely to assess deterministic and computationally inexpensive algorithms which can be used in practical engineering applications, such as the multicast transmission in the Internet. The large dimen…
Quantum Finite One-Counter Automata
1999
In this paper the notion of quantum finite one-counter automata (QF1CA) is introduced. Introduction of the notion is similar to that of the 2-way quantum finite state automata in [1]. The well-formedness conditions for the automata are specified ensuring unitarity of evolution. A special kind of QF1CA, called simple, that satisfies the well-formedness conditions is introduced. That allows specify rules for constructing such automata more naturally and simpler than in general case. Possible models of language recognition by QF1CA are considered. The recognition of some languages by QF1CA is shown and compared with recognition by probabilistic counterparts.
A description based on languages of the final non-deterministic automaton
2014
The study of the behaviour of non-deterministic automata has traditionally focused on the languages which can be associated to the different states. Under this interpretation, the different branches that can be taken at every step are ignored. However, we can also take into account the different decisions which can be made at every state, that is, the branches that can be taken, and these decisions might change the possible future behaviour. In this case, the behaviour of the automata can be described with the help of the concept of bisimilarity. This is the kind of description that is usually obtained when the automata are regarded as labelled transition systems or coalgebras. Contrarily t…
Complexity of operations on cofinite languages
2010
International audience; We study the worst case complexity of regular operation on cofinite languages (i.e., languages whose complement is finite) and provide algorithms to compute efficiently the resulting minimal automata.
Multitasking associative networks.
2012
We introduce a bipartite, diluted and frustrated, network as a sparse restricted Boltzman machine and we show its thermodynamical equivalence to an associative working memory able to retrieve multiple patterns in parallel without falling into spurious states typical of classical neural networks. We focus on systems processing in parallel a finite (up to logarithmic growth in the volume) amount of patterns, mirroring the low-level storage of standard Amit-Gutfreund-Sompolinsky theory. Results obtained trough statistical mechanics, signal-to-noise technique and Monte Carlo simulations are overall in perfect agreement and carry interesting biological insights. Indeed, these associative network…
Active Learning of Recursive Functions by Ultrametric Algorithms
2014
We study active learning of classes of recursive functions by asking value queries about the target function f, where f is from the target class. That is, the query is a natural number x, and the answer to the query is f(x). The complexity measure in this paper is the worst-case number of queries asked. We prove that for some classes of recursive functions ultrametric active learning algorithms can achieve the learning goal by asking significantly fewer queries than deterministic, probabilistic, and even nondeterministic active learning algorithms. This is the first ever example of a problem where ultrametric algorithms have advantages over nondeterministic algorithms.
Data-based modeling of vehicle collisions by nonlinear autoregressive model and feedforward neural network
2013
Vehicle crash test is the most direct and common method to assess vehicle crashworthiness. Visual inspection and obtained measurements, such as car acceleration, are used, e.g. to examine impact severity of an occupant or to assess overall car safety. However, those experiments are complex, time-consuming, and expensive. We propose a method to reproduce car kinematics during a collision using nonlinear autoregressive (NAR) model which parameters are estimated by the use of feedforward neural network. NAR model presented in this study is derived from the more general one - nonlinear autoregressive with moving average (NARMA). Suitability of autoregressive systems for data-based modeling was …
Data Compression with ENO Schemes: A Case Study
2001
Abstract We study the compresion properties of ENO-type nonlinear multiresolution transformations on digital images. Specific error control algorithms are used to ensure a prescribed accuracy. The numerical results reveal that these methods strongly outperform the more classical wavelet decompositions in the case of piecewise smooth geometric images.