Cargando…
Equivalence of Linear Tree Transducers with Output in the Free Group
We show that equivalence of deterministic linear tree transducers can be decided in polynomial time when their outputs are interpreted over the free group. Due to the cancellation properties offered by the free group, the required constructions are not only more general, but also simpler than the co...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
2020
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7247876/ http://dx.doi.org/10.1007/978-3-030-48516-0_16 |
_version_ | 1783538254199390208 |
---|---|
author | Löbel, Raphaela Luttenberger, Michael Seidl, Helmut |
author_facet | Löbel, Raphaela Luttenberger, Michael Seidl, Helmut |
author_sort | Löbel, Raphaela |
collection | PubMed |
description | We show that equivalence of deterministic linear tree transducers can be decided in polynomial time when their outputs are interpreted over the free group. Due to the cancellation properties offered by the free group, the required constructions are not only more general, but also simpler than the corresponding constructions for proving equivalence of deterministic linear tree-to-word transducers. |
format | Online Article Text |
id | pubmed-7247876 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2020 |
record_format | MEDLINE/PubMed |
spelling | pubmed-72478762020-05-26 Equivalence of Linear Tree Transducers with Output in the Free Group Löbel, Raphaela Luttenberger, Michael Seidl, Helmut Developments in Language Theory Article We show that equivalence of deterministic linear tree transducers can be decided in polynomial time when their outputs are interpreted over the free group. Due to the cancellation properties offered by the free group, the required constructions are not only more general, but also simpler than the corresponding constructions for proving equivalence of deterministic linear tree-to-word transducers. 2020-05-26 /pmc/articles/PMC7247876/ http://dx.doi.org/10.1007/978-3-030-48516-0_16 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 Löbel, Raphaela Luttenberger, Michael Seidl, Helmut Equivalence of Linear Tree Transducers with Output in the Free Group |
title | Equivalence of Linear Tree Transducers with Output in the Free Group |
title_full | Equivalence of Linear Tree Transducers with Output in the Free Group |
title_fullStr | Equivalence of Linear Tree Transducers with Output in the Free Group |
title_full_unstemmed | Equivalence of Linear Tree Transducers with Output in the Free Group |
title_short | Equivalence of Linear Tree Transducers with Output in the Free Group |
title_sort | equivalence of linear tree transducers with output in the free group |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7247876/ http://dx.doi.org/10.1007/978-3-030-48516-0_16 |
work_keys_str_mv | AT lobelraphaela equivalenceoflineartreetransducerswithoutputinthefreegroup AT luttenbergermichael equivalenceoflineartreetransducerswithoutputinthefreegroup AT seidlhelmut equivalenceoflineartreetransducerswithoutputinthefreegroup |