Publication result detail

Jumping Pure Grammars

MEDUNA, A.; KŘIVKA, Z.; KUČERA, J.

Original Title

Jumping Pure Grammars

English Title

Jumping Pure Grammars

Type

WoS Article

Original Abstract

This paper introduces and studies jumping pure grammars, which are conceptualized just like classical pure grammars except that during the applications of their productions, they can jump over symbols in either direction within the rewritten strings. The paper compares the generative power of jumping pure grammars with that of classical pure grammars while distinguishing between their versions with and without erasing productions. Apart from sequential versions, the paper makes an analogical study in terms of parallel versions of jumping pure grammars represented by 0L grammars.

English abstract

This paper introduces and studies jumping pure grammars, which are conceptualized just like classical pure grammars except that during the applications of their productions, they can jump over symbols in either direction within the rewritten strings. The paper compares the generative power of jumping pure grammars with that of classical pure grammars while distinguishing between their versions with and without erasing productions. Apart from sequential versions, the paper makes an analogical study in terms of parallel versions of jumping pure grammars represented by 0L grammars.

Keywords

jumping grammars, pure grammars, jumping rewriting, 0L languages, parallel rewriting, pure context-free languages

Key words in English

jumping grammars, pure grammars, jumping rewriting, 0L languages, parallel rewriting, pure context-free languages

Authors

MEDUNA, A.; KŘIVKA, Z.; KUČERA, J.

RIV year

2019

Released

31.01.2019

ISBN

0010-4620

Periodical

COMPUTER JOURNAL

Volume

62

Number

1

State

United Kingdom of Great Britain and Northern Ireland

Pages from

30

Pages to

41

Pages count

12

URL

https://doi.org/10.1093/comjnl/bxy027

BibTex

@article{BUT155634,
  author="Alexandr {Meduna} and Zbyněk {Křivka} and Jiří {Kučera}",
  title="Jumping Pure Grammars",
  journal="COMPUTER JOURNAL",
  year="2019",
  volume="62",
  number="1",
  pages="30--41",
  doi="10.1093/comjnl/bxy027",
  issn="0010-4620",
  url="https://doi.org/10.1093/comjnl/bxy027"
}

Documents

submitted version
print version (with page numbers)