Synchronized rational relations of finite and infinite words. (English) Zbl 0783.68065

Rational relations on finite and infinite words are considered. The emphasis is on the synchronized (letter-to-letter) rational relations and the rational relations that are computed by automata with bounded delay. The authors make use of the resynchronization lemma of Eilenberg and Schützenberger. This result is generalized for infinite words. For the finite words it is shown that the synchronized rational relations are deterministic rational relations. Moreover, it is shown that it is undecidable whether a rational relation is synchronized or not. For infinite words it is proved that the family of deterministic synchronized rational relations is the intersection of the families of synchronized rational relations and deterministic rational relations.
Reviewer: T.J.Harju (Turku)


68Q45 Formal languages and automata
68Q70 Algebraic theory of languages and automata
68R15 Combinatorics on words
Full Text: DOI


[1] D. Berend and Ch. Frougny, Computability by finite automata and Pisot bases, to appear. · Zbl 0819.11005
[2] Berstel, J., Transductions and context-free languages, (1979), Teubner Stuttgart · Zbl 0424.68040
[3] Boasson, L., Cônes rationnels et familles agréables de langages — application au langage à compteur, ()
[4] Büchi, J.R.; Büchi, J.R., On a decision method in restricted second order arithmetic, (), 425-435, reprinted in · Zbl 0147.25103
[5] Dauchet, M.; Tison, S., The theory of ground rewrite systems is decidable, Proc. 5th IEEE symp. LICS, 242-248, (1990)
[6] Eilenberg, S., Automata, languages and machines, vol.A, (1974), Academic Press New York
[7] Elgot, C.C.; Mezei, J.E., On relations defined by generalized finite automata, IBM J. res. develop., 9, 47-68, (1965) · Zbl 0135.00704
[8] Epstein, D.; Cannon, J.; Holt, D.; Levy, S.; Paterson, M.; Thurston, W., Word processing in groups, (1992), Jones and Bartlett Publishers Boston · Zbl 0764.20017
[9] Fischer, P.C.; Rosenberg, A.L., Multitape one-way nonwriting automata, J. comput. system. sci., 2, 88-101, (1968) · Zbl 0159.01504
[10] Frougny, Ch., Systèmes de numération linéaires et automates finis, ()
[11] Frougny, Ch., Representations of numbers and finite automata, Math. systems theory, 25, 37-60, (1992) · Zbl 0776.11005
[12] Frougny, Ch.; Sakarovitch, J.; Frougny, Ch.; Sakarovitch, J., Rational relations with bounded delay, (), 145-159 · Zbl 0881.68068
[13] Gire, F.; Nivat, M., Relations rationnelles infinitaires, Calcolo, 21, 91-125, (1984) · Zbl 0552.68064
[14] Harju, T.; Karhumäki, J., The equivalence problem of multitape finite automata, Theoret. comput. sci., 78, 347-355, (1991) · Zbl 0727.68063
[15] Johnson, J.H., Rational equivalence relations, Theoret. comput. sci., 47, 39-60, (1986) · Zbl 0619.68051
[16] Landweber, L.H., Decision problems for ω-automata, Math. systems theory, 3, 376-384, (1969) · Zbl 0182.02402
[17] Latteux, M.; Timmerman, E., Rational ω-transductions, (), 263-277 · Zbl 0732.68068
[18] Leguy, J., Transductions rationnelles décroissantes, RAIRO inform. théor. appl., 15, 141-148, (1981) · Zbl 0456.68097
[19] Perrin, D.; Pin, J.E., Mots infinis, LITP report 92-17, (1992)
[20] Rabin, M.O.; Scott, D.; Moore, E., Finite automata and their decision problems, IBM J. res. develop, Sequential machines: selected papers, 3, 125-144, (1965), Addison-Wesley Reading, MA, reprinted in
[21] Schützenberger, M.P., Une variante des fonctions séquentielles, Theoret. comput. sci., 4, 47-57, (1977) · Zbl 0366.68043
[22] Stallings, J.R., Topology of finite graphs, Invent. math., 71, 551-565, (1983) · Zbl 0521.20013
[23] Thomas, W., Automata and quantifier hierarchies, (), 104-119
[24] Thomas, W., Infinite trees and automata definable relations over ω-words, (), 407-415
[25] Thomas, W., Automata on infinite objects, (), 133-191 · Zbl 0900.68316
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.