Original title: Hvězdná výška
Translated title: Star height
Authors: Svoboda, Tomáš ; Holub, Štěpán (advisor) ; Žemlička, Jan (referee)
Document type: Bachelor's theses
Year: 2017
Language: eng
Abstract: [eng] [cze]
We present a certain family of languages and show that for those languages infinite hierarchy of star heights exists. The proof was first devised by Dejean and Schützenberger. More recently it was reformulated by Sakarovitch, who left some of the parts of the proof the the reader for more careful consideration. This thesis expands on those parts and provides more detailed proofs. We mainly focus on construction of rational expression with the star height of the given language. We also compare the star height and generalised star height and the difference in achieved results for those two similar concepts. Prezentujeme jistou rodinu jazyků a ukazujene, že pro tyto jazyky existuje nekonečná hierarchie hvězdných výšek. Důkaz byl poprvé proveden pány Dejeanem a Schützenbergerem. Nově byl přeformulován Sakarovitchem, který některé části přenechal čtenáři pro podrobnější prozkoumání. Tato práce rozvádí ony části a poskytuje podrobnější důkazy. Zejména se zaměřujeme na konstrukci racionálních výrazů s hvězdnou výškou daného jazyka. Také srovnáváme hvězdnou výšku a zobecněnou hvězdnou výšku a rozdíl v dosažených výsledcích pro tyto dva podobné koncepty.

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/92402

Permalink: http://www.nusl.cz/ntk/nusl-368909


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses