Language classes generated by tree controlled grammars with bounded nonterminal complexity
A tree controlled grammar is specified as a pair (G, G′) where G is a context-free grammar and G′ is a regular grammar. Its language consists of all terminal words with a derivation in G such that all levels of the corresponding derivation tree – except the last level – belong to L(G′). We define th...
محفوظ في:
| المؤلفون الرئيسيون: | , , , |
|---|---|
| التنسيق: | مقال |
| اللغة: | English |
| منشور في: |
Elsevier
2012
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | http://irep.iium.edu.my/27237/1/Language_classes_generated_by_tree_controlled_grammars_with_bounded_nonterminal_complexity.pdf http://irep.iium.edu.my/27237/ http://www.sciencedirect.com/science/article/pii/S030439751200357X |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| id |
my.iium.irep.27237 |
|---|---|
| record_format |
dspace |
| spelling |
my.iium.irep.272372013-04-15T04:32:29Z http://irep.iium.edu.my/27237/ Language classes generated by tree controlled grammars with bounded nonterminal complexity Turaev, Sherzod Dassow, Juergen Manea, Florin Selamat, Mohd Hasan QA Mathematics QA75 Electronic computers. Computer science A tree controlled grammar is specified as a pair (G, G′) where G is a context-free grammar and G′ is a regular grammar. Its language consists of all terminal words with a derivation in G such that all levels of the corresponding derivation tree – except the last level – belong to L(G′). We define the nonterminal complexity Var(H) of H = (G, G′) as the sum of the numbers of nonterminals of G and G′. In Turaev et al. (2011) [23] it is shown that tree controlled grammars H with Var(H) ≤ 9 are sufficient to generate all recursively enumerable languages. In this paper, we improve the bound to seven. Moreover, we show that all linear and regular simple matrix languages can be generated by tree controlled grammarswith a nonterminal complexity bounded by three, and we prove that this bound is optimal for the mentioned language families. Furthermore, we show that any context-free language can be generated by a tree controlled grammar (G, G′) where the number of nonterminals of G and G′ is at most four. Elsevier 2012-08 Article REM application/pdf en http://irep.iium.edu.my/27237/1/Language_classes_generated_by_tree_controlled_grammars_with_bounded_nonterminal_complexity.pdf Turaev, Sherzod and Dassow, Juergen and Manea, Florin and Selamat, Mohd Hasan (2012) Language classes generated by tree controlled grammars with bounded nonterminal complexity. Theoretical Computer Science, 449 (2012). pp. 134-144. ISSN 0304-3975 http://www.sciencedirect.com/science/article/pii/S030439751200357X 10.1016/j.tcs.2012.04.013 |
| institution |
Universiti Islam Antarabangsa Malaysia |
| building |
IIUM Library |
| collection |
Institutional Repository |
| continent |
Asia |
| country |
Malaysia |
| content_provider |
International Islamic University Malaysia |
| content_source |
IIUM Repository (IREP) |
| url_provider |
http://irep.iium.edu.my/ |
| language |
English |
| topic |
QA Mathematics QA75 Electronic computers. Computer science |
| spellingShingle |
QA Mathematics QA75 Electronic computers. Computer science Turaev, Sherzod Dassow, Juergen Manea, Florin Selamat, Mohd Hasan Language classes generated by tree controlled grammars with bounded nonterminal complexity |
| description |
A tree controlled grammar is specified as a pair (G, G′) where G is a context-free grammar and G′ is a regular grammar. Its language consists of all terminal words with a derivation in G such that all levels of the corresponding derivation tree – except the last level – belong to L(G′). We define the nonterminal complexity Var(H) of H = (G, G′) as the sum of the numbers of nonterminals of G and G′. In Turaev et al. (2011) [23] it is shown that tree controlled grammars H with Var(H) ≤ 9 are sufficient to generate all recursively enumerable languages. In this paper, we improve the bound to seven. Moreover, we show that all linear and regular simple matrix languages can be generated by tree controlled grammarswith a nonterminal complexity bounded by three, and we prove that this bound is optimal for the mentioned language families. Furthermore, we show that any context-free language can be generated by a tree controlled grammar (G, G′) where the number of nonterminals of G and G′
is at most four. |
| format |
Article |
| author |
Turaev, Sherzod Dassow, Juergen Manea, Florin Selamat, Mohd Hasan |
| author_facet |
Turaev, Sherzod Dassow, Juergen Manea, Florin Selamat, Mohd Hasan |
| author_sort |
Turaev, Sherzod |
| title |
Language classes generated by tree controlled grammars with bounded nonterminal complexity |
| title_short |
Language classes generated by tree controlled grammars with bounded nonterminal complexity |
| title_full |
Language classes generated by tree controlled grammars with bounded nonterminal complexity |
| title_fullStr |
Language classes generated by tree controlled grammars with bounded nonterminal complexity |
| title_full_unstemmed |
Language classes generated by tree controlled grammars with bounded nonterminal complexity |
| title_sort |
language classes generated by tree controlled grammars with bounded nonterminal complexity |
| publisher |
Elsevier |
| publishDate |
2012 |
| url |
http://irep.iium.edu.my/27237/1/Language_classes_generated_by_tree_controlled_grammars_with_bounded_nonterminal_complexity.pdf http://irep.iium.edu.my/27237/ http://www.sciencedirect.com/science/article/pii/S030439751200357X |
| _version_ |
1643609300837335040 |
| score |
13.251813 |