Star height

• Název práce v češtině: Hvězdná výška
• Název v anglickém jazyce: Star height
• Akademický rok vypsání: 2016/2017
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: doc. Mgr. Štěpán Holub, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 10.10.2016
• Datum zadání: 29.06.2017
• Datum potvrzení stud. oddělením: 17.07.2017
• Datum a čas obhajoby: 14.09.2017 00:00
• Datum odevzdání elektronické podoby: 21.07.2017
• Datum odevzdání tištěné podoby: 21.07.2017
• Datum proběhlé obhajoby: 14.09.2017
• Oponenti: doc. Mgr. et Mgr. Jan Žemlička, Ph.D.

Zásady pro vypracování

Student se seznámí s problémem hvězdné výšky regulárních jazyků. Popíše konstrukci jazyka s danou hvězdnou výškou.

Seznam odborné literatury

Lawrence C. Eggan. Transition graphs and the star-height of regular events Michigan Mathematical Journal 10 (4):385–397, 1963.
F. Dejean and M. P. Schützenberger. On a Question of Eggan. Information and Control, 9:23–25, 1966.
Jacques Sakarovitch. Elements of Automata Theory, Cambridge university press (2009).

Předběžná náplň práce

Jedná se o starý a zřejmě těžký problém týkající se struktury regulárních množin. Formulace problému a některé základní poznatky jsou ovšem velmi jednoduché, což činí problém atraktivním. Konkrétně se jedná o otázku: lze každý regulární výraz přepsat tak, aby obsahoval jen omezený počet do sebe vnořených Kleenových hvězd?