Publication detail

A Formalization of Sequential, Parallel, and Continuous Rewriting

MEDUNA, A.

Original Title

A Formalization of Sequential, Parallel, and Continuous Rewriting

Type

journal article - other

Language

English

Original Abstract

A formalization of the sequential, parallel, and continuous rewriting based on a uniform underlying concept of selective substitution grammars is presented. Each of the rewriting modes is formalized through a universal derivation restriction characterizing the rewriting in question. It is shown that whichever of the three rewriting modes is formalized, the resulting grammars generate precisely the family of context sensitive languages. Moreover, when erasing productions are allowed, these grammars generate all recursively enumerable languages.

Keywords

sequential rewriting, parallel rewriting, continuous rewriting, selective substitution grammars, context sensitive languages, recursively enumerable languages

Authors

MEDUNA, A.

Released

1. 1. 1993

Publisher

unknown

Location

New York

ISBN

0020-7160

Periodical

International Journal of Computer Mathematics

Year of study

1993

Number

47

State

United Kingdom of Great Britain and Northern Ireland

Pages from

153

Pages to

161

Pages count

9

BibTex

@article{BUT191812,
  author="Alexandr {Meduna}",
  title="A Formalization of Sequential, Parallel, and Continuous Rewriting",
  journal="International Journal of Computer Mathematics",
  year="1993",
  volume="1993",
  number="47",
  pages="153--161",
  issn="0020-7160"
}