On Tree Substitution Grammars

Tree substitution grammars are formal models that are used extensively in natural language processing. It is demonstrated that their expressive power is located strictly between the local tree grammars and the regular tree grammars. A decision procedure for the problem of determining whether a tree...

Descripción completa

Detalles Bibliográficos
Autores principales: Maletti, Andreas, Stier, Kevin
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7247875/
http://dx.doi.org/10.1007/978-3-030-48516-0_18
_version_ 1783538253976043520
author Maletti, Andreas
Stier, Kevin
author_facet Maletti, Andreas
Stier, Kevin
author_sort Maletti, Andreas
collection PubMed
description Tree substitution grammars are formal models that are used extensively in natural language processing. It is demonstrated that their expressive power is located strictly between the local tree grammars and the regular tree grammars. A decision procedure for the problem of determining whether a tree substitution grammar generates a local tree language is provided. Unfortunately, the class of tree substitution languages is neither closed under union, nor intersection, nor complements. Indeed unions of tree substitution languages even generate an infinite hierarchy. However, all finite and all co-finite tree languages are tree substitution languages.
format Online
Article
Text
id pubmed-7247875
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-72478752020-05-26 On Tree Substitution Grammars Maletti, Andreas Stier, Kevin Developments in Language Theory Article Tree substitution grammars are formal models that are used extensively in natural language processing. It is demonstrated that their expressive power is located strictly between the local tree grammars and the regular tree grammars. A decision procedure for the problem of determining whether a tree substitution grammar generates a local tree language is provided. Unfortunately, the class of tree substitution languages is neither closed under union, nor intersection, nor complements. Indeed unions of tree substitution languages even generate an infinite hierarchy. However, all finite and all co-finite tree languages are tree substitution languages. 2020-05-26 /pmc/articles/PMC7247875/ http://dx.doi.org/10.1007/978-3-030-48516-0_18 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
Maletti, Andreas
Stier, Kevin
On Tree Substitution Grammars
title On Tree Substitution Grammars
title_full On Tree Substitution Grammars
title_fullStr On Tree Substitution Grammars
title_full_unstemmed On Tree Substitution Grammars
title_short On Tree Substitution Grammars
title_sort on tree substitution grammars
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7247875/
http://dx.doi.org/10.1007/978-3-030-48516-0_18
work_keys_str_mv AT malettiandreas ontreesubstitutiongrammars
AT stierkevin ontreesubstitutiongrammars

Ejemplares similares