Thesis Details
Deep Pushdown Automata and Their Restricted Versions
Master's Thesis
Student: Charvát Lucie
Academic Year: 2016/2017
Supervisor: Meduna Alexander, prof. RNDr., CSc.
Czech title
Deep Pushdown Automata and Their Restricted Versions
Language
English
Abstract
For a positive integer n, n-expandable deep pushdown automata always contain no more than n occurrences of non-input symbols in their pushdowns during any compilation. As its main result, the present thesis demonstrates that those automata are as powerful as the same automata with #, which always appears solely as the pushdown bottom, and a single pushdown non-input symbol. An infinite hierarchy of language families follows from this result.
Keywords
Deep pushdown automata, pushdown alphabet reduction
Department
Degree Programme
Information Technology, Field of Study
Information Systems
Files
Status
defended, grade A
Date
19 June 2017
Reviewer
Committee
Kolář Dušan, doc. Dr. Ing. (DIFS FIT BUT), předseda
Burget Radek, doc. Ing., Ph.D. (DIFS FIT BUT), člen
Hruška Tomáš, prof. Ing., CSc. (DIFS FIT BUT), člen
Janoušek Vladimír, doc. Ing., Ph.D. (DITS FIT BUT), člen
Matoušek Petr, doc. Ing., Ph.D., M.A. (DIFS FIT BUT), člen
Polášek Ivan, doc. Ing., Ph.D. (FIIT STU), člen
Burget Radek, doc. Ing., Ph.D. (DIFS FIT BUT), člen
Hruška Tomáš, prof. Ing., CSc. (DIFS FIT BUT), člen
Janoušek Vladimír, doc. Ing., Ph.D. (DITS FIT BUT), člen
Matoušek Petr, doc. Ing., Ph.D., M.A. (DIFS FIT BUT), člen
Polášek Ivan, doc. Ing., Ph.D. (FIIT STU), člen
Citation
CHARVÁT, Lucie. Deep Pushdown Automata and Their Restricted Versions. Brno, 2017. Master's Thesis. Brno University of Technology, Faculty of Information Technology. 2017-06-19. Supervised by Meduna Alexander. Available from: https://www.fit.vut.cz/study/thesis/6086/
BibTeX
@mastersthesis{FITMT6086, author = "Lucie Charv\'{a}t", type = "Master's thesis", title = "Deep Pushdown Automata and Their Restricted Versions", school = "Brno University of Technology, Faculty of Information Technology", year = 2017, location = "Brno, CZ", language = "english", url = "https://www.fit.vut.cz/study/thesis/6086/" }