DETERMINISTIC SEQUENTIAL FUNCTIONS

: HARJU T, KLEIJN HCM, LATTEUX M

Publisher: SPRINGER VERLAG

: 1992

Acta Informatica

ACTA INFORMATICA

: ACTA INFORM

: 29

: 6-7

: 545

: 554

: 10

: 0001-5903

DOI: https://doi.org/10.1007/BF01185560

The simple rational partial functions accepted by generalized sequential machines are shown to coincide with the compositions HH(P)-1H, where H(P) consists of the prefix codings. The rational functions accepted by generalized sequential machines are proved to coincide with the compositions HMH(P)-1 RH, where M is the family of endmarkers and R is the family of removals of endmarkers. (The compositions are read from left to right). We also show that MHH(P)-1H is the family of the subsequential functions.

Mathematics