Système de transition

Un système de transition est pour décrire le comportement potentiel de systèmes discrets. Il se compose d’états et de transitions entre états, qui peuvent être étiquetés avec des étiquettes choisies dans un ensemble; la même étiquette peut apparaître sur plusieurs transitions.

Si le jeu d'étiquettes est un singleton, le système est essentiellement sans étiquette et une définition plus simple qui omet les étiquettes est possible.

Les systèmes de transition coïncident mathématiquement avec les systèmes de réécriture abstraits (comme expliqué plus loin dans cet article) et les graphes dirigés. Ils diffèrent des automates finis de plusieurs manières:
•    L'ensemble des états n'est pas nécessairement fini, ni même dénombrable.
•    L'ensemble des transitions n'est pas nécessairement fini, ni même dénombrable.
•    Aucun état "début" ou "final" n'est donné.

Les systèmes de transition peuvent être représentés sous forme de graphiques dirigés.

Le parcours d’arbre est une forme de parcours de graphe et fait référence au processus de visite (vérification et / ou la mise à jour) chaque noeud dans une structure de données d'arbre, exactement une fois. Ces traversées sont classées selon l'ordre dans lequel les nœuds sont visités. Les algorithmes suivants sont décrits pour un arbre binaire, mais ils peuvent également être généralisés à d'autres arbres.