Search results for "102"
showing 10 items of 2892 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.
Dirac physical measures for generic diffeomorphisms
2016
We prove that, for a $C^1$ generic diffeomorphism, the only Dirac physical measures with dense statistical basin are those supported on sinks.
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…
Kolmogorov superposition theorem for image compression
2012
International audience; The authors present a novel approach for image compression based on an unconventional representation of images. The proposed approach is different from most of the existing techniques in the literature because the compression is not directly performed on the image pixels, but is rather applied to an equivalent monovariate representation of the wavelet-transformed image. More precisely, the authors have considered an adaptation of Kolmogorov superposition theorem proposed by Igelnik and known as the Kolmogorov spline network (KSN), in which the image is approximated by sums and compositions of specific monovariate functions. Using this representation, the authors trad…
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.