Detail publikačního výsledku

Solutions To Four Open Problems Concerning Controlled Pure Grammar Systems

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

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

Druh

Článek WoS

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.

Klíčová slova

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

Klíčová slova v angličtině

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

Autoři

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

Rok RIV

2015

Vydáno

18.08.2014

ISSN

0020-7160

Periodikum

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS

Svazek

91

Číslo

6

Stát

Spojené království Velké Británie a Severního Irska

Strany od

1156

Strany do

1169

Strany počet

14

URL

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

Plný text v Digitální knihovně

http://hdl.handle.net/

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