Automate fini non déterministe

Résumé

Un automate fini (on dit parfois, par une traduction littérale de l'anglais, machine à états finis, au lieu de machine avec un nombre fini d'états ou machine à états finie ou machine finie à états), finite-state automaton ou finite-state machine (FSA, FSM), est une machine abstraite qui est un outil fondamental en mathématiques discrètes et en informatique. On les retrouve dans la modélisation de processus, le contrôle, les protocoles de communication, la vérification de programmes, la théorie de la calculabilité, dans l'étude des langages formels et en compilation. Ils sont utilisés dans la recherche des motifs dans un texte. On distingue les automates finis non déterministes (abrégés en AFN) en anglais non-deterministic finite automaton ou NFA, des automates finis déterministes (abrégés en AFD) en anglais deterministic finite automata ou DFA. Sans précision supplémentaire, un automate fini est toujours non déterministe, mais on devrait plutôt dire « indéterministe », puisqu'il

Source officielle

https://fr.wikipedia.org/wiki/Automate_fini_non_d%C3%A9terministe

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (2)

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (16)

Concepts associés

Chargement

Cours associés (15)

Cours associés

Chargement

Séances de cours associées (30)

Séances de cours associées

Chargement

Planner9, a HTN planner distributed on groups of miniature mobile robots

Stéphane Magnenat, Francesco Mondada, Martin Voelkle

Autonomous mobile robots are promising tools for operations in environments that are difficult to access for humans. When these environments are dynamic and non-deterministic, like in collapsed buildings, the robots must coordinate their actions and the use of resources using planning. This paper presents Planner9, a hierarchical task network (HTN) planner that runs on groups of miniature mobile robots. These robots have limited computational power and memory, but are well connected through Wi-Fi. Planner9 takes advantage of this connectivity to distribute the planning over different robots. We have adapted the HTN algorithm to perform parallel search using A* and to limit the number of search nodes through lifting. We show that Planner9 scales well with the number of robots, even on non-linear tasks that involve recursions in their decompositions. We show that contrary to JSHOP2, Planner9 finds optimal plans.

Springer2009

Chargement

Staged parser combinators for efficient data processing

Thierry Coppey, Manohar Jonnalagedda, Martin Odersky, Tiark Rompf, Sandro Stucki

Parsers are ubiquitous in computing, and many applications depend on their performance for decoding data efficiently. Parser combinators are an intuitive tool for writing parsers: tight integration with the host language enables grammar specifications to be interleaved with processing of parse results. Unfortunately, parser combinators are typically slow due to the high overhead of the host language abstraction mechanisms that enable composition. We present a technique for eliminating such overhead. We use staging, a form of runtime code generation, to dissociate input parsing from parser composition, and eliminate intermediate data structures and computations associated with parser composition at staging time. A key challenge is to maintain support for input dependent grammars, which have no clear stage distinction. Our approach applies to top-down recursive-descent parsers as well as bottom-up nondeterministic parsers with key applications in dynamic programming on sequences, where we auto-generate code for parallel hardware. We achieve performance comparable to specialized, hand-written parsers.

ACM Press2014

Chargement