Publication result detail

Jumping Grammars

KŘIVKA, Z.; MEDUNA, A.

Original Title

Jumping Grammars

English Title

Jumping Grammars

Type

WoS Article

Original Abstract

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.

English abstract

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.

Keywords

Modified grammars; discontinuous rewriting; generative power; jumping finite automata; semilinearity; finite index.

Key words in English

Modified grammars; discontinuous rewriting; generative power; jumping finite automata; semilinearity; finite index.

Authors

KŘIVKA, Z.; MEDUNA, A.

RIV year

2016

Released

01.10.2015

ISBN

0129-0541

Periodical

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

Volume

26

Number

6

State

Republic of Singapore

Pages from

709

Pages to

731

Pages count

23

URL

https://www.fit.vut.cz/research/publication/10735/

BibTex

@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/"
}

Documents

jumping_grammars