|
|||||
|
|
The power of programmed grammars with graphs from various classes |
|
| Authors: | Madalina Barbaiani Cristina Bibire Jürgen Dassow Aidan Delaney Szilárd Fazekas Mihai Ionescu Guangwu Liu Atif Lodhi Benedek Nagy |
| Institution: | 1. Research Group on Mathematical Linguistics, Rovira i Virgili University, Tarragona, Spain 2. Fakult?t für Informatik, Otto-von-Guericke-Universit?t Magdeburg, Germany 3. Department of Computer Science, NUI Maynooth, Maynooth, Co., Kildare, Ireland 4. Faculty of Informatics, University of Debrecen, Debrecen, Hungary 5. Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan, People’s Republic of China |
| Abstract: | 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. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |