Restricted Restarting Automata
Omezené Restartovací Automaty
dizertační práce (OBHÁJENO)
Zobrazit/ otevřít
Trvalý odkaz
http://hdl.handle.net/20.500.11956/82615Identifikátory
SIS: 85460
Kolekce
- Kvalifikační práce [10693]
Autor
Vedoucí práce
Oponent práce
Kutrib, Martin
Průša, Daniel
Fakulta / součást
Matematicko-fyzikální fakulta
Obor
Teoretická informatika
Katedra / ústav / klinika
Katedra softwaru a výuky informatiky
Datum obhajoby
22. 9. 2015
Nakladatel
Univerzita Karlova, Matematicko-fyzikální fakultaJazyk
Angličtina
Známka
Prospěl/a
Klíčová slova (česky)
gramatická inference, přepisovací systémy, redukční analýza, restartovací automatyKlíčová slova (anglicky)
analysis by reduction, grammatical inference, restarting automata, string-rewriting systemsRestartovací automaty byly navrženy jako model pro redukční analýzu, která představuje lingvisticky motivovanou metodu pro kontrolu korektnosti věty. Dizertační práce zkoumá lokálně omezené modely restartovacích automatů, které (na rozdíl od obecných restartovacích automatů) smí upravovat obsah vstupní pásky jenom na základě lokálně omezeného kontextu. Studium omezených modelů se ukazuje jako jednodušší než studium obecných restartovacích automatů. Navíc se tyhle modely efektivně učí z pozitivních příkladů redukcí a jejich instrukce jsou srozumitelné i pro člověka. Powered by TCPDF (www.tcpdf.org)
Restarting automata were introduced as a model for analysis by reduction which is a linguistically motivated method for checking correctness of a sentence. The thesis studies locally restricted models of restarting automata which (to the contrary of general restarting automata) can modify the input tape based only on a limited context. The investigation of such restricted models is easier than in the case of general restarting automata. Moreover, these models are effectively learnable from positive samples of reductions and their instructions are human readable. Powered by TCPDF (www.tcpdf.org)