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...

Descripción completa

Detalles Bibliográficos
Autores principales: Löbel, Raphaela, Luttenberger, Michael, Seidl, Helmut
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Article
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

Ejemplares similares