Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
combinatorics on words; binary equality languages
combinatorics on words; binary equality languages
Summary:
Let $w$ be an equality word of two binary non-periodic morphisms $g,h: \{a,b\}^* \to \Delta^*$ with unique overflows. It is known that if $w$ contains at least 25 occurrences of each of the letters $a$ and $b$, then it has to have one of the following special forms: up to the exchange of the letters $a$ and $b$ either $w=(ab)^ia$, or $w=a^ib^j$ with $\operatorname{gcd} (i,j)=1$. We will generalize the result, justify this bound and prove that it can be lowered to nine occurrences of each of the letters $a$ and $b$.
References:
[1] Culik K. II: A purely homomorphic characterization of recursively enumerable sets. J. Assoc. Comput. Mach. 26 (1979), no. 2, 345–350. DOI 10.1145/322123.322136 | MR 0528036 | Zbl 0395.68076
[2] Culik K. II, Karhumäki J.: On the equality sets for homomorphisms on free monoids with two generators. RAIRO Inform. Théor. 14 (1980), no. 4, 349–369. MR 0607436
[3] Ehrenfeucht A., Karhumäki J., Rozenberg G.: The (generalized) post correspondence problem with lists consisting of two words is decidable. Theor. Comput. Sci. 21 (1982), 119–144. DOI 10.1016/0304-3975(89)90080-7 | MR 0677104 | Zbl 0493.68076
[4] 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 (1983), 76–85. DOI 10.1016/0021-8693(83)90119-9 | MR 0723068
[5] Hadravová J., Holub Š.: Large simple binary equality words. Developments in Language Theory, Lecture Notes in Comput. Sci, 5257, Springer, Berlin, 2008, pp. 396–407. DOI 10.1007/978-3-540-85780-8_31 | MR 2490972
[6] Halava V., Harju T., Hirvensalo M.: Binary (generalized) post correspondence problem. Theor. Comput. Sci. 276 (2002), no. 1–2, 183–204. DOI 10.1016/S0304-3975(01)00157-8 | MR 1896352 | Zbl 1023.03038
[7] Halava V., Holub Š.: Reduction tree of the binary generalized post correspondence problem. Internat. J. Found. Comput. Sci.(to appear). MR 2772820
[8] Halava V., Holub Š.: Binary (generalized) post correspondence problem is in P. Turku Centre for Computer Science, 785, 2006.
[9] Holub Š.: Binary morphisms with stable suffix complexity. Internat. J. Found. Comput. Sci.(to appear). MR 2788561
[10] Holub Š.: Binary equality sets are generated by two words. J. Algebra 259 (2003), no. 1, 1–42. DOI 10.1016/S0021-8693(02)00534-3 | MR 1953706 | Zbl 1010.68101
[11] Holub Š.: A unique structure of two-generated binary equality sets. Developments in Language Theory, Lecture Notes in Comput. Sci., 2450, Springer, Berlin, 2003, pp. 245–257. DOI 10.1007/3-540-45005-X_21 | MR 2177348 | Zbl 1015.68089
[12] Holub Š.: Binary equality languages for periodic morphisms. Algebraic Systems, Formal Languages and Conventional and Unconventional Computation Theory, RIMS Kokyuroku, vol. 1366, Kyoto University, Kyoto, 2004.
[13] Karhumäki J.: On recent trends in formal language theory. 14th International Colloquium on Automata, languages and programming (Karlsruhe, 1987), Springer, Berlin, 1987, pp. 136–162. MR 0912705
[14] Karhumäki J.: Open problems and exercises on words and languages (invited talk). in Proceedings of Conference on Algebraic Information, Aristotle University of Thessaloniki, 2005, pp. 295–305. MR 2186471
[15] Lothaire M.: Combinatorics on Words. Addison-Wesley, Reading, Mass., 1983. MR 0675953 | Zbl 1133.68067
[16] Post E.L.: A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc. 52 (1946) 264–268. DOI 10.1090/S0002-9904-1946-08555-9 | MR 0015343 | Zbl 0063.06329
[17] Rozenberg G., Salomaa A.: Handbook of Formal Languages, Vol. 1: Word, Language, Grammar. Springer, New York, 1997. MR 1469992
[18] Salomaa A.: Equality sets for homomorphisms of free monoids. Acta Cybernetica 4 (1978), no. 1, 127–139. MR 0521458 | Zbl 0407.68077
Search
Partner of
