One-way Resynchronizability of Word Transducers

The origin semantics for transducers was proposed in 2014, and it led to various characterizations and decidability results that are in contrast with the classical semantics. In this paper we add a further decidability result for characterizing transducers that are close to one-way transducers in th...

Descripción completa

Detalles Bibliográficos
Autores principales: Bose, Sougata, Krishna, S. N., Muscholl, Anca, Puppis, Gabriele
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2021
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7984121/
http://dx.doi.org/10.1007/978-3-030-71995-1_7
_version_ 1783668009792962560
author Bose, Sougata
Krishna, S. N.
Muscholl, Anca
Puppis, Gabriele
author_facet Bose, Sougata
Krishna, S. N.
Muscholl, Anca
Puppis, Gabriele
author_sort Bose, Sougata
collection PubMed
description The origin semantics for transducers was proposed in 2014, and it led to various characterizations and decidability results that are in contrast with the classical semantics. In this paper we add a further decidability result for characterizing transducers that are close to one-way transducers in the origin semantics. We show that it is decidable whether a non-deterministic two-way word transducer can be resynchronized by a bounded, regular resynchronizer into an origin-equivalent one-way transducer. The result is in contrast with the usual semantics, where it is undecidable to know if a non-deterministic two-way transducer is equivalent to some one-way transducer.
format Online
Article
Text
id pubmed-7984121
institution National Center for Biotechnology Information
language English
publishDate 2021
record_format MEDLINE/PubMed
spelling pubmed-79841212021-03-23 One-way Resynchronizability of Word Transducers Bose, Sougata Krishna, S. N. Muscholl, Anca Puppis, Gabriele Foundations of Software Science and Computation Structures Article The origin semantics for transducers was proposed in 2014, and it led to various characterizations and decidability results that are in contrast with the classical semantics. In this paper we add a further decidability result for characterizing transducers that are close to one-way transducers in the origin semantics. We show that it is decidable whether a non-deterministic two-way word transducer can be resynchronized by a bounded, regular resynchronizer into an origin-equivalent one-way transducer. The result is in contrast with the usual semantics, where it is undecidable to know if a non-deterministic two-way transducer is equivalent to some one-way transducer. 2021-03-23 /pmc/articles/PMC7984121/ http://dx.doi.org/10.1007/978-3-030-71995-1_7 Text en © The Author(s) 2021 Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made. The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
spellingShingle Article
Bose, Sougata
Krishna, S. N.
Muscholl, Anca
Puppis, Gabriele
One-way Resynchronizability of Word Transducers
title One-way Resynchronizability of Word Transducers
title_full One-way Resynchronizability of Word Transducers
title_fullStr One-way Resynchronizability of Word Transducers
title_full_unstemmed One-way Resynchronizability of Word Transducers
title_short One-way Resynchronizability of Word Transducers
title_sort one-way resynchronizability of word transducers
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7984121/
http://dx.doi.org/10.1007/978-3-030-71995-1_7
work_keys_str_mv AT bosesougata onewayresynchronizabilityofwordtransducers
AT krishnasn onewayresynchronizabilityofwordtransducers
AT muschollanca onewayresynchronizabilityofwordtransducers
AT puppisgabriele onewayresynchronizabilityofwordtransducers

Ejemplares similares