On Insertion Grammars with Maximum Parallel Derivation

Article type: Research Article

Authors: Dinu, Liviu P.

Affiliations: University of Bucharest, Faculty of Mathematics and Computer Science, Centre for Computational Linguistics, Academiei 14, 010014, Bucharest, Romania. ldinu@funinf.cs.unibuc.ro

Note: [] Address for correspondence: University of Bucharest, Faculty of Mathematics and Computer Science, Centre for Computational Linguistics, Academiei 14, 010014, Bucharest, Romania

Abstract: In this paper we investigate insertion grammars and explore their capacity to generate words parallelly by introducing parallel derivation (where more than one rule can be applied to the string in parallel) and maximum parallel derivation (where as many rules as possible are applied to the string in parallel). We compare the generative power of these grammars with context sensitive and context free grammars and with different variants of contextual grammars. We apply these grammars to syllabification in Romanian and provide arguments that they can also be used in a cognitive perspective.

Keywords: insertion grammars, parallel derivation, contextual grammars, parallel syllabification

DOI: 10.3233/FI-2009-108

Journal: Fundamenta Informaticae, vol. 93, no. 4, pp. 357-369, 2009