Marcus External Contextual Grammars: From One to Many Dimensions

Issue title: Contagious Creativity – In Honor of the 80th Birthday of Professor Solomon Marcus

Article type: Research Article

Authors: Mitrana, Victor

Affiliations: Faculty of Mathematics and Computer Science, University of Bucharest, Str. Academiei 14, 70109, Bucharest, Romania and Research Group on Mathematical Linguistics, Rovira i Virgili University, Pça. Imperial Tàrraco 1, 43005 Tarragona, Spain. [email protected]

Note: [] Address for correspondence: Faculty of Mathematics and Computer Science, University of Bucharest, Str. Academiei 14, 70109, Bucharest, Romania

Abstract: This work is a continuation of [9]. We extend the multi-dimensional external contextual grammars introduced in the aforementioned work with the possibility of adjoining contexts in a selective way. An investigation of some mathematical properties (computational power and recognition complexity) of these new variants of contextual grammars is done via a constant comparison with the corresponding properties of classic Marcus external contextual grammars with or without choice.

Keywords: External contextual grammars, multi-dimensional external contextual grammars, range concatenation grammars

Journal: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 307-316, 2005