Publication Details
Descriptional Complexity of Generalized Forbidding Grammars
MEDUNA, A.; ŠVEC, M. Descriptional Complexity of Generalized Forbidding Grammars. International Journal of Computer Mathematics, 2003, vol. 2003, no. 80, p. 11-17. ISSN: 0020-7160.
Czech title
Složitost popisu gramatik s rozptýleným kontextem
Type
journal article
Language
English
Authors
Meduna Alexandr, prof. RNDr., CSc.
(DIFS)
Švec Martin, Ing., Ph.D.
Švec Martin, Ing., Ph.D.
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
BibTeX
@article{BUT41990,
author="Alexandr {Meduna} and Martin {Švec}",
title="Descriptional Complexity of Generalized Forbidding Grammars",
journal="International Journal of Computer Mathematics",
year="2003",
volume="2003",
number="80",
pages="11--17",
issn="0020-7160"
}