Result Details

On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars

MEDUNA, A.; ZEMEK, P. On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars. Theoretical Computer Science, 2013, vol. 477, no. 1, p. 67-75. ISSN: 0304-3975.
Type
journal article
Language
English
Authors
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
Zemek Petr, Ing., Ph.D., DIFS (FIT)
Abstract

The present paper explains how to transform any regular-controlled (context-free) grammar with appearance checking G to a propagating regular-controlled (context-free) grammar with appearance checking G' whose language L(G') has sentences of the form wz, where w is in L(G) and z is a parse of w in G'. Consequently, for every recursively enumerable language K, there exists a propagating regular-controlled grammar with appearance checking G' with L(G') of the above form so that K results from L(G') by erasing all rules in L(G'). In addition, analogical results are established (a) in terms of these grammars without appearance checking and (b) in terms of these grammars that make only leftmost derivations. In the conclusion, we point out some consequences implied by the results achieved in this paper.

Keywords

formal languages, context-free grammars, regular-controlled derivations, generation of sentences with their parses

URL
Published
2013
Pages
67–75
Journal
Theoretical Computer Science, vol. 477, no. 1, ISSN 0304-3975
DOI
10.1016/j.tcs.2012.12.040
BibTeX 
@article{BUT103400,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars",
  journal="Theoretical Computer Science",
  year="2013",
  volume="477",
  number="1",
  pages="67--75",
  doi="10.1016/j.tcs.2012.12.040",
  issn="0304-3975",
  url="http://www.sciencedirect.com/science/article/pii/S0304397513000066"
}
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