Result Details

Canonical Scattered Context Generators of Sentences with Their Parses

MEDUNA, A.; TECHET, J. Canonical Scattered Context Generators of Sentences with Their Parses. Theoretical Computer Science, 2007, vol. 2007, no. 389, p. 73-81. ISSN: 0304-3975.
Type
journal article
Language
English
Authors
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
Techet Jiří, Ing., Ph.D., DIFS (FIT)
Abstract

Scattered context generators derive their sentences followed by the corresponding parses. This paper discusses their two canonical versions, which make this derivation either in a leftmost or rightmost way. It demonstrates that for every recursively enumerable language, L, there exists a canonical scattered context generator whose language consists of L's sentences followed by their parses. In fact, this result is established based on the generators containing no more than six nonterminals.

Keywords

scattered context grammars, canonical derivations, parses, descriptional complexity

Published
2007
Pages
73–81
Journal
Theoretical Computer Science, vol. 2007, no. 389, ISSN 0304-3975
BibTeX 
@article{BUT45163,
  author="Alexandr {Meduna} and Jiří {Techet}",
  title="Canonical Scattered Context Generators of Sentences with Their Parses",
  journal="Theoretical Computer Science",
  year="2007",
  volume="2007",
  number="389",
  pages="73--81",
  issn="0304-3975"
}
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
Multi-Information Technologies, GACR, Standardní projekty, GA201/07/0005, start: 2007-01-01, end: 2009-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