Untwisting two-way transducers in elementary time
International audience Functional transductions realized by two-way transducers (equivalently, by streaming transducers and by MSO transductions) are the natural and standard notion of "regular" mappings from words to words. It was shown recently (LICS'13) that it is decidable if such...
Published in: | 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) |
---|---|
Main Authors: | , , , |
Other Authors: | , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2017
|
Subjects: | |
Online Access: | https://hal.science/hal-01864614 https://hal.science/hal-01864614/document https://hal.science/hal-01864614/file/final_lics17.pdf https://doi.org/10.1109/LICS.2017.8005138 |
id |
ftanrparis:oai:HAL:hal-01864614v1 |
---|---|
record_format |
openpolar |
spelling |
ftanrparis:oai:HAL:hal-01864614v1 2023-06-11T04:13:07+02:00 Untwisting two-way transducers in elementary time Baschenis, Félix Gauwin, Olivier Muscholl, Anca Puppis, Gabriele Laboratoire Bordelais de Recherche en Informatique (LaBRI) Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS) ANR-13-JS02-0010,EXSTREAM,Extensions du traitement par flux(2013) ANR-16-CE40-0007,DELTA,DÉfis pour la Logique, les Transducteurs et les Automates(2016) Reykjavik, Iceland 2017-06-20 https://hal.science/hal-01864614 https://hal.science/hal-01864614/document https://hal.science/hal-01864614/file/final_lics17.pdf https://doi.org/10.1109/LICS.2017.8005138 en eng HAL CCSD IEEE info:eu-repo/semantics/altIdentifier/doi/10.1109/LICS.2017.8005138 hal-01864614 https://hal.science/hal-01864614 https://hal.science/hal-01864614/document https://hal.science/hal-01864614/file/final_lics17.pdf doi:10.1109/LICS.2017.8005138 info:eu-repo/semantics/OpenAccess 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'17) https://hal.science/hal-01864614 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'17), Jun 2017, Reykjavik, Iceland. pp.1-12, ⟨10.1109/LICS.2017.8005138⟩ two-way transducers automata [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] info:eu-repo/semantics/conferenceObject Conference papers 2017 ftanrparis https://doi.org/10.1109/LICS.2017.8005138 2023-05-28T23:08:58Z International audience Functional transductions realized by two-way transducers (equivalently, by streaming transducers and by MSO transductions) are the natural and standard notion of "regular" mappings from words to words. It was shown recently (LICS'13) that it is decidable if such a transduction can be implemented by some one-way transducer, but the given algorithm has non-elementary complexity. We provide an algorithm of different flavor solving the above question, that has double exponential space complexity. We further apply our technique to decide whether the transduction realized by a two-way transducer can be implemented by a sweeping transducer, with either known or unknown number of passes. Conference Object Iceland Portail HAL-ANR (Agence Nationale de la Recherche) 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 1 12 |
institution |
Open Polar |
collection |
Portail HAL-ANR (Agence Nationale de la Recherche) |
op_collection_id |
ftanrparis |
language |
English |
topic |
two-way transducers automata [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] |
spellingShingle |
two-way transducers automata [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] Baschenis, Félix Gauwin, Olivier Muscholl, Anca Puppis, Gabriele Untwisting two-way transducers in elementary time |
topic_facet |
two-way transducers automata [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] |
description |
International audience Functional transductions realized by two-way transducers (equivalently, by streaming transducers and by MSO transductions) are the natural and standard notion of "regular" mappings from words to words. It was shown recently (LICS'13) that it is decidable if such a transduction can be implemented by some one-way transducer, but the given algorithm has non-elementary complexity. We provide an algorithm of different flavor solving the above question, that has double exponential space complexity. We further apply our technique to decide whether the transduction realized by a two-way transducer can be implemented by a sweeping transducer, with either known or unknown number of passes. |
author2 |
Laboratoire Bordelais de Recherche en Informatique (LaBRI) Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS) ANR-13-JS02-0010,EXSTREAM,Extensions du traitement par flux(2013) ANR-16-CE40-0007,DELTA,DÉfis pour la Logique, les Transducteurs et les Automates(2016) |
format |
Conference Object |
author |
Baschenis, Félix Gauwin, Olivier Muscholl, Anca Puppis, Gabriele |
author_facet |
Baschenis, Félix Gauwin, Olivier Muscholl, Anca Puppis, Gabriele |
author_sort |
Baschenis, Félix |
title |
Untwisting two-way transducers in elementary time |
title_short |
Untwisting two-way transducers in elementary time |
title_full |
Untwisting two-way transducers in elementary time |
title_fullStr |
Untwisting two-way transducers in elementary time |
title_full_unstemmed |
Untwisting two-way transducers in elementary time |
title_sort |
untwisting two-way transducers in elementary time |
publisher |
HAL CCSD |
publishDate |
2017 |
url |
https://hal.science/hal-01864614 https://hal.science/hal-01864614/document https://hal.science/hal-01864614/file/final_lics17.pdf https://doi.org/10.1109/LICS.2017.8005138 |
op_coverage |
Reykjavik, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'17) https://hal.science/hal-01864614 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'17), Jun 2017, Reykjavik, Iceland. pp.1-12, ⟨10.1109/LICS.2017.8005138⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.1109/LICS.2017.8005138 hal-01864614 https://hal.science/hal-01864614 https://hal.science/hal-01864614/document https://hal.science/hal-01864614/file/final_lics17.pdf doi:10.1109/LICS.2017.8005138 |
op_rights |
info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.1109/LICS.2017.8005138 |
container_title |
2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) |
container_start_page |
1 |
op_container_end_page |
12 |
_version_ |
1768389756456009728 |