Semilineární množiny

• Název práce v češtině: Semilineární množiny
• Název v anglickém jazyce: Semilinear sets
• Klíčová slova: semilineární množina lineární množina bezkontextová gramatika bezkontextový jazyk
• Klíčová slova anglicky: semilinear set linear set context-free grammar context-free language
• Akademický rok vypsání: 2015/2016
• Typ práce: bakalářská práce
• Jazyk práce: češ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í: 22.10.2015
• Datum zadání: 29.10.2015
• Datum potvrzení stud. oddělením: 07.12.2015
• Datum a čas obhajoby: 13.09.2016 00:00
• Datum odevzdání elektronické podoby: 27.07.2016
• Datum odevzdání tištěné podoby: 27.07.2016
• Datum proběhlé obhajoby: 13.09.2016
• Oponenti: doc. Mgr. et Mgr. Jan Žemlička, Ph.D.

Zásady pro vypracování

Student popíše důkaz, že semilineární množiny jsou uzavřeny na booleovské operace (sjednocení, průnik, komplement) a vysvětlí souvislost mezi semilineárními množinami a bezkontextovými jazyky.

Seznam odborné literatury

Ginsburg, Seymour (1966), The Mathematical Theory of Context-free Languages, New York, San Francisco, St. Louis, Toronto, London, Sydney: McGraw-Hill

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

Semilineární množiny celočíselných bodů ležících v konečných sjednoceních výseků euklidova prostoru. Jedná se tedy o téma blízké lineární algebře, s kombinatorickými aspekty plynoucími z faktu, že se jedná pouze o celočíselné body. Semilineární množiny hrají důležitou roli v teorii bezkontextových jazyků, ale tato souvislost není pro práci zásadní.