×

Binary equality sets are generated by two words. (English) Zbl 1010.68101

Summary: We show that the equality set Eq(\(g,h\)) of two non-periodic binary morphisms \(g,h:A*\to \sum *\) is generated by at most two words. If the rank of Eq(\(g,h\))={\(\alpha , \beta\)}* is two, then \(\alpha\) and \(\beta\) begin and end with different letters. This in particular implies that any binary language has a test set of cardinality at most two.

MSC:

68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Choffrut, C.; Karhumäki, J., Combinatorics on words, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, 1 (1997), Springer-Verlag: Springer-Verlag Berlin), 329-438 · Zbl 0866.68057
[2] Ehrenfeucht, A.; Karhumäki, J.; Rozenberg, G., The (generalized) Post correspondence problem with lists consisting of two words is decidable, Theoret. Comput. Sci., 21, 119-144 (1982) · Zbl 0493.68076
[3] Halava, V.; Harju, T., Some new results on Post correspondence problem and its modifications, Bull. Eur. Assoc. Theor. Comput. Sci., 73, 131-141 (2001) · Zbl 0989.68082
[4] Halava, V.; Harju, T.; Hirvensalo, M., Generalized Post correspondence problem for marked morphisms, Internat. J. Algebra Comput., 10, 757-772 (2000) · Zbl 0971.68124
[5] Harju, T.; Karhumäki, J., Morphisms, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, 1 (1997), Springer-Verlag: Springer-Verlag Berlin), 439-510 · Zbl 0866.68057
[6] Čulı́k, K.; Karhumäki, J., On the equality sets for homomorphisms on free monoids with two generators, RAIRO Theor. Inform., 14, 349-369 (1980) · Zbl 0454.20048
[7] Berstel, J.; Perrin, D.; Perrot, J. F.; Restivo, A., Sur le théorème du défaut, J. Algebra, 60, 169-180 (1979) · Zbl 0421.20027
[8] Ehrenfeucht, A.; Karhumäki, J.; Rozenberg, G., On binary equality sets and a solution to the test set conjecture in the binary case, J. Algebra, 85, 76-85 (1983) · Zbl 0523.68066
[9] Salomaa, A., Equality sets for homomorphisms of free monoids, Acta Cybernet., 4, 127-139 (1978) · Zbl 0407.68077
[10] Š. Holub, Equations in free monoids, PhD thesis, Charles University, Prague, 2000; Š. Holub, Equations in free monoids, PhD thesis, Charles University, Prague, 2000
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.