Publication Details

Descriptional Complexity of Scattered Rewriting and Multirewriting: An Overview

MEDUNA Alexander. Descriptional Complexity of Scattered Rewriting and Multirewriting: An Overview. Journal of Automata, Languages and Combinatorics, vol. 2002, no. 7, pp. 571-577. ISSN 1430-189X.
Czech title
Popisná složitost roztroušeného přepisování a multipřepisování
Type
journal article
Language
english
Authors
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Keywords

grammars, scattered rewriting, multirewriting, descriptional complexity

Abstract

Partially parallel grammars are reduced.

Annotation

During a derivation step, partially parallel grammars rewrite some symbols of the sentential form while leaving the others unrewritten. The present paper discusses grammars that perform two types of parallelism - scattered rewriting and multirewriting. It gives an overview of the main results concerning their descriptional complexity with respect to the number of nonterminals or productions. In the conclusion, some open problems are pointed out.

Published
2002
Pages
571-577
Journal
Journal of Automata, Languages and Combinatorics, vol. 2002, no. 7, ISSN 1430-189X
Book
Journal of Automata, Languages and Combinatorics
Publisher
Otto-von-Guericke-University of Magdeburg
Place
Magdeburg, DE
BibTeX 
@ARTICLE{FITPUB7097,
   author = "Alexander Meduna",
   title = "Descriptional Complexity of Scattered Rewriting and Multirewriting: An Overview",
   pages = "571--577",
   booktitle = "Journal of Automata, Languages and Combinatorics",
   journal = "Journal of Automata, Languages and Combinatorics",
   volume = 2002,
   number = 7,
   year = 2002,
   location = "Magdeburg, DE",
   publisher = "Otto-von-Guericke-University of Magdeburg",
   ISSN = "1430-189X",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7097"
}
Back to top