On cancellation properties of languages which are supports of rational power series. (English) Zbl 0578.68061

We show two properties of the languages which are supports of noncommutative rational power series: 1. Each such language L possesses a finite test set; that is, there exists a finite language \(K\subset L\) such that whenever two morphisms into a free monoid coincide on K, then they coincide on L. This is a special case of the Ehrenfeucht conjecture, which was given meanwhile a complete positive (and simple) answer: see e.g. D. Perrin: ”On the solution of Ehrenfeucht’s conjecture” [Bull. Eur. Assoc. Theor. Comput. Sci. 2]. If two complementary languages are both supports, then they are regular.


68Q45 Formal languages and automata
16W60 Valuations, completions, formal power series and related constructions (associative rings and algebras)
20M35 Semigroups in automata theory, linguistics, etc.
Full Text: DOI


[1] Albert, J.; Culik, K.; Karhumäki, J., Test sets for context-free languages and systems of equations over a free monoid, Inform. and Control, 52, 172-186 (1982) · Zbl 0522.68064
[2] Boasson, L.; Restivo, A., Une caractérisation des langages algébriques bornés, RAIRO Inform. Théor., 11, 203-205 (1977) · Zbl 0371.68024
[3] Choffrut, C., Sur les tranductions reconnaissables, RAIRO Inform. Théo., 12, 203-218 (1978) · Zbl 0423.20053
[4] Culik, K.; Salomaa, A., Test sets and checking words for homomorphism equivalence, J. Comput. System Sci., 20, 379-395 (1980) · Zbl 0451.68046
[5] Ehrenfeucht, A.; Parikh, R.; Rozenberg, G., Pumping lemmas for regular sets, SIAM J. Comput., 10, 536-541 (1981) · Zbl 0461.68081
[6] Ehrenfeucht, A.; Karhumäki, J.; Rozenberg, G., On binary equality languages and a solution to the test set conjecture in the binary case, J. Algebra, 85, 76-85 (1983) · Zbl 0523.68066
[7] Eilenberg, S., (Automates, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York) · Zbl 0317.94045
[8] Jacob, G., Un théorème de factorisation des produits d’endomorphismes de \(K^n\), J. Algebra, 63, 389-412 (1979) · Zbl 0441.16002
[9] M. Karpinski (Ed.), New Scottish book of problems, in preparation.; M. Karpinski (Ed.), New Scottish book of problems, in preparation.
[10] Lech, C., A note on recurring series, Ark. Math., 2, 417-421 (1952) · Zbl 0051.27801
[11] Restivo, A., Mots sans répétitions et languages rationnels bornés, RAIRO Inform. Théor., 11, 197-202 (1977) · Zbl 0371.68023
[12] Reutenauer, C., An Ogden-like iteration lemma for rational power series, Acta Informa., 13, 189-197 (1980) · Zbl 0423.68033
[13] Reutenauer, C., Sur les éléments inversibles de l’algèbre de Hadamard des séries rationnelles, Bull. Soc. Math. France, 110, 225-232 (1982) · Zbl 0517.13010
[14] Salomaa, A., Formal power series in noncommuting variables, (18th Scand. Congr. Math., Proc., Aarhus 1980. 18th Scand. Congr. Math., Proc., Aarhus 1980, Prog. Math., 11 (1981)) · Zbl 0485.68076
[15] Salomaa, A.; Sorrrola, M., Automata-Theoretic Aspects of Formal Power Series (1978), Springer-Verlag: Springer-Verlag New York/Berlin · Zbl 0377.68039
[16] Schüdtzenberger, M. P., On the definition of a family of automata, Inform. and Control, 4, 245-270 (1961) · Zbl 0104.00702
[17] Sontag, E., On some questions of rationality and decidability, J. Comput. System Sci., 11, 375-381 (1975) · Zbl 0357.68064
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.