Approximating Dependency Grammars through Intersection of Regular Languages

Abstract. The paper formulates projective dependency grammars in terms of constraints on a string based encoding of dependency trees and develops an approach to obtain a regular approximation for these grammars. In the approach, dependency analyses are encoded with bal-anced bracketing that encodes dependency relations among the words of the analyzed sentence. The brackets, thus, indicate dependencies rather than delimit phrases. The encoding allows expressing dependency rules (in the sense of Hays and Gaifman) using a semi-Dyck language and a so-called context restriction operation. When the semi-Dyck language in the representation is replaced with a regular restriction of it, we obtain an approximation for the original dependency grammar.