62
Views
1
CrossRef citations to date
0
Altmetric
Section A

Solutions to four open problems concerning controlled pure grammar systems

, &
Pages 1156-1169 | Received 29 Oct 2012, Accepted 23 Jul 2013, Published online: 24 Sep 2013
 

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.

2010 AMS Classifications:

Acknowledgements

This work was supported by the following grants: BUT FIT-S-11-2, MŠMT ED1.1.00/02.0070, TAČR TE01010415, and CEZ MŠMT MSM0021630528. The authors thank both anonymous referees for useful comments regarding the first version of this paper.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.