Abstract

Important families of dependency graphs are STRONGLY equivalent to context-free languages whose strings encode the graphs. The consequences of this observation (in ACL 2017 ) increase (i) the scope of the classical context-free grammars by allowing them to generate non-trees, (ii) the relevance of strictly locally testable languages to nonlocal graphical properties, and (iii) the applicability of superbracketing schemes beyond the bracketing of single-headed phrase-structures. The second part of the talk is about the work in progress and considers minimal recursion in the encoded graphs. My preliminary experimental results (in FSMNLP 2017 ) on the Universal Dependencies v2 treebanks indicate that a quite small subset approximation of an encoded family of dependency graphs would already capture 99.994% of the primary dependency structures if the encoding scheme is IMPLICITLY extended to crossing brackets. This raises interesting questions about the expressiveness of the finite-state grammar over graph banks and its potential applications to linear time encoding and decoding tasks in dependency parsing and machine translation.