Search results for "COMPLEXITY"
showing 10 items of 1094 documents
Unary Probabilistic and Quantum Automata on Promise Problems
2015
We continue the systematic investigation of probabilistic and quantum finite automata (PFAs and QFAs) on promise problems by focusing on unary languages. We show that bounded-error QFAs are more powerful than PFAs. But, in contrary to the binary problems, the computational powers of Las-Vegas QFAs and bounded-error PFAs are equivalent to deterministic finite automata (DFAs). Lastly, we present a new family of unary promise problems with two parameters such that when fixing one parameter QFAs can be exponentially more succinct than PFAs and when fixing the other parameter PFAs can be exponentially more succinct than DFAs.
Entropic descriptor of a complex behaviour
2009
We propose a new type of entropic descriptor that is able to quantify the statistical complexity (a measure of complex behaviour) by taking simultaneously into account the average departures of a system's entropy S from both its maximum possible value Smax and its minimum possible value Smin. When these two departures are similar to each other, the statistical complexity is maximal. We apply the new concept to the variability, over a range of length scales, of spatial or grey-level pattern arrangements in simple models. The pertinent results confirm the fact that a highly non-trivial, length-scale dependence of the entropic descriptor makes it an adequate complexity-measure, able to disting…
Estimating the decomposition of predictive information in multivariate systems
2015
In the study of complex systems from observed multivariate time series, insight into the evolution of one system may be under investigation, which can be explained by the information storage of the system and the information transfer from other interacting systems. We present a framework for the model-free estimation of information storage and information transfer computed as the terms composing the predictive information about the target of a multivariate dynamical process. The approach tackles the curse of dimensionality employing a nonuniform embedding scheme that selects progressively, among the past components of the multivariate process, only those that contribute most, in terms of co…
Statistical inference and Monte Carlo algorithms
1996
This review article looks at a small part of the picture of the interrelationship between statistical theory and computational algorithms, especially the Gibbs sampler and the Accept-Reject algorithm. We pay particular attention to how the methodologies affect and complement each other.
From the kinetic theory of active particles to the modeling of social behaviors and politics
2007
This paper deals with the modeling of complex social systems by methods of the mathematical kinetic theory for active particles. Specifically, a recent model by the last two authors is analyzed from the social sciences point of view. The model shows, despite its simplicity, some interesting features. In particular, this paper investigates the ability of the model to describe how a social politics and the disposable overall wealth may have a relevant influence towards the trend of the wealth distribution. The paper also outlines various research perspectives.
Spin-1/2 sub-dynamics nested in the quantum dynamics of two coupled qutrits
2017
In this paper we investigate the quantum dynamics of two spin-1 systems, $\vec{\textbf{S}}_1$ and $\vec{\textbf{S}}_2$, adopting a generalized $(\vec{\textbf{S}}_1+\vec{\textbf{S}}_2)^2$-nonconserving Heisenberg model. We show that, due to its symmetry property, the nine-dimensional dynamics of the two qutrits exactly decouples into the direct sum of two sub-dynamics living in two orthogonal four- and five-dimensional subspaces. Such a reduction is further strengthened by our central result consisting in the fact that in the four-dimensional dynamically invariant subspace, the two qutrits quantum dynamics, with no approximations, is equivalent to that of two non interacting spin 1/2's. The …
kmcEx: memory-frugal and retrieval-efficient encoding of counted k-mers.
2018
Abstract Motivation K-mers along with their frequency have served as an elementary building block for error correction, repeat detection, multiple sequence alignment, genome assembly, etc., attracting intensive studies in k-mer counting. However, the output of k-mer counters itself is large; very often, it is too large to fit into main memory, leading to highly narrowed usability. Results We introduce a novel idea of encoding k-mers as well as their frequency, achieving good memory saving and retrieval efficiency. Specifically, we propose a Bloom filter-like data structure to encode counted k-mers by coupled-bit arrays—one for k-mer representation and the other for frequency encoding. Exper…
Inhomogeneity and complexity measures for spatial patterns
2002
In this work, we examine two different measures for inhomogeneity and complexity that are derived from non-extensive considerations à la Tsallis. Their performance is then tested on theoretically generated patterns. All measures are found to exhibit a most sensitive behaviour for Sierpinski carpets. The procedures here introduced provide us with new, powerful Tsallis’ tools for analysing the inhomogeneity and complexity of spatial patterns.
Selecting the tuning parameter in penalized Gaussian graphical models
2019
Penalized inference of Gaussian graphical models is a way to assess the conditional independence structure in multivariate problems. In this setting, the conditional independence structure, corresponding to a graph, is related to the choice of the tuning parameter, which determines the model complexity or degrees of freedom. There has been little research on the degrees of freedom for penalized Gaussian graphical models. In this paper, we propose an estimator of the degrees of freedom in $$\ell _1$$ -penalized Gaussian graphical models. Specifically, we derive an estimator inspired by the generalized information criterion and propose to use this estimator as the bias term for two informatio…
Design-based estimation for geometric quantiles with application to outlier detection
2010
Geometric quantiles are investigated using data collected from a complex survey. Geometric quantiles are an extension of univariate quantiles in a multivariate set-up that uses the geometry of multivariate data clouds. A very important application of geometric quantiles is the detection of outliers in multivariate data by means of quantile contours. A design-based estimator of geometric quantiles is constructed and used to compute quantile contours in order to detect outliers in both multivariate data and survey sampling set-ups. An algorithm for computing geometric quantile estimates is also developed. Under broad assumptions, the asymptotic variance of the quantile estimator is derived an…