Journal article

MEDUNA Alexander, VRÁBEL Lukáš and ZEMEK Petr. Solutions To Four Open Problems Concerning Controlled Pure Grammar Systems. International Journal of Computer Mathematics. 2014, vol. 91, no. 6, pp. 1156-1169. ISSN 0020-7160. Available from: http://www.tandfonline.com/doi/abs/10.1080/00207160.2013.829214
Publication language:english
Original title:Solutions To Four Open Problems Concerning Controlled Pure Grammar Systems
Title (cs):Řešení čtyř otevřených problémů týkajících se řízených čistých gramatických systémů
Pages:1156-1169
Place:GB
Year:2014
URL:http://www.tandfonline.com/doi/abs/10.1080/00207160.2013.829214
Journal:International Journal of Computer Mathematics, Vol. 91, No. 6, GB
ISSN:0020-7160
Keywords
formal languages, pure grammar systems, controlled leftmost derivations, regular languages, erasing rules
Annotation
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{
   author = {Alexander Meduna and Luk{\'{a}}{\v{s}} Vr{\'{a}}bel and Petr
	Zemek},
   title = {Solutions To Four Open Problems Concerning Controlled Pure
	Grammar Systems},
   pages = {1156--1169},
   journal = {International Journal of Computer Mathematics},
   volume = {91},
   number = {6},
   year = {2014},
   ISSN = {0020-7160},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=10154}
}

Your IPv4 address: 54.224.197.86
Switch to IPv6 connection

DNSSEC [dnssec]