Name
Abstract | ||
|---|---|---|
We consider a pushdown automaton as a word-rewriting system with labelled rules applied only in a prefix way. The notion of pushdown transition graph is then extended to the notion of prefix transition graph generated by a word-rewriting system and accessible from a given axiom. Such accessible prefix transition graphs are context-free graphs in the sense of Muller and Schupp (1985), and we show that they are also the rooted pattern graphs of finite degree, where a pattern graph is a graph produced from a finite graph by iterating the addition of a finite family of finite graphs (the patterns). Furthermore, this characterization is effective in the following sense: any finite family of patterns generating a rooted graph G of finite degree, is mapped effectively into a word-rewriting system R such that the accessible prefix transition graph of R is isomorphic to G , and the reverse transformation is effective. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1016/0304-3975(92)90278-N | CAAP '90 Selected papers of the conference on Fifteenth colloquium on trees in algebra and programming |
Keywords | DocType | Volume |
regular structure | Journal | 106 |
Issue | ISSN | ISBN |
1 | Theoretical Computer Science | 0-387-52590-4 |
Citations | PageRank | References |
96 | 6.67 | 12 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Didier Caucal | 1 | 470 | 39.15 |