×

A construction on finite automata that has remained hidden. (English) Zbl 0913.68137

Summary: We show how a construction on matrix representations of two tape automata proposed by Schützenberger to prove that rational functions are unambiguous can be given a central rôle in the theory of relations and functions realized by finite automata, in such a way that the other basic results such as the “cross-section theorem”, its dual the theorem of rational uniformisation, or the decomposition theorem of rational functions into sequential functions, appear as direct and formal consequences of it.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arnold, A.; Latteux, M., A new proof of two theorems about rational transductions, Theoret. Comput. Sci., 8, 261-263 (1979) · Zbl 0401.68057
[2] Berstel, J., Transductions and Context-Free Languages (1979), Teubner: Teubner Stuttgart · Zbl 0424.68040
[3] Eilenberg, S., (Automata, Languages and Machines, vol. A (1974), Academic Press: Academic Press New York) · Zbl 0317.94045
[4] Elgot, C. C.; Mezei, J. E., On relations defined by generalized finite automata, IBM J. Res. Dev., 9, 47-68 (1965) · Zbl 0135.00704
[5] Frougny, Ch., Fibonacci representations and finite automata, IEEE Trans. Inform. Theory, 37, 393-399 (1991) · Zbl 0716.68067
[6] Frougny, Ch.; Sakarovitch, J., Synchronized rational relations of finite and infinite words, Theoret. Comput. Sci., 108, 45-82 (1993) · Zbl 0783.68065
[7] Ginsburg, S., The Mathematical Theory of Context-Free Languages (1966), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0184.28401
[8] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[9] Kobayashi, K., Classification of formal languages by functional binary transductions, Inform. and Control, 15, 95-109 (1969) · Zbl 0193.32501
[10] Perrin, D., Finite Automata, (van Leeuwen, J., Handbook of Theoretical Computer Science (1990), Elsevier: Elsevier Amsterdam), 1-53 · Zbl 0900.68312
[11] Schützenberger, M. P., A remark on finite transducers, Inform. and Control, 4, 381-388 (1961) · Zbl 0119.13901
[12] Schützenberger, M. P., Certain elementary families of automata, (Proc. Symp. on Mathematical Theory of Automata, Polytechnic Institute of Brooklyn (1962)), 139-153 · Zbl 0221.94080
[13] Schützenberger, M. P., On a theorem of R. Jungen, (Proc. Amer. Math. Soc., 13 (1962)), 885-890 · Zbl 0107.03102
[14] Schiitzenberger, M. P., Sur les relations rationnelles entre monoïdes libres, Theoret. Comput. Sci., 3, 243-259 (1976) · Zbl 0358.68129
[15] Schützenberger, M. P., Une variante des fonctions séquentielles, Theoret. Comput. Sci., 4, 47-57 (1977) · Zbl 0366.68043
[16] Stallings, J. R., Topology of finite graphs, Invent. Math., 71, 551-565 (1983) · Zbl 0521.20013
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.