Publication 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

journal article in Web of Science

Language

en

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

RIV year

2014

Released

18.08.2014

Publisher

NEUVEDEN

Location

NEUVEDEN

ISBN

0020-7160

Periodical

International Journal of Computer Mathematics

Year of study

91

Number

6

State

GB

Pages from

1156

Pages to

1169

Pages count

14

URL

Documents

BibTex


@article{BUT111482,
  author="Alexandr {Meduna} and Lukáš {Vrábel} and Petr {Zemek}",
  title="Solutions To Four Open Problems Concerning Controlled Pure Grammar Systems",
  annote="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.",
  address="NEUVEDEN",
  chapter="111482",
  doi="10.1080/00207160.2013.829214",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  number="6",
  volume="91",
  year="2014",
  month="august",
  pages="1156--1169",
  publisher="NEUVEDEN",
  type="journal article in Web of Science"
}