Detail výsledku

Solutions To Four Open Problems Concerning Controlled Pure Grammar Systems

MEDUNA, A.; VRÁBEL, L.; ZEMEK, P. Solutions To Four Open Problems Concerning Controlled Pure Grammar Systems. INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2014, vol. 91, no. 6, p. 1156-1169. ISSN: 0020-7160.
Typ
článek v časopise
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Vrábel Lukáš, Ing.
Zemek Petr, Ing., Ph.D., UIFS (FIT)
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

URL
Rok
2014
Strany
1156–1169
Časopis
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, roč. 91, č. 6, ISSN 0020-7160
DOI
10.1080/00207160.2013.829214
UT WoS
000340826000002
EID Scopus
2-s2.0-84906788547
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"
}
Projekty
Centrum excelence IT4Innovations, MŠMT, Operační program Výzkum a vývoj pro inovace, ED1.1.00/02.0070, zahájení: 2011-01-01, ukončení: 2015-12-31, ukončen
Centrum kompetence ve zpracování vizuálních informací (V3C - Visual Computing Competence Center), TAČR, Centra kompetence, TE01020415, zahájení: 2012-05-01, ukončení: 2019-12-31, ukončen
Pokročilé rozpoznávání a prezentace multimediálních dat, VUT, Vnitřní projekty VUT, FIT-S-11-2, zahájení: 2011-01-01, ukončení: 2013-12-31, ukončen
Výzkum informačních technologií z hlediska bezpečnosti, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, zahájení: 2007-01-01, ukončení: 2013-12-31, řešení
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru