Is Ramsey's theorem omega-automatic?

Abstract : We study the existence of infinite cliques in omega-automatic (hyper-)graphs. It turns out that the situation is much nicer than in general uncountable graphs, but not as nice as for automatic graphs. More specifically, we show that every uncountable omega-automatic graph contains an uncountable co-context-free clique or anticlique, but not necessarily a context-free (let alone regular) clique or anticlique. We also show that uncountable omega-automatic ternary hypergraphs need not have uncountable cliques or anticliques at all.
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.537-548, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00457041
Contributeur : Publications Loria <>
Soumis le : mardi 16 février 2010 - 14:51:06
Dernière modification le : jeudi 11 janvier 2018 - 06:20:16
Document(s) archivé(s) le : vendredi 18 juin 2010 - 18:46:46

Fichier

kuske.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00457041, version 1

Citation

Dietrich Kuske. Is Ramsey's theorem omega-automatic?. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.537-548, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00457041〉

Partager

Métriques

Consultations de la notice

135

Téléchargements de fichiers

128