On the regular structure of prefix rewritings - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1990

On the regular structure of prefix rewritings

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-1196.pdf (1.35 Mo) Télécharger le fichier

Dates et versions

inria-00075362 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00075362 , version 1

Citer

Didier Caucal. On the regular structure of prefix rewritings. [Research Report] RR-1196, INRIA. 1990. ⟨inria-00075362⟩
80 Consultations
38 Téléchargements

Partager

Gmail Facebook X LinkedIn More