Geodesic
Input- or output-unary sweeping transducers are weaker than their 2-way counterparts
Guillon, Bruno1 
1 LIAFA, Université Paris-Diderot, Paris 7, Paris, France
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 7th Non-Classical Models of Automata and Applications (NCMA-2015) , Tome 50 (2016) no. 4, pp. 275-294

Voir la notice de l'article provenant de la source Numdam

In a previous paper we showed that two-way (nondeterministic) transducers with unary input and output alphabets have the same recognition power as the sweeping ones. We show that this no longer holds when one of the alphabets has cardinality at least 2.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2016028
Classification : 68Q70
Keywords: Unary alphabets, Hadamard relations, two-way, sweeping transducers

Guillon, Bruno 1

1 LIAFA, Université Paris-Diderot, Paris 7, Paris, France 
@article{ITA_2016__50_4_275_0,
     author = {Guillon, Bruno},
     title = {Input- or output-unary sweeping transducers are weaker than their 2-way counterparts},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {275--294},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {4},
     year = {2016},
     doi = {10.1051/ita/2016028},
     mrnumber = {3614546},
     zbl = {1362.68140},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2016028/}
}
TY  - JOUR
AU  - Guillon, Bruno
TI  - Input- or output-unary sweeping transducers are weaker than their 2-way counterparts
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2016
SP  - 275
EP  - 294
VL  - 50
IS  - 4
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2016028/
DO  - 10.1051/ita/2016028
LA  - en
ID  - ITA_2016__50_4_275_0
ER  - 
%0 Journal Article
%A Guillon, Bruno
%T Input- or output-unary sweeping transducers are weaker than their 2-way counterparts
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2016
%P 275-294
%V 50
%N 4
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2016028/
%R 10.1051/ita/2016028
%G en
%F ITA_2016__50_4_275_0
Guillon, Bruno. Input- or output-unary sweeping transducers are weaker than their 2-way counterparts. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 7th Non-Classical Models of Automata and Applications (NCMA-2015) , Tome 50 (2016) no. 4, pp. 275-294. doi: 10.1051/ita/2016028

Cité par Sources :