Detail výsledku

Maximal and Minimal Scattered Context Rewriting

MEDUNA, A.; TECHET, J. Maximal and Minimal Scattered Context Rewriting. FCT 2007 Proceedings. Lecture Notes in Computer Science. Budapest: Springer Verlag, 2007. no. 4639, p. 412-423. ISSN: 0302-9743.
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Techet Jiří, Ing., Ph.D., UIFS (FIT)
Abstrakt

As their name suggest, during a maximal derivation step, a scattered context grammar G rewrites the maximal number of nonterminals while during a minimal derivation step, G rewrites the minimal number of nonterminals. This paper demonstrates that if the propagating scattered context grammars derive their sentences by making either of these two derivation steps, then they characterize the family of context sensitive languages.

Klíčová slova

formal languages, scattered context grammars, generative power

Rok
2007
Strany
412–423
Časopis
Lecture Notes in Computer Science, roč. 2007, č. 4639, ISSN 0302-9743
Sborník
FCT 2007 Proceedings
Konference
16th International Symposium on Fundamentals of Computation Theory
Vydavatel
Springer Verlag
Místo
Budapest
BibTeX 
@inproceedings{BUT28796,
  author="Alexandr {Meduna} and Jiří {Techet}",
  title="Maximal and Minimal Scattered Context Rewriting",
  booktitle="FCT 2007 Proceedings",
  year="2007",
  journal="Lecture Notes in Computer Science",
  volume="2007",
  number="4639",
  pages="412--423",
  publisher="Springer Verlag",
  address="Budapest",
  issn="0302-9743"
}
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