Scattered context grammars generate any recursively enumerable language with two nonterminals

Autor:	György Vaszil, Erzsébet Csuhaj-Varjú
Rok vydání:	2010
Předmět:	Discrete mathematics Recursively enumerable set Context (language use) Computer Science Applications Theoretical Computer Science TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Recursively enumerable language Rule-based machine translation TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS Signal Processing Regulated rewriting Formal language Indexed grammar Maximal set Information Systems Mathematics
Zdroj:	Information Processing Letters. 110:902-907
ISSN:	0020-0190
Popis:	By showing that two nonterminals are sufficient, we present the optimal lower bound on the number of nonterminals of scattered context grammars being able to generate any recursively enumerable language.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::09c3be9ec57faebe695f28c14d94fc96 https://doi.org/10.1016/j.ipl.2010.07.008 Zobrazit plný text záznamu Full Text from ScienceDirect