Název: Kvadratické rovnice na slovech
Překlad názvu: Quadratic word equations
Autoři: Olšák, Miroslav ; Holub, Štěpán (vedoucí práce) ; Stanovský, David (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2013
Jazyk: cze
Abstrakt: [cze] [eng]
Práce se zabývá řešitelnosti kvadratických rovnic na slovech. V upravené podobě opakuje výsledky Robsona a Diekerta a navazuje na otázku jednoduše exponenciální meze na velikost nejkratšího řešení kvadratických rovnic. Kladná odpověď na tuto otázku by znamenala, že je řešitelnost kvadratických rovnic na slovech NP úplný problém. Hypotézu o jednoduše exponenciální mezi se dokázat nepodařilo, ale podařilo se například zúžit třídu rovnic, kterým je třeba se věnovat, a dále ukázat, že se stačí zabývat mezí pro nejkratší proměnnou. V závěru práce je ukázáno chování jisté konkrétní rovnice a dále vysvětlena dualita dvou přístupů ke kvadratickým soustavám. Powered by TCPDF (www.tcpdf.org) The article discuses satisfiability of quadratic word equations. It reproduces results of Robson and Diekert and explores the question about simple exponential bound of the shortest solution of quadratic word equations. The positive answer to this question would mean NP completeness of satisfiability of quadratic word equations. The simple exponential bound hypothesis was not solved but some results were given: for example a smaller class of equations which needs to be investigated or a proposition saying that it is sufficient to prove a bound of the smallest variable. At the end of this work the behavior of a particular equations is shown and afterwards the duality of two concepts of quadratic word equations handling is explained. Powered by TCPDF (www.tcpdf.org)
Klíčová slova: jednoduše exponenciální mez; kombinatorika na slovech; kvadratické rovnice; combinatorics on words; quadratic equations; simple exponential bound

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/56066

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-325345


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce