×

On the regular structure of prefix rewriting. (English) Zbl 0780.68077

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.
Reviewer: Didier Caucal

MSC:

68Q42 Grammars and rewriting systems
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baeten, J. C.M.; Bergstra, J. A.; Klop, J. W., Decidability of bisimulation equivalence for processes generating context-free languages, (Lecture Notes in Computer Science, Vol. 259 (1987), Springer: Springer Berlin), 94-111 · Zbl 0635.68014
[2] Bauderon, M., On systems of equations defining infinite graphs, (Lecture Notes in Computer Science, Vol. 344 (1989), Springer: Springer Berlin), 54-73
[3] Bauderon, M., Infinite hypergraphs: basic properties and systems of equations, Internal Report I-8920 (1989)
[4] L. Boasson and M. Nivat, Centers of context-free languages, Internal Report LITP 84-44.; L. Boasson and M. Nivat, Centers of context-free languages, Internal Report LITP 84-44. · Zbl 0457.68082
[5] Büchi, R., Regular canonical systems, Arch. Math. Logik Grundlag., 6, 91-111 (1964) · Zbl 0129.26102
[6] Caucal, D., Récritures suffixes de mots, Report INRIA 871 (1988)
[7] Caucal, D.; Monfort, R., On the transition graphs of automata and grammars, (WG 90. WG 90, Lecture Notes in Computer Science, Vol. 484 (1990), Springer: Springer Berlin), 311-337 · Zbl 0768.68124
[8] Courcelle, B., The monadic second-order logic of graphs, II: Infinite graphs of bounded width, Math. Systems Theory, 21, 187-222 (1989) · Zbl 0694.68043
[9] Courcelle, B., The definability of equational graphs in monadic second order logic, (ICALP 89. ICALP 89, Lecture Notes in Computer Science, Vol. 372 (1989), Springer: Springer Berlin), 207-221 · Zbl 0686.68011
[10] M. Dauchet and S. Tison, The theory of ground rewrite systems is decidable, in: Proc. 5th IEEE Symp. LICS 90; M. Dauchet and S. Tison, The theory of ground rewrite systems is decidable, in: Proc. 5th IEEE Symp. LICS 90
[11] Frougny, C.; Sakarovitch, J., Rational relations with bounded delay, (Proc. 8th STACS 90. Proc. 8th STACS 90, Lecture Notes in Computer Science, Vol. 480 (1990), Springer: Springer Berlin), 50-63 · Zbl 0773.68045
[12] Habel, A., Hyperedge replacement: grammars and languages, (Dissertation (1989), University of Bremen) · Zbl 0787.68066
[13] Habel, A.; Kreowski, H. J., Some structural aspects of hypergraph languages generated by hyperedge replacement, (Lecture Notes in Computer Science, Vol. 247 (1987), Springer: Springer Berlin), 207-219 · Zbl 0635.68077
[14] Muller, D.; Schupp, P., The theory of ends, pushdown automata, and second order logic, Theoret. Comput. Sci., 37, 51-75 (1985) · Zbl 0605.03005
[15] Salomaa, A., Formal Languages, (ACM monograph series (1973), Academic Press: Academic Press New York) · Zbl 0900.68287
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.