Search results for " Complexity"
showing 10 items of 623 documents
Multiscale Information Storage of Linear Long-Range Correlated Stochastic Processes
2019
Information storage, reflecting the capability of a dynamical system to keep predictable information during its evolution over time, is a key element of intrinsic distributed computation, useful for the description of the dynamical complexity of several physical and biological processes. Here we introduce a parametric approach which allows one to compute information storage across multiple timescales in stochastic processes displaying both short-term dynamics and long-range correlations (LRC). Our analysis is performed in the popular framework of multiscale entropy, whereby a time series is first "coarse grained" at the chosen timescale through low-pass filtering and downsampling, and then …
A PARALLEL ALGORITHM FOR ANALYZING CONNECTED COMPONENTS IN BINARY IMAGES
1992
In this paper, a parallel algorithm for analyzing connected components in binary images is described. It is based on the extension of the Cylindrical Algebraic Decomposition (CAD) to a two-dimensional (2D) discrete space. This extension allows us to find the number of connected components, to determine their connectivity degree, and to solve the visibility problem. The parallel implementation of the algorithm is outlined and its time/space complexity is given.
Representing 2D Digital Objects
2000
The paper describes the combination a multi-views approach to represent connected components of 2D binary images. The approach is based on the Object Connectivity Graph (OCG), which is a sub-graph of the connectivity graph generated by the Discrete Cylindrical Algebraic Decomposition(DCAD) performed in the 2D discrete space. This construction allows us to find the number of connected components, to determine their connectivity degree, and to solve visibility problem. We show that the CAD construction, when performed on two orthogonal views, supply information to avoid ambiguities in the interpretation of each image component. The implementation of the algorithm is outlined and the computati…
New delay-dependent stability conditions for time-varying delay systems
2013
Published version of an article in the journal: Mathematical Problems in Engineering. Also available from the publisher at: http://dx.doi.org/10.1155/2013/360924 Open Access This paper addresses the delay-dependent stability for systems with time-varying delay. First, by taking multi-integral terms into consideration, new Lyapunov-Krasovskii functional is defined. Second, in order to reduce the computational complexity of the main results, reciprocally convex approach and some special transformations are introduced, and new delay-dependent stability criteria are proposed, which are less conservative and have less decision variables than some previous results. Finally, two well-known example…
On the Evaluation of Images Complexity: A Fuzzy Approach
2006
The inherently multidimensional problem of evaluating the complexity of an image is of a certain relevance in both computer science and cognitive psychology. Computer scientists usually analyze spatial dimensions, to deal with automatic vision problems, such as feature-extraction. Psychologists seem more interested in the temporal dimension of complexity, to explore attentional models. Is it possible, by merging both approaches, to define an more general index of visual complexity? We have defined a fuzzy mathematical model of visual complexity, using a specific entropy function; results obtained by applying this model to pictorial images have a strong correlation with ones from an experime…
One-Counter Verifiers for Decidable Languages
2013
Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this paper, we show that if we use architecturally restricted verifiers instead of restricting the working memory, i.e. replacing the working tape(s) with a single counter, we can define some IPS’s for each decidable language. Such verifiers are called two-way probabilistic one-counter automata (2pca’s). Then, we show that by adding a fixed-size quantum memory to a 2pca, called a two-way one-counter automaton with quantum and classical states (2qcca), the protocol can be spac…
Syntactic complexity in Finnish-background EFL learners’ writing at CEFR levels A1–B2
2022
Eurooppalaisen viitekehyksen (EVK) merkitys kielikoulutukselle on lisännyt tutkimusta sen taitotasojen kielellisistä piirteistä; tarkempi tieto näistä piirteistä auttaisi EVK:n soveltamista opetusmateriaalien, kurssien ja arviointin laatimiseen. Tutkimuksessa selvitettiin eroavatko EVK:n tasot toisistaan syntaksin kompleksisuuden perusteella. Suomalaiset 14- ja 17-vuotiaat englannin oppijat (N=379) kirjoittivat kolme kirjoitelmaa, jotka arvioitiin EVK:n taitotasoille. Arviointiaineisto tutkittiin monitahoisella Rasch-analyysillä ja tekstien piirteet selvitettiin automaattisilla analyysiohjelmilla. Tuloksien perusteella alimpia EVK-tasoja (A1–A2) erotti selvimmin toisistaan lauseiden ja T-yk…
Computational Models That Matter During a Global Pandemic Outbreak
2020
The COVID-19 pandemic is causing a dramatic loss of lives worldwide, challenging the sustainability of our health care systems, threatening economic meltdown, and putting pressure on the mental health of individuals (due to social distancing and lock-down measures). The pandemic is also posing severe challenges to the scientific community, with scholars under pressure to respond to policymakers’ demands for advice despite the absence of adequate, trusted data. Understanding the pandemic requires fine-grained data representing specific local conditions and the social reactions of individuals. While experts have built simulation models to estimate disease trajectories that may be enough to gu…
FO^2 with one transitive relation is decidable
2013
We show that the satisfiability problem for the two-variable first-order logic, FO^2, over transitive structures when only one relation is required to be transitive, is decidable. The result is optimal, as FO^2 over structures with two transitive relations, or with one transitive and one equivalence relation, are known to be undecidable, so in fact, our result completes the classification of FO^2-logics over transitive structures with respect to decidability. We show that the satisfiability problem is in 2-NExpTime. Decidability of the finite satisfiability problem remains open.
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)]