Logique temporelle linéaireEn logique, la logique temporelle linéaire (LTL) est une logique temporelle modale avec des modalités se référant au temps. En LTL, on peut coder des formules sur l'avenir d'un chemin infini dans un système de transitions, par exemple une condition finira par être vraie, une condition sera vraie jusqu'à ce qu'une autre devienne vraie, etc. Cette logique est plus faible que la logique CTL*, qui permet d'exprimer des conditions sur des ramifications de chemins et pas seulement sur un seul chemin.
Computation tree logicComputation tree logic (CTL) is a branching-time logic, meaning that its model of time is a tree-like structure in which the future is not determined; there are different paths in the future, any one of which might be an actual path that is realized. It is used in formal verification of software or hardware artifacts, typically by software applications known as model checkers, which determine if a given artifact possesses safety or liveness properties. For example, CTL can specify that when some initial condition is satisfied (e.
Topologievignette|Déformation continue d'une tasse avec une anse, en un tore (bouée). thumb|Un ruban de Möbius est une surface fermée dont le bord se réduit à un cercle. De tels objets sont des sujets étudiés par la topologie. La topologie est la branche des mathématiques qui étudie les propriétés d'objets géométriques préservées par déformation continue sans arrachage ni recollement, comme un élastique que l’on peut tendre sans le rompre.
Graphe orienté acycliqueEn théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG), est un graphe orienté qui ne possède pas de circuit. Un tel graphe peut être vu comme une hiérarchie. Un graphe orienté acyclique est un graphe orienté qui ne possède pas de circuit. On peut toujours trouver un sous-graphe couvrant d’un graphe orienté acyclique qui soit un arbre (resp. une forêt). Dans un graphe orienté acyclique, la relation d'accessibilité R(u, v) définie par « il existe un chemin de u à v » est une relation d'ordre partielle.
Espace topologiqueLa topologie générale est une branche des mathématiques qui fournit un vocabulaire et un cadre général pour traiter des notions de limite, de continuité, et de voisinage. Les espaces topologiques forment le socle conceptuel permettant de définir ces notions. Elles sont suffisamment générales pour s'appliquer à un grand nombre de situations différentes : ensembles finis, ensembles discrets, espaces de la géométrie euclidienne, espaces numériques à n dimensions, espaces fonctionnels plus complexes, mais aussi en géométrie algébrique.
Logique temporelleLa logique temporelle est une branche de la logique mathématique et plus précisément de la logique modale, qui est formalisée de plusieurs manières. La caractéristique commune de ces formalisations réside en l'ajout de modalités (autrement dit de « transformateurs de prédicats ») liées au temps ; par exemple, une formule typique de la logique modale est la formule , qui se lit : « la formule est satisfaite jusqu'à ce que la formule le soit » et qui signifie que l'on cherche à garantir qu'une certaine propriété (ici ) est satisfaite pendant tout le temps qui court avant qu'une autre formule (ici ) le soit.
Tri topologiqueEn théorie des graphes, et plus spécialement en algorithmique des graphes, un tri topologique d'un graphe acyclique orienté (ou dag, de l'anglais directed acyclic graph) est un ordre total sur l'ensemble des sommets, dans lequel s précède t pour tout arc d'un sommet s à un sommet t. En d'autres termes, un tri topologique est une extension linéaire de l'ordre partiel sur les sommets déterminés par les arcs. Soit un graphe orienté avec et . Un ordre topologique sur ce graphe peut donner par exemple la succession des sommets 7, 1, 2, 9, 8, 4, 3, 5, 6.
Ensemble partiellement ordonnéEn mathématiques, un ensemble partiellement ordonné (parfois appelé poset d'après l'anglais partially ordered set) formalise et généralise la notion intuitive d'ordre ou d'arrangement entre les éléments d'un ensemble. Un ensemble partiellement ordonné est un ensemble muni d'une relation d'ordre qui indique que pour certains couples d'éléments, l'un est plus petit que l'autre. Tous les éléments ne sont pas forcément comparables, contrairement au cas d'un ensemble muni d'un ordre total.
Acyclic orientationIn graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orientation. The chromatic number of any graph equals one more than the length of the longest path in an acyclic orientation chosen to minimize this path length. Acyclic orientations are also related to colorings through the chromatic polynomial, which counts both acyclic orientations and colorings.
Multi-arbreEn combinatoire et en théorie des ordres, le terme multi-arbre peut décrire l'une des deux structures suivantes : un graphe orienté acyclique dans lequel l'ensemble des sommets accessibles depuis un nœud est toujours un arbre, ou un ensemble partiellement ordonné dans lequel il n'existe pas quatre éléments a, b, c, et d qui forment un sous-ordre en diamant, avec et mais où b et c sont incomparables (un tel ensemble ordonné est aussi appelé diamond-free poset (ou ordre partiel sans diamant).
