ON USING SEMI-DYCK SETS TO ANALYSE COUPLED-CONTEXT-FREE LANGUAGES

Article type: Research Article

Authors: Hotz, Günter | Pitsch, Gisela

Affiliations: FB 14 - Informatik, Universität des Saarlandes, D-66123 Saarbrücken, Germany, e-mail: hotz/pitsch@cs.uni-sb.de

Note: [] This research has been supported by a Graduiertenkolleg-fellowship of the Deutsche Forschungs-gemeinschaft and by the ESPRIT Basic Research Action No. 6317 (ASMICS2).

Abstract: Coupled-Context-Free Grammars are a natural generalization of context-free grammars obtained by combining nonterminals to corresponding parentheses which can only be substituted simultaneously. Refering to their generative capacity we obtain an infinite hierarchy of languages that comprises the context-free ones as the first and all those generated by Tree Adjoining Grammars (TAGs) as the second element. The latter is important because today, TAGs are commonly used to model the syntax of natural languages. Here, we present a completely new approach to analyse this language hierarchy. It solves the word problem for the class of languages generated by TAGs in time O(n6), n length of the input, by reducing it to the analysis of sequences of parentheses.

DOI: 10.3233/FI-1997-291201

Journal: Fundamenta Informaticae, vol. 29, no. 1-2, pp. 1-26, 1997