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
Department of Information Systems FIT BUT
Degree Programme
Information Technology, Field of Study Information Systems
Files
Status
defended, grade A
Date
19 June 2017
Reviewer
Kučera Jiří, Ing., Ph.D.
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
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/"
}

Theses

Back to top