Result Details
On the Nonterminal Complexity of Left Random Context E0L Grammars
ZEMEK, P. On the Nonterminal Complexity of Left Random Context E0L Grammars. Proceedings of the 17th Conference STUDENT EEICT 2011 Volume 3. Brno: Faculty of Information Technology BUT, 2011. p. 510-514. ISBN: 978-80-214-4273-3.
Type
conference paper
Language
English
Authors
Zemek Petr, Ing., Ph.D., FIT (FIT), DIFS (FIT)
Abstract
The present paper studies the nonterminal complexity of left random context E0L grammars. More specifically, it proves that every recursively enumerable language can be generated by a left random context E0L grammar with nine nonterminals. In the conclusion, some open problems related to the achieved result are stated.
Keywords
Formal languages, left random context E0L grammars, nonterminal complexity
URL
Published
2011
Pages
510–514
Proceedings
Proceedings of the 17th Conference STUDENT EEICT 2011 Volume 3
Conference
Student EEICT 2011
ISBN
978-80-214-4273-3
Publisher
Faculty of Information Technology BUT
Place
Brno
BibTeX
@inproceedings{BUT91268,
author="Petr {Zemek}",
title="On the Nonterminal Complexity of Left Random Context E0L Grammars",
booktitle="Proceedings of the 17th Conference STUDENT EEICT 2011 Volume 3",
year="2011",
pages="510--514",
publisher="Faculty of Information Technology BUT",
address="Brno",
isbn="978-80-214-4273-3",
url="http://www.feec.vutbr.cz/EEICT/2011/sbornik/03-Doktorske%20projekty/08-Informacni%20systemy/11-xzemek02.pdf"
}
Projects
Security-Oriented Research in Information Technology, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, start: 2007-01-01, end: 2013-12-31, running
Research groups
Formal Model Research Group (RG FM)
Departments