Search results for "D algorithm"
showing 10 items of 327 documents
On the suffix automaton with mismatches
2007
International audience; In this paper we focus on the construction of the minimal deterministic finite automaton S_k that recognizes the set of suffixes of a word w up to k errors. We present an algorithm that makes use of S_k in order to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r, where r is the value of the repetition index of w. Moreover, we give some experimental results on some well-known words, like prefixes of Fibonacci and Thue-Morse words, and we make a conjecture on the size of the suffix automaton with mismatches.
A trie-based approach for compacting automata
2004
International audience; We describe a new technique for reducing the number of nodes and symbols in automata based on tries. The technique stems from some results on anti-dictionaries for data compression and does not need to retain the input string, differently from other methods based on compact automata. The net effect is that of obtaining a lighter automaton than the directed acyclic word graph (DAWG) of Blumer et al., as it uses less nodes, still with arcs labeled by single characters.
Utilisation et traitement des données saisies sous EndNote avec des scripts PHP/MySQL
2010
National audience; Cet article présente la façon d’exploiter ou de traiter des données de références bibliographiques saisies ou importées dans EndNote en dehors de leur logiciel natif en utilisant des scripts PHP/MySQL. Deux raisons nous ont amenés à utiliser ce traitement : soit EndNote ne pouvait pas faire des opérations particulières, soit il le pouvait mais de façon trop fastidieuse. Dans ce but nous exposerons dans un premier temps la façon dont les données sont organisées par EndNote, puis la méthode pour les exploiter et enfin nous donnerons quelques exemples d’utilisation.
A Hybrid Algorithm Based on WiFi for Robust and Effective Indoor Positioning
2019
Indoor positioning based on the Wireless Fidelity (WiFi) protocol and the Pedestrian Dead Reckoning (PDR) approach is widely exploited because of the existing WiFi infrastructure in buildings and the advancement of built-in smartphone sensors. In this work, a hybrid algorithm that combines WiFi fingerprinting and PDR to both exploit their advantages as well as limiting the impact of their disadvantages is proposed. Specifically, to build a probability map from noisy Received Signal Strength (RSS), a Gaussian Process (GP) regression is deployed to estimate and construct the RSS fingerprints with incomplete data. Mean and variance of generated points are used to estimate WiFi fingerprinting p…
Probabilistic Logic under Coherence: Complexity and Algorithms
2005
In previous work [V. Biazzo, A. Gilio, T. Lukasiewicz and G. Sanfilippo, Probabilistic logic under coherence, model-theoretic probabilistic logic, and default reasoning in System P, Journal of Applied Non-Classical Logics 12(2) (2002) 189---213.], we have explored the relationship between probabilistic reasoning under coherence and model-theoretic probabilistic reasoning. In particular, we have shown that the notions of g-coherence and of g-coherent entailment in probabilistic reasoning under coherence can be expressed by combining notions in model-theoretic probabilistic reasoning with concepts from default reasoning. In this paper, we continue this line of research. Based on the above sem…
Decentralized classification in societies of autonomous and heterogenous robots
2011
This paper addresses the classification problem for a set of autonomous robots that interact with each other. The objective is to classify agents that “behave” in “different way”, due to their own physical dynamics or to the interaction protocol they are obeying to, as belonging to different “species”. This paper describes a technique that allows a decentralized classification system to be built in a systematic way, once the hybrid models describing the behavior of the different species are given. This technique is based on a decentralized identification mechanism, by which every agent classifies its neighbors using only local information. By endowing every agent with such a local classifie…
Decentralized Deployment of Mobile Sensors for Optimal Connected Sensing Coverage
2008
In this paper, we address the optimal connected sensing coverage problem, i.e., how mobile sensors with limited sensing capabilities can cooperatively adjust their locations so as to maximize the extension of the covered area while avoiding any internal “holes”, areas that are not covered by any sensor. Our solution consists in a distributed motion algorithm that is based on an original extension of the Voronoi tessellation.
Scheduling a cellular manufacturing system with GA
2002
The flexible manufacturing cell scheduling problem is considered with a multi-objective approach, pursuing together makespan minimisation and the in process job wait minimisation. The formulation of the scheduling problem is discussed, analysing how to generate well suited sequences, like generalised permutation sequences, and the proper construction of a JIT timing of activities. An evolutionary sequencing algorithm based on both classic genetic operators and hybrid operators is then proposed. The hybrid operators have been introduced to construct highly fit initial population, to perform periodically a local search on the population and to maintain enough genetical diversity in the actual…
Distributed n-player approachability via time and space average consensus
2012
Abstract In this paper we consider repeated coalitional games with transferable utilities (TU) over networks. Namely, we consider a set of n players that have to distribute among themselves a vector of rewards (one for each player). In our network version there is no coordinator allocating the rewards, but the agents have to agree on a common time-averaged vector by updating the local estimates of the reward vector. The common time-averaged reward vector has to approach a suitable constraint set, called core of the game, that guarantees that no agents benefit from quitting the grand coalition. We propose a doubly (over time and space) averaging distributed algorithm. At every iteration, eac…
An Approach to Delineate Groundwater Bodies at Risk: Seawater Intrusion in Liepāja (Latvia)
2018
Groundwater quality in coastal areas is frequently affected by seawater intrusion as a consequence of intensive water consumption. To achieve “good chemical status” of a groundwater body according to Water Framework Directive the effects of saline or other intrusions should not be observed. Groundwater pumping in former decades has caused a significant seawater intrusion into confined aquifer in Liepāja and has led to deterioration of relatively wide coastal area of the third largest city in Latvia. However, the area affected by seawater intrusion is a small part of groundwater body F1 which overall chemical status is good. Thus, no specific management measures have been applied to explore …