Free Heyting Algebra Endomorphisms: Ruitenburg's Theorem and Beyond - Laboratoire d'Informatique et Systèmes Accéder directement au contenu
Article Dans Une Revue Mathematical Structures in Computer Science Année : 2019

Free Heyting Algebra Endomorphisms: Ruitenburg's Theorem and Beyond

Résumé

Ruitenburg's Theorem says that every endomorphism f of a finitely generated free Heyting algebra is ultimately periodic if f fixes all the generators but one. More precisely, there is N ≥ 0 such that f N +2 = f N , thus the period equals 2. We give a semantic proof of this theorem, using duality techniques and bounded bisimulation ranks. By the same techniques, we tackle investigation of arbitrary endomorphisms between free algebras. We show that they are not, in general, ultimately periodic. Yet, when they are (e.g. in the case of locally finite subvarieties), the period can be explicitly bounded as function of the cardinality of the set of generators.
Fichier principal
Vignette du fichier
main.pdf (311.25 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01969235 , version 1 (03-01-2019)

Identifiants

Citer

Silvio Silvio.Ghilardi@unimi.It Ghilardi, Luigi Santocanale. Free Heyting Algebra Endomorphisms: Ruitenburg's Theorem and Beyond. Mathematical Structures in Computer Science, inPress. ⟨hal-01969235⟩
153 Consultations
163 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More