Search results for "algorithm"
showing 10 items of 4887 documents
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…
Rough Sets and Vague Sets
2007
The subject-matter of the consideration touches the problem of vagueness. The notion of the rough set, originated by Zdzislaw Pawlak, was constructed under the influence of vague information and methods of shaping systems of notions leading to conceptualization and representation of vague knowledge, so also systems of their scopes as some vague sets. This paper outlines some direction of searching for a solution to this problem. In the paper, in connection to the notion of the rough set, the notion of a vague set is introduced. Some operations on these sets and their properties are discussed. The considerations intend to take into account a classical approach to reasoning, based on vague pr…
Fragtique: Applying an OO Database Distribution Strategy to Data Warehouse
2001
We propose a strategy for distribution of a relational data warehouse organized according to a star schema. We adapt fragmentation and allocation strategies that were developed for OO databases. We split the most-often-accessed dimension table into fragments by using primary horizontal fragmentation. The derived fragmentation then divides the fact table into fragments. Other dimension tables are not fragmented since they are presumed to be sufficiently small. Allocation of fragments encompasses duplication of non-fragmented dimension tables that we call a closure.
Distributed Consensus on Boolean Information
2009
Abstract In this paper we study the convergence towards consensus on information in a distributed system of agents communicating over a network. The particularity of this study is that the information on which the consensus is seeked is not represented by real numbers, rather by logical values or sets. Whereas the problems of allowing a network of agents to reach a consensus on logical functions of input events, and that of agreeing on set–valued information, have been separately addressed in previous work, in this paper we show that these problems can indeed be attacked in a unified way in the framework of Boolean distributed information systems. Based on a notion of contractivity for Bool…
On the problem of visualizing point distributions in high dimensional spaces
1995
Abstract Exploring dynamical systems with the aid of computer graphics requires that the relevant structures can be seen and be noticed. This poses special problems if the system is multidimensional, and it has to be decided which kind of projection serves the purpose. I propose using the mathematical frame of categories and functors to describe the process of visualization. This allows detecting and analyzing possible sources of misinterpretation in a formal way. The distribution of distances of embedded electroencephalographic data from a fixed reference point is used as an example for discussing some aspects of the visualization process. The multidimensional p-norms are an example of a p…
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.
Asymmetric Comparison and Querying of Biological Networks
2011
Comparing and querying the protein-protein interaction (PPI) networks of different organisms is important to infer knowledge about conservation across species. Known methods that perform these tasks operate symmetrically, i.e., they do not assign a distinct role to the input PPI networks. However, in most cases, the input networks are indeed distinguishable on the basis of how the corresponding organism is biologically well characterized. In this paper a new idea is developed, that is, to exploit differences in the characterization of organisms at hand in order to devise methods for comparing their PPI networks. We use the PPI network (called Master) of the best characterized organism as a …
Shrinking language models by robust approximation
2002
We study the problem of reducing the size of a language model while preserving recognition performance (accuracy and speed). A successful approach has been to represent language models by weighted finite-state automata (WFAs). Analogues of classical automata determinization and minimization algorithms then provide a general method to produce smaller but equivalent WFAs. We extend this approach by introducing the notion of approximate determinization. We provide an algorithm that, when applied to language models for the North American Business task, achieves 25-35% size reduction compared to previous techniques, with negligible effects on recognition time and accuracy.
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).
Building Construction Sets by Tiling Grammar Simplification
2016
This paper poses the problem of fabricating physical construction sets from example geometry: A construction set provides a small number of different types of building blocks from which the example model as well as many similar variants can be reassembled. This process is formalized by tiling grammars. Our core contribution is an approach for simplifying tiling grammars such that we obtain physically manufacturable building blocks of controllable granularity while retaining variability, i.e., the ability to construct many different, related shapes. Simplification is performed by sequences of two types of elementary operations: non-local joint edge collapses in the tile graphs reduce the gra…