| Title:
|
A length bound for binary equality words (English) |
| Author:
|
Hadravová, Jana |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
52 |
| Issue:
|
1 |
| Year:
|
2011 |
| Pages:
|
1-20 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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$. (English) |
| Keyword:
|
combinatorics on words |
| Keyword:
|
binary equality languages |
| MSC:
|
68R15 |
| idZBL:
|
Zbl 1240.68162 |
| idMR:
|
MR2828362 |
| . |
| Date available:
|
2011-03-08T17:33:00Z |
| Last updated:
|
2013-09-22 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/141422 |
| . |
| Reference:
|
[1] Culik K. II: A purely homomorphic characterization of recursively enumerable sets.J. Assoc. Comput. Mach. 26 (1979), no. 2, 345–350. Zbl 0395.68076, MR 0528036, 10.1145/322123.322136 |
| Reference:
|
[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 |
| Reference:
|
[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. Zbl 0493.68076, MR 0677104, 10.1016/0304-3975(89)90080-7 |
| Reference:
|
[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. MR 0723068, 10.1016/0021-8693(83)90119-9 |
| Reference:
|
[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. MR 2490972, 10.1007/978-3-540-85780-8_31 |
| Reference:
|
[6] Halava V., Harju T., Hirvensalo M.: Binary (generalized) post correspondence problem.Theor. Comput. Sci. 276 (2002), no. 1–2, 183–204. Zbl 1023.03038, MR 1896352, 10.1016/S0304-3975(01)00157-8 |
| Reference:
|
[7] Halava V., Holub Š.: Reduction tree of the binary generalized post correspondence problem.Internat. J. Found. Comput. Sci.(to appear). MR 2772820 |
| Reference:
|
[8] Halava V., Holub Š.: Binary (generalized) post correspondence problem is in P.Turku Centre for Computer Science, 785, 2006. |
| Reference:
|
[9] Holub Š.: Binary morphisms with stable suffix complexity.Internat. J. Found. Comput. Sci.(to appear). MR 2788561 |
| Reference:
|
[10] Holub Š.: Binary equality sets are generated by two words.J. Algebra 259 (2003), no. 1, 1–42. Zbl 1010.68101, MR 1953706, 10.1016/S0021-8693(02)00534-3 |
| Reference:
|
[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. Zbl 1015.68089, MR 2177348, 10.1007/3-540-45005-X_21 |
| Reference:
|
[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. |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[15] Lothaire M.: Combinatorics on Words.Addison-Wesley, Reading, Mass., 1983. Zbl 1133.68067, MR 0675953 |
| Reference:
|
[16] Post E.L.: A variant of a recursively unsolvable problem.Bull. Amer. Math. Soc. 52 (1946) 264–268. Zbl 0063.06329, MR 0015343, 10.1090/S0002-9904-1946-08555-9 |
| Reference:
|
[17] Rozenberg G., Salomaa A.: Handbook of Formal Languages, Vol. 1: Word, Language, Grammar.Springer, New York, 1997. MR 1469992 |
| Reference:
|
[18] Salomaa A.: Equality sets for homomorphisms of free monoids.Acta Cybernetica 4 (1978), no. 1, 127–139. Zbl 0407.68077, MR 0521458 |
| . |
