Events Calendar

NL Seminar-Parsing Graphs with Regular Graph Grammars

Speaker: Sorcha Gilroy, University of Edinburgh

Talk Title: Parsing Graphs with Regular Graph Grammars

Series: Natural Language Seminar

Abstract: Recently, several datasets have become available which represent natural language phenomena as graphs. Hyperedge Replacement Languages HRL have been the focus of much attention as a formalism to represent the graphs in these datasets. Chiang et al. 2013 prove that HRL graphs can be parsed in polynomial time with respect to the size of the input graph. We believe that HRL may be more expressive than is necessary to represent semantic graphs and we propose looking at Regular Graph Languages RGL Courcelle, 1991, which is a subfamily of HRL, as a possible alternative. We provide a top down parsing algorithm for RGL that runs in time linear in the size of the input graph.



Biography: Sorcha is a 2nd year PhD student at the University of Edinburgh and is a student in the Center for Doctoral Training in Data Science. Her PhD is focused on formal languages of graphs for NLP and her supervisors are Adam Lopez and Sebastian Maneth. She completed her undergraduate degree in mathematical sciences at University College Cork and her masters degree in data science at the University of Edinburgh. She is at ISI as an intern in the NLP group.

Host: Marjan Ghazvininejad and Kevin Knight

More Info: http://nlg.isi.edu/nl-seminar/

Webcast: http://webcastermshd.isi.edu/Mediasite/Play/c523b7ef95b443e8b29cfac3092e00081d

Location: Information Science Institute (ISI) - 11th Flr Conf Rm # 1135, Marina Del Rey

WebCast Link: http://webcastermshd.isi.edu/Mediasite/Play/c523b7ef95b443e8b29cfac3092e00081d

Audiences: Everyone Is Invited

Contact: Peter Zamar

Event Link: http://nlg.isi.edu/nl-seminar/