Result Details
An Improvement of the Descriptional Complexity of Grammars Regulated by Context Conditions
MASOPUST, T. An Improvement of the Descriptional Complexity of Grammars Regulated by Context Conditions. Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006). Mikulov: Faculty of Information Technology BUT, 2006. p. 105-112. ISBN: 80-214-3287-X.
Type
conference paper
Language
English
Authors
Masopust Tomáš, doc. RNDr., Ph.D., DIFS (FIT)
Abstract
This paper improves some well-known results concerning thedescriptional complexity of grammars regulated by context conditions.Specifically, it proves that every recursively enumerable language isgenerated by a generalized forbidding grammar of degree two with nomore than eight conditional productions and ten nonterminals, or by asimple semi-conditional grammar of degree (2,1) with no more than nineconditional productions and ten nonterminals.
Keywords
descriptional complexity, generalized forbidding grammar, simple semi-conditional grammar
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
ISBN
80-214-3287-X
Publisher
Faculty of Information Technology BUT
Place
Mikulov
BibTeX
@inproceedings{BUT22301,
author="Tomáš {Masopust}",
title="An Improvement of the Descriptional Complexity of Grammars Regulated by Context Conditions",
booktitle="Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006)",
year="2006",
pages="105--112",
publisher="Faculty of Information Technology BUT",
address="Mikulov",
isbn="80-214-3287-X"
}
Projects
Integrated approach to education of PhD students in the area of parallel and distributed systems, GACR, Doktorské granty, GD102/05/H050, start: 2005-01-01, end: 2008-12-31, completed
Research groups
Formal Model Research Group (RG FM)
Departments