Publication detail

One-Sided Random Context Grammars with a Limited Number of Right Random Context Rules

MEDUNA, A. ZEMEK, P.

Original Title

One-Sided Random Context Grammars with a Limited Number of Right Random Context Rules

Type

journal article in Web of Science

Language

English

Original Abstract

This paper deals with regulated grammars. Specifically, it studies one-sided random context grammars. It demonstrates that any recursively enumerable language can be generated by these grammars with no more than two right random context rules.

Keywords

formal languages, one-sided random context grammars, right random context rules, reduction

Authors

MEDUNA, A.; ZEMEK, P.

RIV year

2014

Released

9. 1. 2014

ISBN

0304-3975

Periodical

Theoretical Computer Science

Year of study

516

Number

1

State

Kingdom of the Netherlands

Pages from

127

Pages to

132

Pages count

6

URL

BibTex

@article{BUT111481,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="One-Sided Random Context Grammars with a Limited Number of Right Random Context Rules",
  journal="Theoretical Computer Science",
  year="2014",
  volume="516",
  number="1",
  pages="127--132",
  doi="10.1016/j.tcs.2013.11.009",
  issn="0304-3975",
  url="http://www.sciencedirect.com/science/article/pii/S030439751300827X"
}