×

Concatenation of inputs in a two-way automaton. (English) Zbl 0664.68081

To every input string of a two-way automaton one associates a quadruple of partial functions (or relations) between the states. This quadruple describes the behavior of the automaton on that input, and can also be used to formulate acceptance, or notions like the crossing sequence. Formulas are given that show how two such quadruples are combined (“multiplied”) as their corresponding input strings are concatenated.

MSC:

68Q45 Formal languages and automata
68Q70 Algebraic theory of languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berstel, J., Transductions and Context-free Languages (1979), Teubner: Teubner Stuttgart · Zbl 0424.68040
[2] J.C. Birget, Two-way automaton computations, RAIRO Inform. Théor.; J.C. Birget, Two-way automaton computations, RAIRO Inform. Théor. · Zbl 0701.68058
[3] Eilenberg, S., Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press London · Zbl 0317.94045
[4] Hopcroft, J. E.; Ullman, J. D., Formal Languages and their Relation to Automata, Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley New York: Addison-Wesley: Addison-Wesley: Addison-Wesley New York: Addison-Wesley New York · Zbl 0196.01701
[5] Lallement, G., Semigroups and Combinatorial Applications (1979), Wiley: Wiley London · Zbl 0421.20025
[6] Pécuchet, J. P., Automates boustrophedon, semigroupe de Birget et monoïde inversif libre, RAIRO Inform. Théor., 19, 1, 71-100 (1985) · Zbl 0604.68094
[7] Rabin, M. O., Two-way automata, (Proc. Summer Institute of Symbolic Logic (1957), Cornell University), 366-369 · Zbl 0148.01003
[8] Rabin, M. O.; Scott, D., Finite automata and their decision problems, IBM J. Res. Dev.. (Moore, E. F., Sequential Machines: Selected Papers (1964), Addison-Wesley: Addison-Wesley New York), 3, 2, 114-125 (1959) · Zbl 0158.25404
[9] Shepherdson, J. C., The reduction of two-way automata to one-way automata, IBM J. Res. Dev.. (Moore, E. F., Sequential Machines: Selected Papers (1964), Addison-Wesley: Addison-Wesley New York), 3, 2, 198-200 (1959) · Zbl 0158.25601
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.