EUVIMEDEUVIMED entdecken
Crossref

On Szilard Languages of Labelled Insertion Grammars

Prithwineel Paul

Fundamenta Informaticae · 08.02.2020 · 172 (1) · 53-72

DOI: 10.3233/fi-2020-1892 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Fundamenta Informaticae, online erschienen am 08.02.2020. Verfasst von Prithwineel Paul. Die Arbeit wurde bisher 2-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this work we initiate the study of Szilard languages of labelled insertion grammars. It is well-known that there exist context-free languages which cannot be generated by any insertion grammar. We show that there exist some regular languages which cannot be Szilard language of any labelled insertion grammar. But any regular language can be given as a homomorphic image of Szilard language obtained by a labelled insertion grammar of weight 1. Also, any context-free language can be obtained as a homomorphic image of Szilard language of a labelled insertion grammar of weight 2. We show that even though insertion grammars of weight 1 can generate only context-free languages, there exists some context-sensitive language which can be obtained as Szilard language of a labelled insertion grammar of weight 1. At the end we show that any recursively enumerable language can be characterized by the homomorphic image of Szilard language obtained by a labelled insertion grammar of weight 5.

Zitieren

APA

Paul, P. (2020). On Szilard Languages of Labelled Insertion Grammars. Fundamenta Informaticae, 172(1), 53-72. https://doi.org/10.3233/fi-2020-1892

Vancouver

Paul P. On Szilard Languages of Labelled Insertion Grammars. Fundamenta Informaticae. 2020;172(1):53-72. doi:10.3233/fi-2020-1892

BibTeX
@article{Paul2020,
  author = {Paul, Prithwineel},
  title = {On Szilard Languages of Labelled Insertion Grammars},
  journal = {Fundamenta Informaticae},
  year = {2020},
  volume = {172},
  number = {1},
  pages = {53--72},
  doi = {10.3233/fi-2020-1892}
}
Kostenlos starten →