Result Details

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.
Type
conference paper
Language
English
Authors
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
Techet Jiří, Ing., Ph.D., DIFS (FIT)
Abstract

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.

Keywords

formal languages, scattered context grammars, generative power

Published
2007
Pages
412–423
Journal
Lecture Notes in Computer Science, vol. 2007, no. 4639, ISSN 0302-9743
Proceedings
FCT 2007 Proceedings
Conference
16th International Symposium on Fundamentals of Computation Theory
Publisher
Springer Verlag
Place
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"
}
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