(Re)introducing regular graph languages

Sorcha Gilroy, Adam Lopez, Sebastian Maneth, Pijus Simonaitis

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Distributions over strings and trees can be represented by probabilistic regular languages, which characterise many models in natural language processing. Re-
cently, several datasets have become available which represent natural language phenomena as graphs, so it is natural to ask whether there is an equivalent of probabilistic regular languages for graphs. This paper presents regular graph languages, a formalism due to Courcelle (1991) that has not previously been studied in natural language processing. RGL is crucially a subfamily of both Hyperedge Replacement Languages (HRL), which can be made probabilistic; and Monadic Second Order Languages (MSOL), which are closed under intersection. We give an accessible introduction to Courcelle’s proof that RGLs are in MSOL, providing clues about how RGL may relate to other recently introduced graph grammar formalisms.
Original languageEnglish
Title of host publicationProceedings of the 15th Meeting on the Mathematics of Language
PublisherAssociation for Computational Linguistics (ACL)
Number of pages14
Publication statusPublished - 14 Jul 2017
Event15th Meeting on the Mathematics of Language - London, United Kingdom
Duration: 13 Jul 201714 Jul 2017


Conference15th Meeting on the Mathematics of Language
Abbreviated titleMOL 2017
CountryUnited Kingdom
Internet address


Dive into the research topics of '(Re)introducing regular graph languages'. Together they form a unique fingerprint.

Cite this