Detail publikace

Solutions To Four Open Problems Concerning Controlled Pure Grammar Systems

Originální název

Solutions To Four Open Problems Concerning Controlled Pure Grammar Systems

Anglický název

Solutions To Four Open Problems Concerning Controlled Pure Grammar Systems

Jazyk

en

Originální abstrakt

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.

Anglický abstrakt

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.

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