Result 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.
Type
journal article
Language
English
Authors
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
Zemek Petr, Ing., Ph.D., DIFS (FIT)
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

URL
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"
}
Projects
Advanced recognition and presentation of multimedia data, BUT, Vnitřní projekty VUT, FIT-S-11-2, start: 2011-01-01, end: 2013-12-31, completed
Centrum excelence IT4Innovations, MŠMT, Operační program Výzkum a vývoj pro inovace, ED1.1.00/02.0070, start: 2011-01-01, end: 2015-12-31, completed
Security-Oriented Research in Information Technology, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, start: 2007-01-01, end: 2013-12-31, running
V3C - Visual Computing Competence Center, TAČR, Centra kompetence, TE01020415, start: 2012-05-01, end: 2019-12-31, completed
Research groups
Formal Model Research Group (RG FM)
Departments
Department of Information Systems (DIFS)
Back to top