Search results for "Theoretical Computer Science"
showing 10 items of 1151 documents
Content quality assessment and acceptance testing in location‐based services
2006
In this paper, we develop and evaluate an approach to assessing the content quality in a location‐based service (LBS). The proposed approach, instead of assessing the quality in absolute terms such as completeness or accuracy, measures the effect that the imperfection of the content is having on the reliability of that specific LBS. We apply the basic ideas from Software Reliability Engineering (SRE), but develop a modification of SRE, 2‐Branch, in order to separate content quality from other factors, such as positioning imprecision, and to reduce the measurement error. In our experimental study, we first compare 2‐Branch to the standard SRE, after which we experimentally analyze some prope…
Assessing the Performance of Interactive Multiobjective Optimization Methods
2021
Interactive methods are useful decision-making tools for multiobjective optimization problems, because they allow a decision-maker to provide her/his preference information iteratively in a comfortable way at the same time as (s)he learns about all different aspects of the problem. A wide variety of interactive methods is nowadays available, and they differ from each other in both technical aspects and type of preference information employed. Therefore, assessing the performance of interactive methods can help users to choose the most appropriate one for a given problem. This is a challenging task, which has been tackled from different perspectives in the published literature. We present a …
Strong chromatic index of products of graphs
2007
Graphs and Algorithms
Exact results for accepting probabilities of quantum automata
2001
One of the properties of Kondacs-Watrous model of quantum finite automata (QFA) is that the probability of the correct answer for a QFA cannot be amplified arbitrarily. In this paper, we determine the maximum probabilities achieved by QFAs for several languages. In particular, we show that any language that is not recognized by an RFA (reversible finite automaton) can be recognized by a QFA with probability at most 0.7726...
Word assembly through minimal forbidden words
2006
AbstractWe give a linear-time algorithm to reconstruct a finite word w over a finite alphabet A of constant size starting from a finite set of factors of w verifying a suitable hypothesis. We use combinatorics techniques based on the minimal forbidden words, which have been introduced in previous papers. This improves a previous algorithm which worked under the assumption of stronger hypothesis.
Using skeleton and Hough transform variant to correct skew in historical documents
2020
International audience; As a main part of several document analysis systems, Skew estimation represents one of the major research challenges, particularly in case of historical documents exploration. In this paper, we propose an original skew angle detection and correction technique. Morphological Skeleton is introduced to considerably diminish the amount of data by eliminating the redundant pixels and preserving only the central curves of the image components. Next, the proposed method uses Progressive Probabilistic Hough Transform (PPHT) to find image lines. At the end, a specific procedure is applied in order to measure the global skew angle of the document image from these identified li…
Automatic shape detection of ice crystals
2021
Abstract Clouds have a crucial impact on the energy balance of the Earth-Atmosphere system. They can cool the system by partly reflecting or scattering of the incoming solar radiation (albedo effect); moreover, thermal radiation as emitted from the Earth's surface can be absorbed and partly re-emitted by clouds leading to a warming of the atmosphere (greenhouse effect). The effectiveness of both effects crucially depends on the size and the shape of a cloud's particulate constituents, i.e. liquid water droplets or solid ice crystals. For studying cloud microphysics, in situ measurements on board of aircraft are commonly used. An important class of measurement techniques comprises optical ar…
Amount of nonconstructivity in deterministic finite automata
2010
AbstractWhen D. Hilbert used nonconstructive methods in his famous paper on invariants (1888), P. Gordan tried to prevent the publication of this paper considering these methods as non-mathematical. L.E.J. Brouwer in the early twentieth century initiated intuitionist movement in mathematics. His slogan was “nonconstructive arguments have no value for mathematics”. However, P. Erdös got many exciting results in discrete mathematics by nonconstructive methods. It is widely believed that these results either cannot be proved by constructive methods or the proofs would have been prohibitively complicated. The author (Freivalds, 2008) [10] showed that nonconstructive methods in coding theory are…
Local Normal Forms for First-Order Logic with Applications to Games and Automata
1999
Building on work of Gaifman [Gai82] it is shown that every first-order formula is logically equivalent to a formula of the form ∃ x_1,...,x_l, \forall y, φ where φ is r-local around y, i.e. quantification in φ is restricted to elements of the universe of distance at most r from y. \par From this and related normal forms, variants of the Ehrenfeucht game for first-order and existential monadic second-order logic are developed that restrict the possible strategies for the spoiler, one of the two players. This makes proofs of the existence of a winning strategy for the duplicator, the other player, easier and can thus simplify inexpressibility proofs. \par As another application, automata mode…
The pruning-grafting lattice of binary trees
2008
AbstractWe introduce a new lattice structure Bn on binary trees of size n. We exhibit efficient algorithms for computing meet and join of two binary trees and give several properties of this lattice. More precisely, we prove that the length of a longest (resp. shortest) path between 0 and 1 in Bn equals to the Eulerian numbers 2n−(n+1) (resp. (n−1)2) and that the number of coverings is (2nn−1). Finally, we exhibit a matching in a constructive way. Then we propose some open problems about this new structure.