Original title: Kvadratické rovnice na slovech
Translated title: Quadratic word equations
Authors: Olšák, Miroslav ; Holub, Štěpán (advisor) ; Stanovský, David (referee)
Document type: Bachelor's theses
Year: 2013
Language: cze
Abstract: [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)
Keywords: combinatorics on words; quadratic equations; simple exponential bound; jednoduše exponenciální mez; kombinatorika na slovech; kvadratické rovnice

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/56066

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


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