Detail publikačního výsledku

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

English Title

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

Type

WoS Article

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.

English 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

Key words in English

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

Authors

MEDUNA, A.; ZEMEK, P.

RIV year

2015

Released

09.01.2014

ISBN

0304-3975

Periodical

Theoretical Computer Science

Volume

516

Number

1

State

Kingdom of the Netherlands

Pages from

127

Pages to

132

Pages count

6

URL

http://www.sciencedirect.com/science/article/pii/S030439751300827X

Full text in the Digital Library

http://hdl.handle.net/

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"
}