Deterministic sequential functions
Tóm tắt
The simple rational partial functions accepted by generalized sequential machines are shown to coincide with the compositions ℋ ℋ
−1
ℋ, where ℋ
P
consists of the prefix codings. The rational functions accepted by generalized sequential machines are proved to coincide with the compositions ℋ ℳℋ
−1
ℛ ℋ , where ℳ is the family of endmarkers and ℛ is the family of removals of endmarkers. (The compositions are read from left to right). We also show that ℳ ℋℋ
−1
ℋ is the family of the subsequential functions.
Tài liệu tham khảo
Berstel, J.: Transductions and context-free languages. Stuttgart: B. G. Teubner 1979
Choffrut, C., Culik, K. II: Properties of finite and pushdown transducers. SIAM J. Comput.12, 300–315 (1983)
Eilenberg, S.: Automata, languages, and machines, Vol. A. New York: Academic Press 1974
Harju, T., Kleijn, H.C.M., Latteux, M.: Compositional representation of rational functions. RAIRO Theoret. Inf.26, 243–255 (1992)
Karhumäki, J., Linna, M.: A note on morphic characterization of languages. Discrete Appl. Math.5, 243–246 (1983)
Latteux, M., Leguy, J.: On the composition of morphisms and inverse morphisms (Lect. Notes Comput. Sci., vol. 154, pp. 420–432) Berlin Heidelberg New York: Springer 1983
Latteux, M., Turakainen, P.: A new normal form for the compositions of morphisms and inverse morphisms. Math. Syst. Theory20, 261–271 (1987)
Turakainen, P.: A homomorphic characterization of principal semi-AFLs without using intersection with regular sets. Inf. Sci.27 141–149 (1982)
Turakainen, P.: A machine-oriented approach to compositions of morphisms and inverse morphisms. EATCS Bull.20, 162–166 (1983)