Publication Details

Descriptional Complexity of Scattered Rewriting and Multirewriting: An Overview

MEDUNA, A. Descriptional Complexity of Scattered Rewriting and Multirewriting: An Overview. Journal of Automata, Languages and Combinatorics, 2002, vol. 2002, no. 7, p. 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 Alexandr, prof. RNDr., CSc. (DIFS)

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

BibTeX

@article{BUT45760,
  author="Alexandr {Meduna}",
  title="Descriptional Complexity of Scattered Rewriting and Multirewriting: An Overview",
  journal="Journal of Automata, Languages and Combinatorics",
  year="2002",
  volume="2002",
  number="7",
  pages="571--577",
  issn="1430-189X"
}