|
| << 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 19 van 39 gevonden artikelen
| Titel: |
On Characterizing Recursively Enumerable Languages by Insertion Grammars |
| Auteur: |
Madhu Mutyam Kamala Krithivasan A. Siddhartha Reddy |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 64 (2005) nr. 1-4 pagina's 317-324 |
| Jaar: |
2005-06-27 |
| Inhoud: |
Insertion grammars have been introduced in [1] and their computational power has been studied in several places. In [7] it is proved that insertion grammars with weight at least 7 can characterize recursively enumerable languages (modulo a weak coding and an inverse morphism), and the question was formulated whether or not this result can be improved. In this paper, we come up with a positive answer to this question, by decreasing the weight of the insertion grammar used to 5. We also give a characterization of recursively enumerable languages in terms of right quotients of insertion languages. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 19 van 39 gevonden artikelen
| << vorige | volgende >> |