Separation Results for Separated Apex NLC and NCE Graph Languages

摘要

Relations among various types of node replacement graph languages are known in the literature but there has remained a gap in the hierarchy of these graph languages. The present paper fills this gap by proving a separation result for k-separated apex graph languages and by extending a known result for k-separated graph languages. This yields, together with other known relations, a complete hierarchy of NLC, NCE, eNCE graph languages and their k-separated, linear, and/or apex subclasses.