Publication Details

Descriptional Complexity of Generalized Forbidding Grammars

MEDUNA Alexander and ŠVEC Martin. Descriptional Complexity of Generalized Forbidding Grammars. International Journal of Computer Mathematics, vol. 2003, no. 80, pp. 11-17. ISSN 0020-7160.

Czech title

Složitost popisu gramatik s rozptýleným kontextem

Type

journal article

Language

english

Authors

Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Švec Martin, Ing. (DIFS FIT BUT)

Keywords

Generalized forbidding grammars, recursively enumerable languages

Abstract

Generalized forbidding grammars are reduced.

Annotation

This paper discusses the descriptional complexity of generalized forbidding grammars. It proves that every recursively enumerable language is generated by a generalized forbidding grammar containing no more than thirteen forbidding productions and no more than fifteen nonterminals.

Published

2003

Pages

11-17

Journal

International Journal of Computer Mathematics, vol. 2003, no. 80, ISSN 0020-7160

Book

International Journal of Computer Mathematics

Publisher

Taylor & Francis Informa plc

Place

London, GB

BibTeX

@ARTICLE{FITPUB7034,
   author = "Alexander Meduna and Martin \v{S}vec",
   title = "Descriptional Complexity of Generalized Forbidding Grammars",
   pages = "11--17",
   booktitle = "International Journal of Computer Mathematics",
   journal = "International Journal of Computer Mathematics",
   volume = 2003,
   number = 80,
   year = 2003,
   location = "London, GB",
   publisher = "Taylor \& Francis Informa plc",
   ISSN = "0020-7160",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7034"
}