no. 4
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, Tome 50 (2016) no. 4, pp. 275-294.

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
Mots clés : 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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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, Tome 50 (2016) no. 4, pp. 275-294. doi : 10.1051/ita/2016028. http://www.numdam.org/articles/10.1051/ita/2016028/

J. Alfonsín, The Diophantine Frobenius Problem. Oxford Lecture Series in Mathematics and Its Applications. OUP, Oxford (2005). | MR | Zbl

M. Anselmo, Two-way automata with multiplicity. In Automata, Languages and Programming. Vol. 443 of Lect. Notes Comput. Sci. Springer-Verlag, Berlin/Heidelberg (1990) 88–102. | MR | Zbl

F. Baschenis, O. Gauwin, A. Muscholl and G. Puppis, One-way definability of sweeping transducer. In 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS (2015) 16-18, 2015, Bangalore, India (2015) 178–191. | MR

J. Berstel, Transductions and context-free languages. Teubner (1979). | MR | Zbl

V. Carnino and S. Lombardy,Tropical Two-Way Automata. In vol. 8705, Theoretical Computer Science, Berlin, Heidelberg, Springer Berlin Heidelberg (2014) 195–206. | MR

C. Choffrut, Sequences of words defined by two-way transducers. Theoret. Comput. Sci. 658 (2017) 85–96. | DOI | MR | Zbl

C. Choffrut and B. Guillon, An Algebraic Characterization of Unary Two-Way Transducers. Lect. Notes Comput. Sci. (2014) 196–207. | MR

R. de Souza, Uniformisation of Two-Way Transducers. In vol. 7810 Language and Automata Theory and Applications, Lect. Notes Compt. Sci. Springer Berlin Heidelberg (2013) 547–558. | MR

S. Eilenberg, Automata, Languages and Machines, vol. A. Academic Press (1974). | MR

S. Eilenberg and M.-P. Schützenberger, Rational sets in commutative monoids. J. Algebra13 (1969) 173–191. | MR | Zbl

J. Engelfriet and H.J. Hoogeboom, MSO definable string transductions and two-way finite-state transducers. ACM Trans. Comput. Logic 2 (2001) 216–254. | DOI | MR | Zbl

E. Filiot, O. Gauwin, P.-A. Reynier and F.Servais, From Two-Way to One-Way Finite State Transducers. CoRR abs/1301.5197 (2013). | MR

S. Ginsburg and H.G. Rice, Two Families of Languages Related to ALGOL. J. ACM 9 (1962) 350–371. | DOI | MR | Zbl

E. Landau, Über die Maximalordnung der Permutationen gegebenen Grades. Arch. der Math. u. Phys. 5 (1903) 92–103. | JFM

S. Lombardy,Weighted two-way automata. In Seventh Workshop on Non-Classical Models of Automata and Applications – NCMA 2015, Porto, Portugal, August 31 – September 1, (2015). Proceedings (2015) 37–47.

M. Rabin and D. Scott,Finite automata and their decision problems. IBM J. Res. Develop. 3(1959) 114–125. | MR | Zbl

J. Sakarovitch, Elements of Automata Theory. Cambridge University Press (2009). | MR | Zbl

J.C. Shepherdson, The reduction of two-way automata to one-way automata. IBM J. Res. Develop. 3 (1959) 198–200. | DOI | MR | Zbl

Cité par Sources :