Graph grammar induction as a parser-controlled heuristic search process
Fürst, Luka (Author), Mernik, Marjan (Author), Mahnič, Viljan (Author)

URLURL - Presentation file, Visit http://eprints.fri.uni-lj.si/1936/ This link opens in a new window

A graph grammar is a generative description of a graph language (a possibly infinite set of graphs). In this paper, we present a novel algorithm for inducing a graph grammar from a given set of 'positive' and 'negative' graphs. The algorithm is guaranteed to produce a grammar that can generate all of the positive and none of the negative input graphs. Driven by a heuristic specific-to-general search process, the algorithm tries to find a small grammar that generalizes beyond the positive input set. During the search, the algorithm employs a graph grammar parser to eliminate the candidate grammars that can generate at least one negative input graph. We validate our method by inducing grammars for chemical structural formulas and flowcharts and thereby show its potential applicability to chemical engineering and visual programming.

Keywords:grafne gramatike, indukcija grafnih gramatik, sintaksna analiza z grafnimi gramatikami, hevristično iskanje
Work type:Not categorized (r6)
Tipology:1.08 - Published Scientific Conference Contribution
Organization:FRI - Faculty of computer and information science
Publisher:Springer-Verlag, Berlin Heidelberg
Number of pages:Str. 121-136
ISSN on article:0302-9743
COBISS.SI-ID:9507668 Link is opened in a new window
Average score:(0 votes)
Your score:Voting is allowed only to logged in users.
AddThis uses cookies that require your consent. Edit consent...

Record is a part of a proceedings

Title:Applications of graph transformations with industrial relevance
COBISS.SI-ID:9507156 This link opens in a new window

Record is a part of a journal

Title:Lecture notes in computer science
Shortened title:Lect. notes comput. sci.
COBISS.SI-ID:4292374 This link opens in a new window

Secondary language

Keywords:graph grammars, graph grammar induction, graph grammar parsing, heuristic search

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:


Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
There are no comments!