Enumerace ternárních balancovaných slov
| advisor: | prof. Ing. Edita Pelantová, CSc. |
| e-mail: | show e-mail |
| type: | bachelor thesis, master thesis |
| branch of study: | MI_MM, MINF |
| key words: | sturmovská slova, ternární balancovaná slova, enumerace faktorů |
| description: | Balancovaná slova hrají důležitou úlohu např. v navrhování výrobních schémat (viz téma Bc. práce s názvem Toyota problem), v diskretizaci spojitých geometrických útvarů pro účely jejich zobrazování na monitorech atp. Konstrukce balancovaných slov nad k prvkovou abecedou je dobře známa od roku 2000 (P. Hubert). Známý je rovněž počet balancovaných slov délky n nad dvouprvkovou abecedou (J. Berstel, M. Pacchiola). Analogicky výsledek není však znám pro víceprvkové abecedy. Cílem práce bude nastudovat konstrukci ternárních balancovaných slov a vytvořit program pro jejich generování. Seznámit se s různými důkazy enumerace binárních balancovaných slov. Na základě počítačového experimentu navrhnout horní a dolní odhady počtu ternárních balancovaných slov dané délky a pokusit se je odvodit. |
| references: | Arseny M. Shur: Languages with a Finite antidictionary: some growth Questions. Int. J. Found. Comput. Sci. 25(8): 937-954 (2014) Pascal Hubert: Suites équilibrées. Theor. Comput. Sci. 242(1-2): 91-108 (2000) Jean Berstel, Michel Pocchiola: A Geometric Proof of the Enumeration Formula for Sturmian Words. Int. J. Algebra Comput. 3(3): 349-356 (1993) |
| last update: | 07.09.2022 17:10:29 |
administrator for this page:
Ľubomíra Dvořáková | last update: 09/12/2011