Nonterminal Complexity of One-Sided Random Context Grammars
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F12%3APU98153" target="_blank" >RIV/00216305:26230/12:PU98153 - isvavai.cz</a>
Result on the web
<a href="http://www.springerlink.com/content/5822041380786746/" target="_blank" >http://www.springerlink.com/content/5822041380786746/</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00236-012-0150-6" target="_blank" >10.1007/s00236-012-0150-6</a>
Alternative languages
Result language
angličtina
Original language name
Nonterminal Complexity of One-Sided Random Context Grammars
Original language description
In the present paper, we study the nonterminal complexity of one-sided random context grammars. More specifically, we prove that every recursively enumerable language can be generated by a one-sided random context grammar with no more than ten nonterminals. An analogical result holds for thirteen nonterminals in terms of these grammars with the set of left random context rules coinciding with the set of right random context rules. Furthermore, we introduce the notion of a right random context nonterminal, defined as a nonterminal that appears on the left-hand side of a right random context rule. We demonstrate how to convert any one-sided random context grammar G to an equivalent one-sided random context grammar H with two right random context nonterminals. An analogical conversion is given in terms of (1) propagating one-sided random context grammars and (2) left random context nonterminals. In the conclusion, two open problems are stated.
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/ED1.1.00%2F02.0070" target="_blank" >ED1.1.00/02.0070: IT4Innovations Centre of Excellence</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Acta Informatica
ISSN
0001-5903
e-ISSN
—
Volume of the periodical
49
Issue of the periodical within the volume
2
Country of publishing house
DE - GERMANY
Number of pages
14
Pages from-to
55-68
UT code for WoS article
000301374500001
EID of the result in the Scopus database
—