A length bound for binary equality words
Commentationes Mathematicae Universitatis Carolinae (2011)
- Volume: 52, Issue: 1, page 1-20
- ISSN: 0010-2628
Access Full Article
top
Abstract
topHow to cite
topHadravová, Jana. "A length bound for binary equality words." Commentationes Mathematicae Universitatis Carolinae 52.1 (2011): 1-20. <http://eudml.org/doc/246151>.
@article{Hadravová2011,
abstract = {Let $w$ be an equality word of two binary non-periodic morphisms $g,h: \lbrace a,b\rbrace ^* \rightarrow \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$.},
author = {Hadravová, Jana},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {combinatorics on words; binary equality languages; morphism; equality words; equality language; combinatorics on words},
language = {eng},
number = {1},
pages = {1-20},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {A length bound for binary equality words},
url = {http://eudml.org/doc/246151},
volume = {52},
year = {2011},
}
TY - JOUR
AU - Hadravová, Jana
TI - A length bound for binary equality words
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2011
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 52
IS - 1
SP - 1
EP - 20
AB - Let $w$ be an equality word of two binary non-periodic morphisms $g,h: \lbrace a,b\rbrace ^* \rightarrow \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$.
LA - eng
KW - combinatorics on words; binary equality languages; morphism; equality words; equality language; combinatorics on words
UR - http://eudml.org/doc/246151
ER -
References
top- Culik K. II, 10.1145/322123.322136, J. Assoc. Comput. Mach. 26 (1979), no. 2, 345–350. Zbl0395.68076MR0528036DOI10.1145/322123.322136
- 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. MR0607436
- Ehrenfeucht A., Karhumäki J., Rozenberg G., 10.1016/0304-3975(89)90080-7, Theor. Comput. Sci. 21 (1982), 119–144. Zbl0493.68076MR0677104DOI10.1016/0304-3975(89)90080-7
- Ehrenfeucht A., Karhumäki J., Rozenberg G., 10.1016/0021-8693(83)90119-9, J. Algebra 85 (1983), 76–85. MR0723068DOI10.1016/0021-8693(83)90119-9
- Hadravová J., Holub Š., 10.1007/978-3-540-85780-8_31, Developments in Language Theory, Lecture Notes in Comput. Sci, 5257, Springer, Berlin, 2008, pp. 396–407. MR2490972DOI10.1007/978-3-540-85780-8_31
- Halava V., Harju T., Hirvensalo M., 10.1016/S0304-3975(01)00157-8, Theor. Comput. Sci. 276 (2002), no. 1–2, 183–204. Zbl1023.03038MR1896352DOI10.1016/S0304-3975(01)00157-8
- Halava V., Holub Š., Reduction tree of the binary generalized post correspondence problem, Internat. J. Found. Comput. Sci.(to appear). MR2772820
- Halava V., Holub Š., Binary (generalized) post correspondence problem is in P, Turku Centre for Computer Science, 785, 2006.
- Holub Š., Binary morphisms with stable suffix complexity, Internat. J. Found. Comput. Sci.(to appear). MR2788561
- Holub Š., 10.1016/S0021-8693(02)00534-3, J. Algebra 259 (2003), no. 1, 1–42. Zbl1010.68101MR1953706DOI10.1016/S0021-8693(02)00534-3
- Holub Š., 10.1007/3-540-45005-X_21, Developments in Language Theory, Lecture Notes in Comput. Sci., 2450, Springer, Berlin, 2003, pp. 245–257. Zbl1015.68089MR2177348DOI10.1007/3-540-45005-X_21
- 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.
- 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. MR0912705
- 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. MR2186471
- Lothaire M., Combinatorics on Words, Addison-Wesley, Reading, Mass., 1983. Zbl1133.68067MR0675953
- Post E.L., 10.1090/S0002-9904-1946-08555-9, Bull. Amer. Math. Soc. 52 (1946) 264–268. Zbl0063.06329MR0015343DOI10.1090/S0002-9904-1946-08555-9
- Rozenberg G., Salomaa A., Handbook of Formal Languages, Vol. 1: Word, Language, Grammar, Springer, New York, 1997. MR1469992
- Salomaa A., Equality sets for homomorphisms of free monoids, Acta Cybernetica 4 (1978), no. 1, 127–139. Zbl0407.68077MR0521458
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.