×
Birget, Jean-Camille

Two-way automaton computations. (English) Zbl 0701.68058

RAIRO, Inform. Théor. Appl. 24, No. 1, 47-66 (1990).
Summary: Computations of a two-way automaton on an input tape are studied using the algebraic notion of trace of a two-way computation (due to J. P. Pécuchet), and certain “reductions” of traces.

Cited in 1 Review
Cited in 8 Documents

MSC:

68Q45 Formal languages and automata

Keywords:

two-way automaton
Cite Review PDF
Full Text: DOI EuDML

References:

[1] 1. J. BERSTEL, Transductions and Context-Free Languages, Teubner, Stuttgart, 1979. Zbl0424.68040 MR549481 · Zbl 0424.68040
[2] 2. J. C. BIRGET, Concatenation of Inputs in a Two-Way Automaton, Theoret. Comp. Sci., Vol. 63, 1989, pp. 141-156. Zbl0664.68081 MR984314 · Zbl 0664.68081 · doi:10.1016/0304-3975(89)90075-3
[3] 3. J. C. BIRGET, Machines and expansions of a semigroup, and applications, Ph. D. thesis, U. of California, Berkeley, May 1983.
[4] 4. J. C. BIRGET, Arbitrary Versus Regular Semigroups, J. Pure and Appl. Algebra, Vol. 34, 1984, pp. 56-115. Zbl0547.20055 MR766155 · Zbl 0547.20055 · doi:10.1016/0022-4049(84)90056-2
[5] 5. S. EILENBERG, Automata, Languages and Machines, Vol. A, Academic Press, 1974. Zbl0317.94045 MR530382 · Zbl 0317.94045
[6] 6. J. E. HOPCROFT, and J. D. ULLMAN, Formal Languages and their Relation to Automata, Addison-Wesley, 1969, and Zbl0196.01701 MR237243 · Zbl 0196.01701
[7] J. E. HOPCROFT and J. D. ULLMAN, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979. Zbl0426.68001 MR645539 · Zbl 0426.68001
[8] 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. Zbl0604.68094 MR795773 · Zbl 0604.68094
[9] 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. Zbl0158.25601 MR103796 · Zbl 0158.25601
[10] 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. Zbl0496.68052 MR785156 · Zbl 0496.68052
[11] 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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.