Insertion-Deletion Systems with Substitutions I

With good biological motivation, we add substitutions as a further type of operations to (in particular, context-free) insertion-deletion systems. This way, we obtain new characterizations of and normal forms for context-sensitive and recursively enumerable languages.

Detalles Bibliográficos
Autores principales: Vu, Martin, Fernau, Henning
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7309486/
http://dx.doi.org/10.1007/978-3-030-51466-2_33
_version_ 1783549216819249152
author Vu, Martin
Fernau, Henning
author_facet Vu, Martin
Fernau, Henning
author_sort Vu, Martin
collection PubMed
description With good biological motivation, we add substitutions as a further type of operations to (in particular, context-free) insertion-deletion systems. This way, we obtain new characterizations of and normal forms for context-sensitive and recursively enumerable languages.
format Online
Article
Text
id pubmed-7309486
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-73094862020-06-23 Insertion-Deletion Systems with Substitutions I Vu, Martin Fernau, Henning Beyond the Horizon of Computability Article With good biological motivation, we add substitutions as a further type of operations to (in particular, context-free) insertion-deletion systems. This way, we obtain new characterizations of and normal forms for context-sensitive and recursively enumerable languages. 2020-06-24 /pmc/articles/PMC7309486/ http://dx.doi.org/10.1007/978-3-030-51466-2_33 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Vu, Martin
Fernau, Henning
Insertion-Deletion Systems with Substitutions I
title Insertion-Deletion Systems with Substitutions I
title_full Insertion-Deletion Systems with Substitutions I
title_fullStr Insertion-Deletion Systems with Substitutions I
title_full_unstemmed Insertion-Deletion Systems with Substitutions I
title_short Insertion-Deletion Systems with Substitutions I
title_sort insertion-deletion systems with substitutions i
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7309486/
http://dx.doi.org/10.1007/978-3-030-51466-2_33
work_keys_str_mv AT vumartin insertiondeletionsystemswithsubstitutionsi
AT fernauhenning insertiondeletionsystemswithsubstitutionsi

Ejemplares similares