Detail publikace
Nonterminal Complexity of One-Sided Random Context Grammars
Originální název
Nonterminal Complexity of One-Sided Random Context Grammars
Anglický název
Nonterminal Complexity of One-Sided Random Context Grammars
Jazyk
en
Originální abstrakt
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.
Anglický abstrakt
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.
BibTex
@article{BUT91445,
author="Alexandr {Meduna} and Petr {Zemek}",
title="Nonterminal Complexity of One-Sided Random Context Grammars",
annote="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.",
address="NEUVEDEN",
chapter="91445",
doi="10.1007/s00236-012-0150-6",
edition="NEUVEDEN",
howpublished="print",
institution="NEUVEDEN",
number="2",
volume="49",
year="2012",
month="february",
pages="55--68",
publisher="NEUVEDEN",
type="journal article in Web of Science"
}