Contextual Grammars with Uniform Sets of Trajectories

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

Article type: Research Article

Authors: Okhotin, Alexander | Salomaa, Kai

Affiliations: School of Computing, Queen's University, Kingston, Ontario K7L 3N6, Canada. {okhotin,ksalomaa}@cs.queensu.ca

Note: [] Address for correspondence: School of Computing, Queen's University, Kingston, Ontario K7L 3N6, Canada

Abstract: A uniformcontextual grammar with contexts shuffled along trajectories uses the same set of trajectories for each context. We prove that when the alphabet has at least two symbols, the nonuniform contextual grammars with trajectories are strictly more powerful than the uniform variant. For unary alphabets the generative power of the two variants coincides, and the same is true for grammars where the sets of trajectories are regular or context-free.

Keywords: Contextual grammar, trajectory, regular language, context-free language

Journal: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 341-351, 2005