Publication Details

Jumping Pure Grammars

MEDUNA, A.; KŘIVKA, Z.; KUČERA, J. Jumping Pure Grammars. COMPUTER JOURNAL, 2019, vol. 62, no. 1, p. 30-41. ISSN: 0010-4620.
Czech title
Skákající čisté gramatiky
Type
journal article
Language
English
Authors
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Křivka Zbyněk, Ing., Ph.D. (DIFS)
Kučera Jiří, Ing., Ph.D.
URL
Keywords

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

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.

Published
2019
Pages
30–41
Journal
COMPUTER JOURNAL, vol. 62, no. 1, ISSN 0010-4620
DOI
10.1093/comjnl/bxy027
UT WoS
000462595500003
EID Scopus
2-s2.0-85062734639
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"
}
Files
Back to top