2024/01/15 by Cardó, Carles
#68Q42 #68Q43 #F.4.2 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2401.07815
Context-free languages can be characterized in several ways. This article studies projective linearisations of languages of simple dependency trees, i.e., dependency trees in which a node can govern at most one node with a given syntactic function. We prove that the projective linearisations of local languages of simple dependency trees coincide with the context-free languages. Simple dependency trees suggest alternative dual notions of locality and projectivity, which permits defining a dual language for each context-free language. We call this new class of languages anti-context-free. These languages are related to some linguistic constructions exhibiting the so-called cross-serial dependencies that were historically important for the development of computational linguistics. We propose that this duality could be a relevant linguistic phenomenon.