Abstract
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.