Hereditary Rigid Relations.

Abstract : An h-ary relation ρ on a finite set A is said to be hereditarily rigid if the unary partial functions on A that preserve ρ are the subfunctions of the identity map or of constant maps. A family of relations F is said to be hereditarily strongly rigid if the partial functions on A that preserve every ρ ∈ F are the subfunctions of projections or constant functions. In this paper we show that hereditarily rigid relations exist and we give a lower bound on their arities. We also prove that no finite hereditarily strongly rigid families of relations exist and we also construct an infinite hereditarily strongly rigid family of relations.
Type de document :
Communication dans un congrès
45th IEEE International Symposium on Multiple-Valued Logic (ISMVL 2015), May 2015, Waterloo, Canada. Proceedings of 45th IEEE International Symposium on Multiple-Valued Logic (ISMVL 2015), IEEE Computer Society. 〈http://mvl.jpn.org/ISMVL2015/index.php〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01175699
Contributeur : Miguel Couceiro <>
Soumis le : samedi 11 juillet 2015 - 18:14:57
Dernière modification le : jeudi 5 avril 2018 - 09:56:01

Identifiants

  • HAL Id : hal-01175699, version 1

Citation

Miguel Couceiro, Lucien Haddad, Maurice Pouzet, Karsten Schölzel. Hereditary Rigid Relations.. 45th IEEE International Symposium on Multiple-Valued Logic (ISMVL 2015), May 2015, Waterloo, Canada. Proceedings of 45th IEEE International Symposium on Multiple-Valued Logic (ISMVL 2015), IEEE Computer Society. 〈http://mvl.jpn.org/ISMVL2015/index.php〉. 〈hal-01175699〉

Partager

Métriques

Consultations de la notice

434