izpis_h1_title_alt

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

Abstract
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.

Language:English
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
Year:2012
Publisher:Springer-Verlag, Berlin Heidelberg
Number of pages:Str. 121-136
Numbering:7233
UDC:519.17
ISSN on article:0302-9743
COBISS.SI-ID:9507668 Link is opened in a new window
Views:426
Downloads:127
Metadata:XML RDF-CHPDL DC-XML DC-RDF
 
Average score:(0 votes)
Your score:Voting is allowed only to logged in users.
:
Share:AddThis
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.
Publisher:Springer
ISSN:0302-9743
COBISS.SI-ID:4292374 This link opens in a new window

Secondary language

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

Similar documents

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

Comments

Leave comment

You have to log in to leave a comment.

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

Back