Théorème de Rabin sur les arbres
From Wikipedia, the free encyclopedia
En informatique théorique, le théorème de Rabin sur les arbres énonce la décidabilité de la théorie monadique du second ordre de l'arbre binaire infini complet, mais aussi des arbres infinis d'arité finie fixée, et de l'arbre infini d'arité dénombrable. Ce théorème a été démontré par Michael Rabin en 1969[1],[2].
