Relational graph rewritings

Yoshihiro Mizoguchi, Yasuo Kawahara

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)


This note presents a new formalization of graph rewritings which generalizes traditional graph rewritings. Relational notions of graphs and their rewritings are introduced and several properties about graph rewritings are discussed using relational calculus (theory of binary relations). Single pushout approaches to graph rewritings proposed by Raoult and Kennaway are compared with our rewritings of relational (labeled) graph. Moreover, a more general sufficient condition for two rewritings to commute and a theorem concerning critical pairs useful to demonstrate the confluency of graph rewriting systems are also given.

Original languageEnglish
Pages (from-to)311-328
Number of pages18
JournalTheoretical Computer Science
Issue number1-2
Publication statusPublished - Apr 17 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Relational graph rewritings'. Together they form a unique fingerprint.

Cite this