Title: Characterizing compressibility of disjoint subgraphs with NLC grammars
Authors: Brijder, Robert
Blockeel, Hendrik
Issue Date: 2011
Publisher: Springer
Host Document: Proceedings of LATA-2011, Fifth International Conference on Language and Automata Theory and Applications vol:6638 pages:167-178
Series Title: Lecture Notes in Computer Science
Conference: International Conference on Language and Automata Theory and Applications edition:5 location:Tarragona date:26-28 May 2011
Abstract: We consider compression of a given set S of isomorphic and disjoint subgraphs of a graph G using node label controlled (NLC) graph grammars. Given S and G, we characterize whether or not there exists a NLC graph grammar consisting of exactly one rule such that (1) each of the subgraphs S in G are compressed (i.e., replaced by a nonterminal) in the (unique) initial graph I , and (2) the set of generated terminal graphs is the singleton {G}.
Description: acceptance rate: 39%
ISBN: 978-3-642-21253-6
ISSN: 0302-9743
Publication status: published
KU Leuven publication type: IC
Appears in Collections:Informatics Section

Files in This Item:
File Description Status SizeFormat
paper 50.pdfmain article Published 147KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science