Találati lista | Tudóstér

001-es BibID:	BIBFORM039427
Első szerző:	Vaszil György (matematikus)
Cím:	On the Nonterminal Complexity of Tree Controlled Grammars / Vaszil György
Dátum:	2012
Megjegyzések:	A tree controlled grammar is a regulated rewriting device which can be given as a pair (G, R) where G is a context-free grammar and R is a regular set over the terminal and nonterminal alphabets of G . The language generated by the tree controlled grammar contains those words of L ( G ) which have a derivation tree where all the words obtained by reading the symbols labeling the nodes belonging to the different levels of the tree, from left to right, belong to the language R . The nonterminal complexity of tree controlled grammars can be given as the number of nonterminals of the context-free grammar G , and the number of nonterminals that a regular grammar needs to generate the control language R . Here we improve the currently known best upper bound on the nonterminal complexity of tree controlled grammars from seven to six, that is, we show that a context-free grammar with five nonterminals and a control language which can be generated by a grammar with one nonterminal is sufficient to generate any recursively enumerable language.
Tárgyszavak:	Természettudományok Matematika- és számítástudományok könyvfejezet
Megjelenés:	Languages Alive / (ed. by) Henning Bordihn, Martin Kutrib, Bianca Truthe. - p. 265-272. -
Internet cím:	Intézményi repozitóriumban (DEA) tárolt változat
Borító:
Saját polcon: