Detail publikace

Nonterminal Complexity of One-Sided Random Context Grammars

MEDUNA, A. ZEMEK, P.

Originální název

Nonterminal Complexity of One-Sided Random Context Grammars

Typ

článek v časopise ve Web of Science, Jimp

Jazyk

angličtina

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.

Klíčová slova

Formal languages, nonterminal complexity, one-sided random context grammars, random context nonterminals

Autoři

MEDUNA, A.; ZEMEK, P.

Rok RIV

2012

Vydáno

1. 2. 2012

ISSN

0001-5903

Periodikum

Acta Informatica

Ročník

49

Číslo

2

Stát

Spolková republika Německo

Strany od

55

Strany do

68

Strany počet

14

URL

http://www.springerlink.com/content/5822041380786746/

BibTex

@article{BUT91445,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="Nonterminal Complexity of One-Sided Random Context Grammars",
  journal="Acta Informatica",
  year="2012",
  volume="49",
  number="2",
  pages="55--68",
  doi="10.1007/s00236-012-0150-6",
  issn="0001-5903",
  url="http://www.springerlink.com/content/5822041380786746/"
}