Search results for "Computation Theory & Mathematics"
showing 10 items of 332 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…
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.
Multiple SIP strategies and bottom-up adorning in logic query optimization
1990
Preprocessing methods called “readorning” and “bottom-up adorning” are introduced as means of enlarging the application domain of magic sets and related query optimization strategies for logic databases. Readorning tries to make possible the simultaneous use of multiple sideways information passing (sip) strategies defined for a rule, thus yielding an optimization effect that may not be achieved by any particular choice of sip strategies. Bottom-up adorning is used to make magic sets applicable to cases in which potential optimizations can be derived from bindings coming upwards from rule bodies to rule heads in bottom-up evaluation. These include the cases in which we know that some base r…
Challenges of Program Synthesis with Grammatical Evolution
2020
Program synthesis is an emerging research topic in the field of EC with the potential to improve real-world software development. Grammar-guided approaches like GE are suitable for program synthesis as they can express common programming languages with their required properties. This work uses common software metrics (lines of code, McCabe metric, size and depth of the abstract syntax tree) for an analysis of GE’s search behavior and the resulting problem structure. We find that GE is not able to solve program synthesis problems, where correct solutions have higher values of the McCabe metric (which means they require conditions or loops). Since small mutations of high-quality solutions str…
Robustness and Randomness
2008
The study of robustness problems for computational geometry algorithms is a topic that has been subject to intensive research efforts from both computer science and mathematics communities. Robustness problems are caused by the lack of precision in computations involving floating-point instead of real numbers. This paper reviews methods dealing with robustness and inaccuracy problems. It discusses approaches based on exact arithmetic, interval arithmetic and probabilistic methods. The paper investigates the possibility to use randomness at certain levels of reasoning to make geometric constructions more robust.
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…
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.
Properties and constraints of cheating-immune secret sharing schemes
2006
AbstractA secret sharing scheme is a cryptographic protocol by means of which a dealer shares a secret among a set of participants in such a way that it can be subsequently reconstructed by certain qualified subsets. The setting we consider is the following: in a first phase, the dealer gives in a secure way a piece of information, called a share, to each participant. Then, participants belonging to a qualified subset send in a secure way their shares to a trusted party, referred to as a combiner, who computes the secret and sends it back to the participants.Cheating-immune secret sharing schemes are secret sharing schemes in the above setting where dishonest participants, during the recons…
On the satisfiability problem for fragments of two-variable logic with one transitive relation
2019
Abstract We study the satisfiability problem for two-variable first-order logic over structures with one transitive relation. We show that the problem is decidable in 2-NExpTime for the fragment consisting of formulas where existential quantifiers are guarded by transitive atoms. As this fragment enjoys neither the finite model property nor the tree model property, to show decidability we introduce a novel model construction technique based on the infinite Ramsey theorem. We also point out why the technique is not sufficient to obtain decidability for the full two-variable logic with one transitive relation; hence, contrary to our previous claim, [FO$^2$ with one transitive relation is deci…