|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 4 van 5 gevonden artikelen
| Titel: |
Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals |
| Auteur: |
Masopust, Tomáš |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 99 (2010) nr. 4 pagina's 473-480 |
| Jaar: |
2010-07-07 |
| Inhoud: |
Scattered context grammars with three nonterminals are known to be computationally complete. So far, however, it was an open problem whether the number of parallel productions can be bounded along with three nonterminals. In this paper, we prove that every recursively enumerable language is generated by a scattered context grammar with three nonterminals and five parallel productions, each of which simultaneously rewrites no more than nine nonterminals. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 4 van 5 gevonden artikelen
| << vorige | volgende >> |