Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 6:04:12 PM
Last modification on : Thursday, January 7, 2021 - 4:18:48 PM
Long-term archiving on: : Tuesday, April 12, 2011 - 6:39:20 PM


  • HAL Id : inria-00075362, version 1


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



Record views


Files downloads