Publication Details
Jumping Grammars
Modified grammars; discontinuous rewriting; generative power; jumping finite
automata; semilinearity; finite index.
This paper introduces and studies jumping grammars, which represent a grammatical
counterpart to the recently introduced jumping automata. These grammars are
conceptualized just like classical grammars except that during the applications
of their productions, they can jump over symbols in either direction within the
rewritten strings. More precisely, a jumping grammar rewrites a string z
according to a rule x -> y in such a way that it selects an occurrence of x in z,
erases it, and inserts y anywhere in the rewritten string, so this insertion may
occur at a different position than the erasure of x.
The paper concentrates its attention on investigating the generative power of
jumping grammars. More specifically, it compares this power with that of jumping
automata and that of classical grammars. A special attention is paid to various
context-free versions of jumping grammars, such as regular, right-linear, linear,
and context-free grammars of finite index. In addition, we study the
semilinearity of context-free, context-sensitive, and monotonous jumping
grammars. We also demonstrate that the general versions of jumping grammars
characterize the family of recursively enumerable languages. In its conclusion,
the paper formulates several open problems and suggests future investigation
areas.
@article{BUT119793,
author="Zbyněk {Křivka} and Alexandr {Meduna}",
title="Jumping Grammars",
journal="International Journal of Foundations of Computer Science",
year="2015",
volume="26",
number="6",
pages="709--731",
doi="10.1142/S0129054115500409",
issn="0129-0541",
url="https://www.fit.vut.cz/research/publication/10735/"
}