Two-way automaton computations
Birget, Jean-Camille
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 24 (1990), p. 47-66 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1990__24_1_47_0,
     author = {Birget, Jean-Camille},
     title = {Two-way automaton computations},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {24},
     year = {1990},
     pages = {47-66},
     mrnumber = {1060466},
     zbl = {0701.68058},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1990__24_1_47_0}
}

Birget, Jean-Camille. Two-way automaton computations. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 24 (1990) pp. 47-66. http://gdmltest.u-ga.fr/item/ITA_1990__24_1_47_0/

1. J. Berstel, Transductions and Context-Free Languages, Teubner, Stuttgart, 1979. | MR 549481 | Zbl 0424.68040

2. J. C. Birget, Concatenation of Inputs in a Two-Way Automaton, Theoret. Comp. Sci., Vol. 63, 1989, pp. 141-156. | MR 984314 | Zbl 0664.68081

3. J. C. Birget, Machines and expansions of a semigroup, and applications, Ph. D. thesis, U. of California, Berkeley, May 1983.

4. J. C. Birget, Arbitrary Versus Regular Semigroups, J. Pure and Appl. Algebra, Vol. 34, 1984, pp. 56-115. | MR 766155 | Zbl 0547.20055

5. S. Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, 1974. | MR 530382 | Zbl 0317.94045

6. J. E. Hopcroft, and J. D. Ullman, Formal Languages and their Relation to Automata, Addison-Wesley, 1969, and | MR 237243 | Zbl 0196.01701

J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979. | MR 645539 | Zbl 0426.68001

7. J. P. Pécuchet, Automates boustrophedon, semigroupe de Birget et monoïde inversif libre, R.A.I.R.O. (Revue française d'automatique, d'informatique et de rech. opérat.), Informatique théorique, Vol. 19.1, 1985, pp. 71-100. | Numdam | MR 795773 | Zbl 0604.68094

8. J. C. Shepherdson, The Reduction of Two-Way to One-Way Automata, I.B.M. J. Res. and Dev., Vol. 3.2, 1959, pp. 198-200, and in E. F. MOORE (Ed.), Sequential Machines: Selected Papers, Addison-Wesley, 1964. | MR 103796 | Zbl 0158.25601

9. J. E. Pin and J. Sakarovitch, Some Operations and Transductions which Preserve Rationality, 6th G.I. ( = Gesellschaft für Informatik) Conference, Lecture Notes in Comp. Sci. (Springer Verlag) 145, pp. 277-288 and: Une application de la représentation matricielle des transductions, Theoretical Computer Science, 35, 1985, pp. 271-293. | MR 785156 | Zbl 0496.68052

10. J. C. Birget, Proof of a Conjecture of R. Kannan, Proc. 21st A.C.M. Symp. on Theory of Computing, 1989, pp. 445-453.