Publication result detail

Solutions To Four Open Problems Concerning Controlled Pure Grammar Systems

MEDUNA, A.; VRÁBEL, L.; ZEMEK, P.

Original Title

Solutions To Four Open Problems Concerning Controlled Pure Grammar Systems

English Title

Solutions To Four Open Problems Concerning Controlled Pure Grammar Systems

Type

WoS Article

Original Abstract

In this paper, we address several open problems concerning pure grammar systems (pGSs) and their controlled versions. More specifically, we prove the following four results. (I) Regular-controlled pGSs having a single component define the family of regular languages. (II) pGSs having two components controlled by infinite regular languages define the family of recursively enumerable languages. (III) Regular-controlled pGSs without any erasing rules define the family of regular languages not containing the empty string. (IV) pGSs define a proper subfamily of the family of regular languages.

English abstract

In this paper, we address several open problems concerning pure grammar systems (pGSs) and their controlled versions. More specifically, we prove the following four results. (I) Regular-controlled pGSs having a single component define the family of regular languages. (II) pGSs having two components controlled by infinite regular languages define the family of recursively enumerable languages. (III) Regular-controlled pGSs without any erasing rules define the family of regular languages not containing the empty string. (IV) pGSs define a proper subfamily of the family of regular languages.

Keywords

formal languages, pure grammar systems, controlled leftmost derivations, regular languages, erasing rules

Key words in English

formal languages, pure grammar systems, controlled leftmost derivations, regular languages, erasing rules

Authors

MEDUNA, A.; VRÁBEL, L.; ZEMEK, P.

RIV year

2015

Released

18.08.2014

ISBN

0020-7160

Periodical

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS

Volume

91

Number

6

State

United Kingdom of Great Britain and Northern Ireland

Pages from

1156

Pages to

1169

Pages count

14

URL

http://www.tandfonline.com/doi/abs/10.1080/00207160.2013.829214

BibTex

@article{BUT111482,
  author="Alexandr {Meduna} and Lukáš {Vrábel} and Petr {Zemek}",
  title="Solutions To Four Open Problems Concerning Controlled Pure Grammar Systems",
  journal="INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS",
  year="2014",
  volume="91",
  number="6",
  pages="1156--1169",
  doi="10.1080/00207160.2013.829214",
  issn="0020-7160",
  url="http://www.tandfonline.com/doi/abs/10.1080/00207160.2013.829214"
}