http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
The power of programmed grammars with graphs from various classes
Madalina Barbaiani,Cristina Bibire,J urgen Dassow,Aidan Delaney,Szilard Fazekas,Mihai Ionescu,Guangwu Liu,Atif Lodhi,Benedek Nagy 한국전산응용수학회 2006 Journal of applied mathematics & informatics Vol.22 No.1-2
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 re- stricts the generative power of programmed grammars with erasing rules and without appearance checking, too. We obtain that Eulerian, Hamil- tonian, planar and bipartite graphs and regular graphs of degree at least three are pr-universal in that sense that any language which can be gener- ated by programmed grammars (with erasing rules and without appearance checking) can be obtained by programmed grammars where the underly- ing 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.