On the regular structure of prefix rewriting

DOI10.1016/0304-3975(92)90278-NMaRDI QIDQ685354zbMATH OpenFDO

Authors Didier Caucal

Publication date 6 February 1994

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(92)90278-N

zbMATH Keywords

labelled word rewriting system prefix transition graph regular graph

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Graph theory (including graph drawing) in computer science (68R10)

Review text

A labelled word rewriting system \(R\) on an alphabet \(X\) and a set \(L\) of labels is a finite set of labelled transitions \(u@>a>>v\) where \(a\) is a label and \(u\) and \(v\) are words over \(X\). The prefix transition graph of \(R\) is the infinite set of labelled transitions \(uw@>a>>vw\) where \(u@>a>>v\) is a rule of \(R\) and \(w\) is a word over \(X\). We show that any prefix transition graph is effectively a regular graph of finite degree: it is produced from a finite graph by iterating the addition of a finite family of finite graphs. It turns out that the rational restrictions of the prefix transition graphs are exactly the regular graphs of finite degree. Furthermore we show that the prefix transition graphs and the regular graphs of finite degree have the same connected components and the same accessible subgraphs. Finally we establish that the prefix transition graphs corresponds to the transition graphs of pushdown automata. All constructions are effective.

Recommendations

Cites work

Cited in

(51)

This page was built for publication: On the regular structure of prefix rewriting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685354)