Undirected Graph Languages
Haizhong Shi · 2011
Undirected graph is a elementary concept of graph theory.Graph semigroup is a concept proposed in 1991.A concept of undirected graph language was proposed with undirected graph and graph semigroup.Furthermore,a subclass of undirected graph language,plane graph language was studied.It is proved that a graph language is a plane graph language if and only if it contains no subdivision graph language of K5 language or K3,3 language.In addition,four open problems were proposed.One of them:what is the relations between undirected graph language and regular language,context free language,context sensitive language,phrase structure language,respectively.