On the regular structure of prefix rewritings

Didier Caucal 1
1 MICAS - Modèles et implémentation des calculs syntaxiques
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires
Abstract : We can consider a pushdown automaton as a word rewriting system with labelled rules applied only in a prefix way. The notion of context-free graph, defined by Muller and Schupp is then extended to the notion of prefix transition graph of a word rewriting system. Prefix transition graphs are context-free graphs, and we show they are also the rooted pattern graphs of finite degree, where a pattern graph produced from a finite graph by iterating the addition of a finite family of finite graphs (the patterns). Furthermore, this characterisation is effective in the following sense : any finite family of patterns generating a graph G having a finite degree and a root, is mapped effectively into a rewriting system R on words such that the prefix transition graph of R is isomorphic to G, and the reverse transformation is effective.
Type de document :
Rapport
[Research Report] RR-1196, INRIA. 1990
Liste complète des métadonnées

https://hal.inria.fr/inria-00075362
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 18:04:12
Dernière modification le : vendredi 13 juillet 2018 - 16:00:04
Document(s) archivé(s) le : mardi 12 avril 2011 - 18:39:20

Fichiers

Identifiants

  • HAL Id : inria-00075362, version 1

Citation

Didier Caucal. On the regular structure of prefix rewritings. [Research Report] RR-1196, INRIA. 1990. 〈inria-00075362〉

Partager

Métriques

Consultations de la notice

98

Téléchargements de fichiers

49