Construction par sous-ensemblesEn informatique théorique, et notamment en théorie des automates, l'algorithme appelé la construction par sous-ensembles, en anglais « powerset construction » ou « subset construction », est la méthode usuelle pour convertir un automate fini non déterministe (abrégé en « AFN ») en un automate fini déterministe (abrégé en « AFD ») équivalent, c'est-à-dire qui reconnaît le même langage rationnel. L'existence même d'une conversion, et l'existence d'un algorithme pour la réaliser, est remarquable et utile.
Automate quantiqueEn informatique quantique et en informatique théorique, un automate fini quantique est une généralisation des automates finis où un mot est accepté selon le résultat d'une certaine mesure. Il existe plusieurs modèles des automates finis quantiques ; le plus restrictif est celui des automates dits « measure-once » de ; un autre est celui des automates « measure-many » de . Ces deux modèles sont très différents l'un de l’autre ; le modèle « measure-once » se rapproche plus de la théorie classique des automates finis.
PalindromeLe palindrome (adjectif et substantif masculin), du grec / pálin (« en arrière ») et / drómos (« chemin, voie »), aussi appelé palindrome de lettres est une figure de style désignant un mot ou une phrase dont l'ordre des lettres reste le même qu'on les lise de gauche à droite ou de droite à gauche, comme dans la phrase ou encore à un accent près. Le palindrome est un cas particulier d'anacyclique (lequel est lui-même un cas particulier d'anagramme) comme « suce|écus », pour lequel la signification est la même dans les deux sens de lecture.
Abstract rewriting systemIn mathematical logic and theoretical computer science, an abstract rewriting system (also (abstract) reduction system or abstract rewrite system; abbreviated ARS) is a formalism that captures the quintessential notion and properties of rewriting systems. In its simplest form, an ARS is simply a set (of "objects") together with a binary relation, traditionally denoted with ; this definition can be further refined if we index (label) subsets of the binary relation.
Confluence (informatique)vignette|Le nom « confluence » est le même que celui utilisé en géographie : deux cours d'eau se rejoignent. En mathématiques, ou en informatique, la confluence d'une relation binaire est définie comme la propriété suivante : Pour tous éléments tels que et , il existe un élément tel que et . La confluence est équivalente à la propriété de Church-Rosser. La confluence locale est une propriété plus faible que la confluence, utile pour les systèmes de réécriture. Elle est définie par : Pour tous éléments tels que et , il existe un élément tel que et .
Réécriture (informatique)En informatique théorique, la réécriture (ou récriture) est un modèle de calcul dans lequel il s’agit de transformer des objets syntaxiques (mots, termes, lambda-termes, programmes, preuves, graphes, etc.) en appliquant des règles bien précises. La réécriture est utilisée en informatique, en algèbre, en logique mathématique et en linguistique. La réécriture est utilisée en pratique pour la gestion des courriers électroniques (dans le logiciel sendmail, les entêtes de courrier sont manipulées par des systèmes de réécriture) ou la génération et l'optimisation de code dans les compilateurs.
Transducteur finiEn informatique théorique, en linguistique, et en particulier en théorie des automates, un transducteur fini (appelé aussi transducteur à états finis par une traduction littérale de l'anglais finite state transducer) est un automate fini avec sorties. C'est une extension des automates finis. Ils opèrent en effet sur les mots sur un alphabet d'entrée et, au lieu de simplement accepter ou refuser le mot, ils le transforment, de manière parfois non déterministe, en un ou plusieurs mots sur un alphabet de sortie.
Minimisation d'un automate fini déterministevignette|upright=1.5|Dans cet automate, tous les états sont accessibles, les états c, d et e sont indistinguables, ainsi que les états a et b. vignette|upright=1.5|Automate minimal équivalent. Les états indistinguables sont regroupés en un seul état. En informatique théorique, et plus particulièrement en théorie des automates, la minimisation d'un automate fini déterministe est l'opération qui consiste à transformer un automate fini déterministe donné en un automate fini déterministe ayant le nombre minimal d'états et qui reconnaît le même langage rationnel.
Machine de TuringEn informatique théorique, une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur. Ce modèle a été imaginé par Alan Turing en 1936, en vue de donner une définition précise au concept d’algorithme ou de « procédure mécanique ». Il est toujours largement utilisé en informatique théorique, en particulier dans les domaines de la complexité algorithmique et de la calculabilité.
Automate fini alternantEn informatique théorique, et notamment en théorie des automates, un automate fini alternant est une extension des automates finis. Dans un automate fini non déterministe usuel, un mot est accepté si, parmi les états atteints, il y a au moins un état final. Dans automate fini alternant, c'est la valeur d'une fonction booléenne sur les états atteints qui définit la condition d'acceptation.
