Search results for " Theoretical Computer Science"
showing 10 items of 28 documents
New results for finding common neighborhoods in massive graphs in the data stream model
2008
AbstractWe consider the problem of finding pairs of vertices that share large common neighborhoods in massive graphs. We give lower bounds for randomized, two-sided error algorithms that solve this problem in the data-stream model of computation. Our results correct and improve those of Buchsbaum, Giancarlo, and Westbrook [On finding common neighborhoods in massive graphs, Theoretical Computer Science, 299 (1–3) 707–718 (2004)]
On fixed points of the Burrows-Wheeler transform
2017
The Burrows-Wheeler Transform is a well known transformation widely used in Data Compression: important competitive compression software, such as Bzip (cf. [1]) and Szip (cf. [2]) and some indexing software, like the FM-index (cf. [3]), are deeply based on the Burrows Wheeler Transform. The main advantage of using BWT for data compression consists in its feature of "clustering" together equal characters. In this paper we show the existence of fixed points of BWT, i.e., words on which BWT has no effect. We show a characterization of the permutations associated to BWT of fixed points and we give the explicit form of fixed points on a binary ordered alphabet a, b having at most four b's and th…
Burrows-Wheeler transform and Run-Length Enconding
2017
In this paper we study the clustering effect of the Burrows-Wheeler Transform (BWT) from a combinatorial viewpoint. In particular, given a word w we define the BWT-clustering ratio of w as the ratio between the number of clusters produced by BWT and the number of the clusters of w. The number of clusters of a word is measured by its Run-Length Encoding. We show that the BWT-clustering ratio ranges in ]0, 2]. Moreover, given a rational number \(r\,\in \,]0,2]\), it is possible to find infinitely many words having BWT-clustering ratio equal to r. Finally, we show how the words can be classified according to their BWT-clustering ratio. The behavior of such a parameter is studied for very well-…
Robust stabilisation of 2D state-delayed stochastic systems with randomly occurring uncertainties and nonlinearities
2013
This paper is concerned with the state feedback control problem for a class of two-dimensional (2D) discrete-time stochastic systems with time-delays, randomly occurring uncertainties and nonlinearities. Both the sector-like nonlinearities and the norm-bounded uncertainties enter into the system in random ways, and such randomly occurring uncertainties and nonlinearities obey certain mutually uncorrelated Bernoulli random binary distribution laws. Sufficient computationally tractable linear matrix inequality–based conditions are established for the 2D nonlinear stochastic time-delay systems to be asymptotically stable in the mean-square sense, and then the explicit expression of the desired…
Modeling Drug Effects on Personalized 3D Models of the Heart: A Simulation Study
2010
[EN] The use of anti-arrhythmic drugs is common to treat heart rhythm disorders. Computational modeling and simulation are powerful tools that can be used to investigate the effects of specific drugs on cardiac electrophysiology. In this work a patient-specific anatomical heart model is built to study the effects of dofetilide, a drug that affects IKr current in cardiac cells. We study the multi-scale effects of the drug, from cellular to organ level, by simulating electrical propagation on tissue coupled cellular ion kinetics for several heart beats. Different cell populations configurations namely endocardial, midmyocardial and epicardial are used to test the effect of tissue heterogeneit…
A structured filter for Markovian switching systems
2014
In this work, a new methodology for the structuring of multiple model estimation schemas is developed. The proposed filter is applied to the estimation and detection of active mode in dynamic systems. The discrete-time Markovian switching systems represented by several linear models, associated with a particular operating mode, are studied. Therefore, the main idea of this work is the subdivision of the models set to some subsets in order to improve the detection and estimation performances. Each subset is associated with sub-estimators based on models of the subset. In order to compute the global estimate and subset probabilities, a global estimator is proposed. Theoretical developments ba…
Visibly pushdown modular games,
2014
Games on recursive game graphs can be used to reason about the control flow of sequential programs with recursion. In games over recursive game graphs, the most natural notion of strategy is the modular strategy, i.e., a strategy that is local to a module and is oblivious to previous module invocations, and thus does not depend on the context of invocation. In this work, we study for the first time modular strategies with respect to winning conditions that can be expressed by a pushdown automaton. We show that such games are undecidable in general, and become decidable for visibly pushdown automata specifications. Our solution relies on a reduction to modular games with finite-state automat…
Abelian Powers and Repetitions in Sturmian Words
2016
Richomme, Saari and Zamboni (J. Lond. Math. Soc. 83: 79-95, 2011) proved that at every position of a Sturmian word starts an abelian power of exponent $k$ for every $k > 0$. We improve on this result by studying the maximum exponents of abelian powers and abelian repetitions (an abelian repetition is an analogue of a fractional power) in Sturmian words. We give a formula for computing the maximum exponent of an abelian power of abelian period $m$ starting at a given position in any Sturmian word of rotation angle $\alpha$. vAs an analogue of the critical exponent, we introduce the abelian critical exponent $A(s_\alpha)$ of a Sturmian word $s_\alpha$ of angle $\alpha$ as the quantity $A(s_\a…
Abelian-Square-Rich Words
2017
An abelian square is the concatenation of two words that are anagrams of one another. A word of length $n$ can contain at most $\Theta(n^2)$ distinct factors, and there exist words of length $n$ containing $\Theta(n^2)$ distinct abelian-square factors, that is, distinct factors that are abelian squares. This motivates us to study infinite words such that the number of distinct abelian-square factors of length $n$ grows quadratically with $n$. More precisely, we say that an infinite word $w$ is {\it abelian-square-rich} if, for every $n$, every factor of $w$ of length $n$ contains, on average, a number of distinct abelian-square factors that is quadratic in $n$; and {\it uniformly abelian-sq…
Delay-dependent exponential stabilization of positive 2D switched state-delayed systems in the Roesser model
2014
This paper deals with the controller synthesis for a class of positive two-dimensional (2D) switched delay systems described by the Roesser model. This kind of systems has the property that the states take nonnegative values whenever the initial boundaries are nonnegative, some delay-dependent sufficient conditions for the exponential stability of positive 2D switched systems with state delays are given. Furthermore, the design of positive state feedback controller under which the resulting closed-loop system meets the requirements of positivity and exponential stability is presented in terms of linear matrix inequalities (LMIs). An example is included to illustrate the effectiveness of the…