Search results for "Programming"
showing 10 items of 3090 documents
Researching Conditional Probability Problem Solving
2014
The chapter is organized into two parts. In the first one, the main protagonist is the conditional probability problem. We show a theoretical study about conditional probability problems, identifying a particular family of problems we call ternary problems of conditional probability. We define the notions of Level, Category and Type of a problem in order to classify them into sub-families and in order to study them better. We also offer a tool we call trinomial graph that functions as a generative model for this family of problems. We show the syntax of the model that allows researchers and teachers to translate a problem in terms of the trinomial graphs language, and the consequences of th…
Multi-Dimensional motivic pattern extraction founded on adaptive redundancy filtering
2005
Abstract We present a computational model for discovering repeated patterns in symbolic representations of monodic music. Patterns are discovered through an incremental adaptive identification along a multi-dimensional parametric space. The difficulties of pattern discovery mainly come from combinatorial redundancies, that our model is able to control efficiently. A specificity relation is defined between pattern descriptions, unifying suffix and inclusion relations and enabling a filtering of redundant descriptions. Combinatorial proliferation caused by successive repetitions of patterns is managed using cyclic patterns. The modelling of these redundancy control mechanisms enables an autom…
Representations for evolutionary algorithms
2015
Successful and efficient use of evolutionary algorithms (EA) depends on the choice of the genotype, the problem representation (mapping from genotype to phenotype) and on the choice of search operators that are applied to the genotypes. These choices cannot be made independently of each other. The question whether a certain representation leads to better performing EAs than an alternative representation can only be answered when the operators applied are taken into consideration. The reverse is also true: deciding between alternative operators is only meaningful for a given representation. In EA practice one can distinguish two complementary approaches. The first approach uses indirect repr…
High Locality Representations for Automated Programming
2011
We study the locality of the genotype-phenotype mapping used in grammatical evolution (GE). GE is a variant of genetic programming that can evolve complete programs in an arbitrary language using a variable-length binary string. In contrast to standard GP, which applies search operators directly to phenotypes, GE uses an additional mapping and applies search operators to binary genotypes. Therefore, there is a large semantic gap between genotypes (binary strings) and phenotypes (programs or expressions). The case study shows that the mapping used in GE has low locality leading to low performance of standard mutation operators. The study at hand is an example of how basic design principles o…
LeSSS: Learned Shared Semantic Spaces for Relating Multi-Modal Representations of 3D Shapes
2015
In this paper, we propose a new method for structuring multi-modal representations of shapes according to semantic relations. We learn a metric that links semantically similar objects represented in different modalities. First, 3D-shapes are associated with textual labels by learning how textual attributes are related to the observed geometry. Correlations between similar labels are captured by simultaneously embedding labels and shape descriptors into a common latent space in which an inner product corresponds to similarity. The mapping is learned robustly by optimizing a rank-based loss function under a sparseness prior for the spectrum of the matrix of all classifiers. Second, we extend …
A basic analysis toolkit for biological sequences
2007
This paper presents a software library, nicknamed BATS, for some basic sequence analysis tasks. Namely, local alignments, via approximate string matching, and global alignments, via longest common subsequence and alignments with affine and concave gap cost functions. Moreover, it also supports filtering operations to select strings from a set and establish their statistical significance, via z-score computation. None of the algorithms is new, but although they are generally regarded as fundamental for sequence analysis, they have not been implemented in a single and consistent software package, as we do here. Therefore, our main contribution is to fill this gap between algorithmic theory an…
Tally languages accepted by Monte Carlo pushdown automata
1997
Rather often difficult (and sometimes even undecidable) problems become easily decidable for tally languages, i.e. for languages in a single-letter alphabet. For instance, the class of languages recognizable by 1-way nondeterministic pushdown automata equals the class of the context-free languages, but the class of the tally languages recognizable by 1-way nondeterministic pushdown automata, contains only regular languages [LP81]. We prove that languages over one-letter alphabet accepted by randomized one-way 1-tape Monte Carlo pushdown automata are regular. However Monte Carlo pushdown automata can be much more concise than deterministic 1-way finite state automata.
Automata and forbidden words
1998
Abstract Let L ( M ) be the (factorial) language avoiding a given anti-factorial language M . We design an automaton accepting L ( M ) and built from the language M . The construction is effective if M is finite. If M is the set of minimal forbidden words of a single word ν, the automaton turns out to be the factor automaton of ν (the minimal automaton accepting the set of factors of ν). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a nontrivial upper bound on the number of minimal forbidden words of a word.
Minimal forbidden words and factor automata
1998
International audience; Let L(M) be the (factorial) language avoiding a given antifactorial language M. We design an automaton accepting L(M) and built from the language M. The construction is eff ective if M is finite. If M is the set of minimal forbidden words of a single word v, the automaton turns out to be the factor automaton of v (the minimal automaton accepting the set of factors of v). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a non-trivial upper bound on the number of minimal forbidden words of a word.
A Logic of Discovery
1998
A logic of discovery is introduced. In this logic, true sentences are discovered over time based on arriving data. A notion of expectation is introduced to reflect the growing certainty that a universally quantified sentence is true as more true instances are observed. The logic is shown to be consistent and complete. Monadic predicates are considered as a special case