Search results for "complex"
showing 10 items of 5889 documents
Text Compression Using Antidictionaries
1999
International audience; We give a new text compression scheme based on Forbidden Words ("antidictionary"). We prove that our algorithms attain the entropy for balanced binary sources. They run in linear time. Moreover, one of the main advantages of this approach is that it produces very fast decompressors. A second advantage is a synchronization property that is helpful to search compressed data and allows parallel compression. Our algorithms can also be presented as "compilers" that create compressors dedicated to any previously fixed source. The techniques used in this paper are from Information Theory and Finite Automata.
Extracting string motif bases for quorum higher than two
2012
Bases of generators of motifs consisting of strings in which some positions can be occupied by a don’t care provide a useful conceptual tool for their description and a way to reduce the time and space involved in the discovery process. In the last few years, a few algorithms have been proposed for the extraction of a basis, building in large part on combinatorial properties of strings and their autocorrelations. Currently, the most efficient techniques for binary alphabets and quorum q = 2 require time quadratic in the length of the host string. The present paper explores properties of motif bases for quorum q ≥ 2, both with binary and general alphabets, by also showing that important resu…
Communication complexity in a 3-computer model
1996
It is proved that the probabilistic communication complexity of the identity function in a 3-computer model isO(√n).
On the Influence of Technology on Learning Processes
2014
Probabilistic computations and frequency computations were invented for the same purpose, namely, to study possible advantages of technology involving random choices. Recently several authors have discovered close relationships of these generalizations of deterministic computations to computations taking advice. Various forms of computation taking advice were studied by Karp and Lipton [1], Damm and Holzer [2], and Freivalds [3]. In the present paper, we apply the nonconstructive, probabilistic, and frequency methods to an inductive inference paradigm originally due to Gold [4] and investigate their impact on the resulting learning models. Several trade-offs with respect to the resulting l…
Correlation Analysis of Node and Edge Centrality Measures in Artificial Complex Networks
2021
The role of an actor in a social network is identified through a set of measures called centrality. Degree centrality, betweenness centrality, closeness centrality, and clustering coefficient are the most frequently used metrics to compute the node centrality. Their computational complexity in some cases makes unfeasible, when not practically impossible, their computations. For this reason, we focused on two alternative measures, WERW-Kpath and Game of Thieves, which are at the same time highly descriptive and computationally affordable. Our experiments show that a strong correlation exists between WERW-Kpath and Game of Thieves and the classical centrality measures. This may suggest the po…
Game of Thieves and WERW-Kpath: Two Novel Measures of Node and Edge Centrality for Mafia Networks
2021
Real-world complex systems can be modeled as homogeneous or heterogeneous graphs composed by nodes connected by edges. The importance of nodes and edges is formally described by a set of measures called centralities which are typically studied for graphs of small size. The proliferation of digital collection of data has led to huge graphs with billions of nodes and edges. For this reason, we focus on two new algorithms, Game of Thieves and WERW-Kpath which are computationally-light alternatives to the canonical centrality measures such as degree, node and edge betweenness, closeness and clustering. We explore the correlation among these measures using the Spearman’s correlation coefficient …
Algorithmics for the Life Sciences
2013
The life sciences, in particular molecular biology and medicine, have wit- nessed fundamental progress since the discovery of the “the Double Helix”. A rele- vant part of such an incredible advancement in knowledge has been possible thanks to synergies with the mathematical sciences, on the one hand, and computer science, on the other. Here we review some of the most relevant aspects of this cooperation focusing on contributions given by the design, analysis and engineering of fast al- gorithms for the life sciences.
A Mechanistic Reading of Quantum Laser Theory
2015
Quantum laser theory proceeds in a way that seems at variance with the mechanistic model of explanation. First, as is typical for a complex systems theory, the detailed behavior of the component parts plays a surprisingly subordinate role. In particular, the so-called “enslaving principle” seems to defy a mechanistic reading. Moreover, being quantum objects, the “parts” of a laser are neither located in space nor describable as separate entities. I want to show that, despite these apparent obstacles, quantum laser theory constitutes a good example of a mechanistic explanation in a quantum physical setting, provided that one broadens the notion of mechanism. One may feel that such adjustment…
IR fingerprints of U(VI) nitrate monoamides complexes: a joint experimental and theoretical study.
2010
Infrared spectra of 0.5 mol·L-1 uranium(VI) nitrate monoamide complexes in toluene have been recorded and compared with infrared spectra calculated by DFT. The investigated monoamides were N,N- dimethylformamide (DMF), N,N-dibutylformamide (DBF), and N,N- dicyclohexylformamide (DcHF). The validity of DFT calculations for describing uranium nitrate monoamide complexes has been confirmed as a fair agreement between experimental and calculated spectra was obtained. Furthermore, a topological analysis of the electron density has been carried out to characterize monoamide-uranium interactions. From this work, it appears that the increase of stability of uranylmonoamide complexes may be directly …
Oxygen isotope composition of North American bobcat (Lynx rufus) and puma (Puma concolor) bone phosphate: implications for provenance and climate rec…
2015
Feline carnivores are threatened by illegal wildlife trade. Tracing the provenance of unknown felid tissues via stable isotope analysis could provide important information in wildlife crime investigations. The oxygen isotope composition of mammalian skeletal phosphate (δ18Op) is widely applied to trace the origin of animal remains and to reconstruct migratory patterns in palaeontological, archaeological, ecological and wildlife forensic applications. Teeth and bones of terrestrial mammals form at constant body temperature in isotope equilibrium with body water, which is predominantly controlled by ingested meteoric water (δ18Ow) that varies systematically with latitude, altitude and climate…