Publication Details

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

MEDUNA, A.; ZEMEK, P. One-Sided Random Context Grammars with a Limited Number of Right Random Context Rules. Theoretical Computer Science, 2014, vol. 516, no. 1, p. 127-132. ISSN: 0304-3975.

Czech title

Jednostranné gramatiky s nahodilým kontextem a s omezeným počtem pravě kontextových pravidel

Type

journal article

Language

English

Authors

Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Zemek Petr, Ing., Ph.D.

URL

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

Keywords

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

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.

Published

2014

Pages

127–132

Journal

Theoretical Computer Science, vol. 516, no. 1, ISSN 0304-3975

DOI

10.1016/j.tcs.2013.11.009

UT WoS

000330817700012

EID Scopus

2-s2.0-84890492849

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