Title :
Properties of NLC Languages Squeezed with Hypercube Graphs
Author :
Bharathi, S. Jeya ; Vadivu, M. Saravana ; Thiagarajan, K.
Author_Institution :
Dept. of Math., Thiagarajar Coll. of Eng., Madurai, India
Abstract :
The hypercube is a generalization of 3-cube to n dimensions, also called an n-cube or measure polytope. In this paper we define boundary edNCE recursive graph grammar and generate the language for the hypercube. For a graph grammar G with a graph-theoretical property ψ, let Lψ(G) Ψ be the language L(G) squeezed with ψ i.e., L(G) ΩL(ψ). This paper presents result on language-theoretic properties (such as membership and other decision properties) of NLC, B-edNCE languages squeezed with hyper cube graphs. We show that LQn (G) is in NP complete.
Keywords :
computational complexity; graph grammars; graph theory; NLC languages; NP complete; edNCE recursive graph grammar; graph-theoretical property; hypercube graphs; language-theoretic properties; Bipartite graph; Context; Educational institutions; Grammar; Hypercubes; Production; Graph grammar; Hamiltonian; NP complete; edNCE graph grammar;
Conference_Titel :
Bio-Inspired Computing: Theories and Applications (BIC-TA), 2011 Sixth International Conference on
Conference_Location :
Penang
Print_ISBN :
978-1-4577-1092-6
DOI :
10.1109/BIC-TA.2011.3
