On external presentations of infinite graphs

Abstract : The vertices of a finite state system are usually a subset of the natural numbers. Most algorithms relative to these systems only use this fact to select vertices. For infinite state systems, however, the situation is different: in particular, for such systems having a finite description, each state of the system is a configuration of some machine. Then most algorithmic approaches rely on the structure of these configurations. Such characterisations are said internal. In order to apply algorithms detecting a structural property (like identifying connected components) one may have first to transform the system in order to fit the description needed for the algorithm. The problem of internal characterisation is that it hides structural properties, and each solution becomes ad hoc relatively to the form of the configurations. On the contrary, external characterisations avoid explicit naming of the vertices. Such characterisation are mostly defined via graph transformations. In this paper we present two kind of external characterisations: deterministic graph rewriting, which in turn characterise regular graphs, deterministic context-free languages, and rational graphs. Inverse substitution from a generator (like the complete binary tree) provides characterisation for prefix-recognizable graphs, the Caucal Hierarchy and rational graphs. We illustrate how these characterisation provide an efficient tool for the representation of infinite state systems.
Type de document :
Communication dans un congrès
Axel Legay and Azadeh Farzan. Infinity (International Workshop on Verification of Infinite-State Systems), 2009, Bologne, Italy. EPTCS, 10, pp.23-35, 2009
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00525379
Contributeur : Christophe Morvan <>
Soumis le : lundi 11 octobre 2010 - 16:57:24
Dernière modification le : mercredi 29 novembre 2017 - 15:09:48
Document(s) archivé(s) le : jeudi 25 octobre 2012 - 16:51:04

Fichier

finaleOfficielle.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : inria-00525379, version 1

Collections

Citation

Christophe Morvan. On external presentations of infinite graphs. Axel Legay and Azadeh Farzan. Infinity (International Workshop on Verification of Infinite-State Systems), 2009, Bologne, Italy. EPTCS, 10, pp.23-35, 2009. 〈inria-00525379〉

Partager

Métriques

Consultations de la notice

136

Téléchargements de fichiers

107