Detail výsledku

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.
Typ
článek v časopise
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Techet Jiří, Ing., Ph.D., FIT (FIT), UIFS (FIT)
Abstrakt

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.

Klíčová slova

scattered context grammars, canonical derivations, parses, descriptional complexity

Rok
2007
Strany
73–81
Časopis
Theoretical Computer Science, roč. 2007, č. 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"
}
Projekty
Integrovaný přístup k výchově studentů DSP v oblasti paralelních a distribuovaných systémů, GAČR, Doktorské granty, GD102/05/H050, zahájení: 2005-01-01, ukončení: 2008-12-31, ukončen
Multiinformační technologie, GAČR, Standardní projekty, GA201/07/0005, zahájení: 2007-01-01, ukončení: 2009-12-31, ukončen
Výzkum informačních technologií z hlediska bezpečnosti, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, zahájení: 2007-01-01, ukončení: 2013-12-31, řešení
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru