The power of programmed grammars with graphs from various classes

Aidan Delaney, Madalina Barbaiani, Cristina Bibire, Jürgen Dassow, Szilárd Fazekas, Mihai Ionescu, Guangwu Liu, Atif Lodhi, Benedek Nagy

Research output: Contribution to journalArticlepeer-review


Programmed grammars, one of the most important and well investigated classes of grammars with context-free rules and a mechanism controlling the application of the rules, can be described by graphs. We investigate whether or not the restriction to special classes of graphs restricts the generative power of programmed grammars with erasing rules and without appearance checking, too. We obtain that Eulerian, Hamiltonian, planar and bipartite graphs and regular graphs of degree at least three are pr-universal in that sense that any language which can be generated by programmed grammars (with erasing rules and without appearance checking) can be obtained by programmed grammars where the underlying graph belongs to the given special class of graphs, whereas complete graphs, regular graphs of degree 2 and backbone graphs lead to proper subfamilies of the family of programmed languages.
Original languageEnglish
Pages (from-to)21-38
Number of pages18
JournalJournal of Applied Mathematics and Computing
Issue number1-2
Publication statusPublished - 1 Sept 2006


  • Programmed grammars and languages
  • Graph controlled grammars and languages


Dive into the research topics of 'The power of programmed grammars with graphs from various classes'. Together they form a unique fingerprint.

Cite this