Abstract
In the literature, many bijections between (labeled) Motzkin paths and various other combinatorial objects are studied. We consider abelian (un)bordered words and show the connection with irreducible symmetric Motzkin paths and paths in ℤ not returning to the origin. This study can be extended to abelian unbordered words over an arbitrary alphabet and we derive expressions to compute the number of these words. In particular, over a 3-letter alphabet, the connection with paths in the triangular lattice is made. Finally, we study the lengths of the abelian unbordered factors occurring in the Thue–Morse word.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barnabei, M., Bonetti, F., Silimbani, M.: Restricted involutions and Motzkin paths. Adv. in Appl. Math. 47, 102–115 (2011)
Bruyère, V., Hansel, G., Michaux, C., Villemaire, R.: Logic and p-recognizable sets of integers. Bull. Belg. Math. Soc. 1, 191–238 (1994)
Charlier, E., Rampersad, N., Shallit, J.: Enumeration and decidable properties of automatic sequences. Int. J. Found. Comput. Sci. 23, 1035–1066 (2012)
Currie, J.D., Saari, K.: Least periods of factors of infinite words. RAIRO Inform. Théor. App. 43, 165–178 (2009)
Ehrenfeucht, A., Silberger, D.M.: Periodicity and unbordered segments of words. Disc. Math. 26, 101–109 (1979)
Goč, D., Henshall, D., Shallit, J.: Automatic theorem-proving in combinatorics on words. In: Moreira, N., Reis, R. (eds.) CIAA 2012. LNCS, vol. 7381, pp. 180–191. Springer, Heidelberg (2012)
Graham, D., Knuth, D.E., Patashnik, O.: Concrete mathematics. A foundation for computer science, 2nd edn. Addison-Wesley Pub. Company (1994)
Harju, T., Nowotka, D.: Periodicity and Unbordered Words: A Proof of Duval’s Conjecture. J. ACM 54 (2007)
Holub, S., Saari, K.: On highly palindromic words. Disc. Appl. Math. 157, 953–959 (2009)
Guibert, O., Pergola, E.: Enumeration of vexillary involutions which are equal to their mirror/complement. Disc. Math. 224, 281–287 (2000)
Sapounakis, A., Tsikouras, P.: On k-colored Motzkin words. J. Integer Seq. 7 (2004)
Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences. The OEIS Foundation Inc., http://oeis.org/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rampersad, N., Rigo, M., Salimov, P. (2013). On the Number of Abelian Bordered Words. In: Béal, MP., Carton, O. (eds) Developments in Language Theory. DLT 2013. Lecture Notes in Computer Science, vol 7907. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38771-5_37
Download citation
DOI: https://doi.org/10.1007/978-3-642-38771-5_37
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38770-8
Online ISBN: 978-3-642-38771-5
eBook Packages: Computer ScienceComputer Science (R0)