Publication result detail

A Formalization of Sequential, Parallel, and Continuous Rewriting

MEDUNA, A.

Original Title

A Formalization of Sequential, Parallel, and Continuous Rewriting

English Title

A Formalization of Sequential, Parallel, and Continuous Rewriting

Type

Peer-reviewed article not indexed in WoS or Scopus

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.

English 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

Key words in English

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

Authors

MEDUNA, A.

Released

01.01.1993

Publisher

unknown

Location

New York

Book

International Journal of Computer Mathematics

ISBN

0020-7160

Periodical

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS

Volume

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"
}