Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

Concept

Automate fini

thumb|upright=2|Fig. 1 : Une hiérarchie d'automates. Un automate fini ou automate avec un nombre fini d'états (en anglais finite-state automaton ou finite state machine ou FSM) est un modèle mathématique de calcul, utilisé dans de nombreuses circonstances, allant de la conception de programmes informatiques et de circuits en logique séquentielle aux applications dans des protocoles de communication, en passant par le contrôle des processus, la linguistique et même la biologie. Un automate fini est une construction mathématique abstraite, susceptible d'être dans un nombre fini détats, mais étant un moment donné dans un seul état à la fois ; l'état dans lequel il se trouve alors est appelé l'« état courant ». Le passage d'un état à un autre est activé par un événement ou une condition ; ce passage est appelé une « transition ». Un automate particulier est défini par l'ensemble de ses états et l'ensemble de ses transitions. On rencontre couramment des automates finis dans de nombreux ap

À 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 (100)

Chargement

Afficher plus

Publications associées

Chargement

Personnes associées (28)

Personnes associées

Chargement

Unités associées (20)

Unités associées

Chargement

Concepts associés (61)

Concepts associés

Chargement

Cours associés (82)

Cours associés

Chargement

Séances de cours associées (191)

Afficher plus

Séances de cours associées

Chargement

Théorie des automates

En informatique théorique, l'objectif de la théorie des automates est de proposer des modèles de mécanismes mathématiques qui formalisent les méthodes de calcul. Cette théorie est le fondement de pl

Automate fini déterministe

Un automate fini déterministe, parfois abrégé en AFD (en anglais deterministic finite automaton, abrégé en DFA) est un automate fini dont les transitions à partir de chaque état sont déterminées

Algorithme

thumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de

EE-110: Logic systems (for MT)

Ce cours couvre les fondements des systèmes numériques. Sur la base d'algèbre Booléenne et de circuitscombinatoires et séquentiels incluant les machines d'états finis, les methodes d'analyse et de synthèse de systèmelogiques sont étudiées et appliquée

EE-334: Digital systems design

Students will acquire basic knowledge about methodologies and tools for the design, optimization, and verification of custom digital systems/hardware. They learn how to design synchronous digital circuits on register transfer level, analyse their timing and implement them in VHDL and on FPGAs.

CS-472: Design technologies for integrated systems

Hardware compilation is the process of transforming specialized hardware description languages into circuit descriptions, which are iteratively refined, detailed and optimized. The course presents algorithms, tools and methods for hardware compilation and logic synthesis.

PROFACTORY: Improving IoT Security via Formalized Protocol Customization

Mathias Josef Payer, Fei Wang, Duo Xu, Xiangyu Zhang

As IoT applications gain widespread adoption, it becomes important to design and implement IoT protocols with security. Existing research in protocol security reveals that the majority of disclosed protocol vulnerabilities are caused by incorrectly implemented message parsing and network state machines. Instead of testing and fixing those bugs after development, which is extremely expensive, we would like to avert them upfront. For this purpose, we propose PROFACTORY which formally and unambiguously models a protocol, checks model correctness, and generates a secure protocol implementation. We leverage PROFACTORY to generate a group of IoT protocols in the Bluetooth and Zigbee families and the evaluation demonstrates that 82 known vulnerabilities are averted. PROFACTORY will be publicly available [1].

USENIX ASSOC2022

Chargement

The weakest failure detector for eventual consistency

Rachid Guerraoui, Pierre Sens

In its classical form, a consistent replicated service requires all replicas to witness the same evolution of the service state. If we consider an asynchronous messagepassing environment in which processes might fail by crashing, and assume that a majority of processes are correct, then the necessary and sufficient information about failures for implementing a general state machine replication scheme ensuring consistency is captured by the Omega failure detector. This paper shows that in such a message-passing environment, Omega is also the weakest failure detector to implement an eventually consistent replicated service, where replicas are expected to agree on the evolution of the service state only after some (a priori unknown) time. In fact, we show that Omega is the weakest to implement eventual consistency in any message-passing environment, i.e., under any assumption on when and where failures might occur. Ensuring (strong) consistency in any environment requires, in addition to Omega, the quorum failure detector S. Our paper thus captures, for the first time, an exact computational difference between building a replicated state machine that ensures consistency and one that only ensures eventual consistency.

2019

Chargement

The Weakest Failure Detector for Eventual Consistency

Rachid Guerraoui, Pierre Sens

In its classical form, a consistent replicated service requires all replicas to witness the same evolution of the service state. Assuming a message-passing environment with a majority of correct processes, the necessary and sufficient information about failures for implementing a general state machine replication scheme ensuring consistency is captured by the ω failure detector. This paper shows that in such a message-passing environment, ω is also the weakest failure detector to implement an eventually consistent replicated service, where replicas are expected to agree on the evolution of the service state only after some (a priori unknown) time. In fact, we show that ω is the weakest to implement eventual consistency in any message-passing environment, i.e., under any assumption on when and where failures might occur. Ensuring (strong) consistency in any environment requires, in addition to ω, the quorum failure detector Σ. Our paper thus captures, for the first time, an exact computational difference between building a replicated state machine that ensures consistency and one that only ensures eventual consistency. © Copyright 2015 ACM.

ACM Press2015

Chargement

Afficher plus