Search results for "Computation"
showing 10 items of 7362 documents
An inductive inference approach to classification
1992
In this paper, we introduce a formal framework for investigating the relationship of inductive inference and the task of classification. We give the first results on the relationship between functions that can be identified in the limit and functions that can be acquired from unclassified objects only. Moreover, we present results on the complexity of classification functions and the preconditions necessary in order to allow the computation of such functions.
Psi4: an open-source ab initio electronic structure program
2011
The Psi4 program is a new approach to modern quantum chemistry, encompassing Hartree–Fock and density-functional theory to configuration interaction and coupled cluster. The program is written entirely in C++ and relies on a new infrastructure that has been designed to permit high-efficiency computations of both standard and emerging electronic structure methods on conventional and high-performance parallel computer architectures. Psi4 offers flexible user input built on the Python scripting language that enables both new and experienced users to make full use of the program's capabilities, and even to implement new functionality with moderate effort. To maximize its impact and usefulness, …
Non-interleaved Quadtree Node Codification
2004
The usual quadtree node non-pointer codification is based on interleaved binary representations of node coordinates, in such a way that every operation that concerns to the spatial position or to the specific orientation of the region represented by the node needs to undo this interleaving process. So, the computation time of such operations is linear with the node depth. In this paper an alternative codification is presented called “non-interleaved codification”. The new codification has a simpler management and a higher intuitiveness than current codifications that use the interleaving approach. The proposed codification is more efficient than previous ones for the following set of operat…
Dictionary-symbolwise flexible parsing
2012
AbstractLinear-time optimal parsing algorithms are rare in the dictionary-based branch of the data compression theory. A recent result is the Flexible Parsing algorithm of Matias and Sahinalp (1999) that works when the dictionary is prefix closed and the encoding of dictionary pointers has a constant cost. We present the Dictionary-Symbolwise Flexible Parsing algorithm that is optimal for prefix-closed dictionaries and any symbolwise compressor under some natural hypothesis. In the case of LZ78-like algorithms with variable costs and any, linear as usual, symbolwise compressor we show how to implement our parsing algorithm in linear time. In the case of LZ77-like dictionaries and any symbol…
HOW SMART DOES AN AGENT NEED TO BE?
2005
The classic distributed computation is done by atoms, molecules or spins in vast numbers, each equipped with nothing more than the knowledge of their immediate neighborhood and the rules of statistical mechanics. These agents, 1023 or more, are able to form liquids and solids from gases, realize extremely complex ordered states, such as liquid crystals, and even decode encrypted messages. We will describe a study done for a sensor-array "challenge problem" in which we have based our approach on old-fashioned simulated annealing to accomplish target acquisition and tracking under the rules of statistical mechanics. We believe the many additional constraints that occur in the real problem ca…
Soft Pyramid Symmetry Transforms
2005
Pyramid computation is a natural paradigm of computation in planning strategies and multi-resolution image analysis. This paper introduces a new paradigm that is based on the concept of soft-hierarchical operators implemented in a pyramid architecture to retrieve global versus local symmetries. The concept of symmetry is mathematically well defined in geometry whenever patterns are crisp images (two levels). Necessity for a soft approach occurs whenever images are multi-levels and the separation between object and background is subjective or not well defined. The paper describes a new pyramid operator to detect symmetries and shows some experiments supporting the approach. This work has bee…
A Tool for Implementing and Exploring SBM Models: Universal 1D Invertible Cellular Automata
2005
The easiest form of designing Cellular Automata rules with features such as invertibility or particle conserving is to rely on a partitioning scheme, the most important of which is the 2D Margolus neighborhood. In this paper we introduce a 1D Margolus-like neighborhood that gives support to a complete set of Cellular Automata models. We present a set of models called Sliding Ball Models based on this neighborhood and capable of universal computation. We show the way of designing logic gates with these models, propose a digital structure to implement them and finally we present SBMTool, a software development system capable of working with the new models.
Statistically validated networks in bipartite complex systems.
2011
Many complex systems present an intrinsic bipartite nature and are often described and modeled in terms of networks [1-5]. Examples include movies and actors [1, 2, 4], authors and scientific papers [6-9], email accounts and emails [10], plants and animals that pollinate them [11, 12]. Bipartite networks are often very heterogeneous in the number of relationships that the elements of one set establish with the elements of the other set. When one constructs a projected network with nodes from only one set, the system heterogeneity makes it very difficult to identify preferential links between the elements. Here we introduce an unsupervised method to statistically validate each link of the pr…
Gl-learning
2016
In this paper, we present a new open-source software library, Gl-learning, for grammatical inference. The rise of new application scenarios in recent years has required optimized methods to address knowledge extraction from huge amounts of data and to model highly complex systems. Our library implements the main state-of-the-art algorithms in the grammatical inference field (RPNI, EDSM, L*), redesigned through the OpenMP library for a parallel execution that drastically decreases execution times. To our best knowledge, it is also the first comprehensive library including a noise tolerance learning algorithm, such as Blue*, that significantly broadens the range of the potential application s…
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.