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.

Язык оригиналаанглийский
Страницы (с-по)341-351
Число страниц11
ЖурналFundamenta Informaticae
Том64
Номер выпуска1-4
СостояниеОпубликовано - 7 сен 2005
Опубликовано для внешнего пользованияДа

    Предметные области Scopus

  • Компьютерная графика и машинное проектирования
  • Программный продукт
  • Прикладная математика
  • Безопасность, риски, качество и надежность

ID: 41144246