Publication Details

An Improvement of the Descriptional Complexity of Grammars Regulated by Context Conditions

MASOPUST Tomáš. An Improvement of the Descriptional Complexity of Grammars Regulated by Context Conditions. In: Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006). Mikulov: Faculty of Information Technology BUT, 2006, pp. 105-112. ISBN 80-214-3287-X.
Czech title
Vylepšení popisné složitosti gramatik regulovaných kontextovými podmínkami
Type
conference paper
Language
english
Authors
Masopust Tomáš, RNDr., Ph.D. (DIFS FIT BUT)
Keywords

descriptional complexity, generalized forbidding grammar, simple semi-conditional grammar

Abstract

This paper improves some well-known results concerning the descriptional complexity of grammars regulated by context conditions. Specifically, it proves that every recursively enumerable language is generated by a generalized forbidding grammar of degree two with no more than eight conditional productions and ten nonterminals, or by a simple semi-conditional grammar of degree (2,1) with no more than nine conditional productions and ten nonterminals.

Published
2006
Pages
105-112
Proceedings
Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006)
Conference
2nd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science -- MEMICS'06, Mikulov, CZ
ISBN
80-214-3287-X
Publisher
Faculty of Information Technology BUT
Place
Mikulov, CZ
BibTeX 
@INPROCEEDINGS{FITPUB8194,
   author = "Tom\'{a}\v{s} Masopust",
   title = "An Improvement of the Descriptional Complexity of Grammars Regulated by Context Conditions",
   pages = "105--112",
   booktitle = "Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006)",
   year = 2006,
   location = "Mikulov, CZ",
   publisher = "Faculty of Information Technology BUT",
   ISBN = "80-214-3287-X",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8194"
}
Back to top