Result Details

Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof

MASOPUST, T.; TECHET, J. Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2008, vol. 10, no. 2, p. 39-46. ISSN: 1365-8050.
Type
journal article
Language
English
Authors
Masopust Tomáš, doc. RNDr., Ph.D., DIFS (FIT)
Techet Jiří, Ing., Ph.D., DIFS (FIT)
Abstract

In 1973, V. Virkkunen proved that propagating scattered context grammars which use leftmost derivations are as powerful as context-sensitive grammars. This paper brings a significantly simplified proof of this result.

Keywords

formal languages, propagating scattered context grammars, leftmost derivations, generative power

URL
Published
2008
Pages
39–46
Journal
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, vol. 10, no. 2, ISSN 1365-8050
UT WoS
000255071100001
BibTeX 
@article{BUT48169,
  author="Tomáš {Masopust} and Jiří {Techet}",
  title="Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof",
  journal="DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE",
  year="2008",
  volume="10",
  number="2",
  pages="39--46",
  issn="1462-7264",
  url="http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/issue/view/93"
}
Projects
Integrated approach to education of PhD students in the area of parallel and distributed systems, GACR, Doktorské granty, GD102/05/H050, start: 2005-01-01, end: 2008-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
Research groups
Formal Model Research Group (RG FM)
Departments
Department of Information Systems (DIFS)
Back to top