Cargando…
Context-Sensitive Fusion Grammars Are Universal
Context-sensitive fusion grammars are a special case of context-dependent fusion grammars where a rule has only a single positive context condition instead of finite sets of positive and negative context conditions. They generate hypergraph languages from start hypergraphs via successive application...
Autor principal: | |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
2020
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7206639/ http://dx.doi.org/10.1007/978-3-030-40608-0_19 |
_version_ | 1783530448994959360 |
---|---|
author | Lye, Aaron |
author_facet | Lye, Aaron |
author_sort | Lye, Aaron |
collection | PubMed |
description | Context-sensitive fusion grammars are a special case of context-dependent fusion grammars where a rule has only a single positive context condition instead of finite sets of positive and negative context conditions. They generate hypergraph languages from start hypergraphs via successive applications of context-sensitive fusion rules and multiplications of connected components, as well as a filtering mechanism to extract terminal hypergraphs from derived hypergraphs in a certain way. The application of a context-sensitive fusion rule consumes two complementarily labeled hyperedges and identifies corresponding attachment vertices provided that the context condition holds. In this paper, we show that the Post correspondence problem can be formulated very intuitively by such a grammar. Furthermore, we prove that these grammars can generate all recursively enumerable string languages (up to representation of strings as graphs) and are universal in this respect. |
format | Online Article Text |
id | pubmed-7206639 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2020 |
record_format | MEDLINE/PubMed |
spelling | pubmed-72066392020-05-08 Context-Sensitive Fusion Grammars Are Universal Lye, Aaron Language and Automata Theory and Applications Article Context-sensitive fusion grammars are a special case of context-dependent fusion grammars where a rule has only a single positive context condition instead of finite sets of positive and negative context conditions. They generate hypergraph languages from start hypergraphs via successive applications of context-sensitive fusion rules and multiplications of connected components, as well as a filtering mechanism to extract terminal hypergraphs from derived hypergraphs in a certain way. The application of a context-sensitive fusion rule consumes two complementarily labeled hyperedges and identifies corresponding attachment vertices provided that the context condition holds. In this paper, we show that the Post correspondence problem can be formulated very intuitively by such a grammar. Furthermore, we prove that these grammars can generate all recursively enumerable string languages (up to representation of strings as graphs) and are universal in this respect. 2020-01-07 /pmc/articles/PMC7206639/ http://dx.doi.org/10.1007/978-3-030-40608-0_19 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 Lye, Aaron Context-Sensitive Fusion Grammars Are Universal |
title | Context-Sensitive Fusion Grammars Are Universal |
title_full | Context-Sensitive Fusion Grammars Are Universal |
title_fullStr | Context-Sensitive Fusion Grammars Are Universal |
title_full_unstemmed | Context-Sensitive Fusion Grammars Are Universal |
title_short | Context-Sensitive Fusion Grammars Are Universal |
title_sort | context-sensitive fusion grammars are universal |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7206639/ http://dx.doi.org/10.1007/978-3-030-40608-0_19 |
work_keys_str_mv | AT lyeaaron contextsensitivefusiongrammarsareuniversal |