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: |