Graphes canoniques de graphes algébriques. (Canonical graphs of algebraic graphs). (French) Zbl 0701.68082

Summary: Concerning algebraic grammars in reduced form, bisimulation in the graph of left derivations is known to be decidable. The quotient of the above graph by its greatest bisimulation, called the canonical graph, is indeed isomorphic to the graph of left derivations for another algebraic grammar in reduced form, produced by an effective procedure.


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


[1] J. C. M. BAETEN, J. A. BERGSTRA et J. W. KLOP, Decidability of Bisimulation Equivalence for Processes Generating Context-free Languages, LNCS 259, 1987, p. 94-111. Zbl0635.68014 MR910305 · Zbl 0635.68014
[2] D. CAUCAL, Décidabilité de l’égalité des langages algébriques infinitaires simples, LNCS 210, 1986, p. 37-48. Zbl0595.68072 MR827723 · Zbl 0595.68072
[3] D. CAUCAL, On the regular structure of prefix rewritings, Rapport interne 507, CAAP90 paraîtra dans LNCS, 1990. Zbl0786.68047 MR1075024 · Zbl 0786.68047
[4] P. M. COHN, Universal Algebra, Klumer Academic Publishers Group, 1981. MR620952
[5] B. COURCELLE, An Axiomatic Approach to the KH Algorithms, Math. Systems Theory, vol. 16, 1983, p. 191-231. Zbl0581.68032 MR702448 · Zbl 0581.68032
[6] I. GUESSARIAN, Algebraic Semantics, LNCS 99, 1981. Zbl0474.68010 MR617908 · Zbl 0474.68010
[7] D. MULLER et P. SCHUPP, The Theory of Ends, Pushdown Automata, and Second Order Logic, TCS 37, 1985, p. 51-75. Zbl0605.03005 MR796313 · Zbl 0605.03005
[8] D. PARK, Concurrency and Automata on Infinite Sequences, LNCS 104, 1981, p. 167-183. Zbl0457.68049 · Zbl 0457.68049
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.