Thesis Details

Výpočetní historie Turingových strojů a jejich generování gramatikami s rozptýleným kontextem

Master's Thesis Student: Kajan Dušan Academic Year: 2014/2015 Supervisor: Meduna Alexander, prof. RNDr., CSc.

English title

Computational Histories of Turing Machines and Their Generation by Scattered Context Grammars

Language

Czech

Abstract

The purpose of this thesis is to show a method, that would transform given Turing machine into propagating scattered context grammar, which language contains all valid computational histories of that particular Turing machine. Afterwards this thesis deals with questions arising from existence of such algorithm, especially in regards to the current knowledge about power of propagating scattered context grammars. Practical examples and implementation of proposed algorithm is also part of this thesis.

Keywords

scattered context grammars, propagating scattered context grammars,

theory of computation,  Turing machine, algorithm, Haskell,

computational history

Department

Department of Information Systems FIT BUT

Degree Programme

Information Technology, Field of Study Mathematical Methods in Information Technology

Files

Thesis text 592 kB

Status

defended, grade A

Date

24 June 2015

Reviewer

Soukup Ondřej, Ing.

Committee

Vojnar Tomáš, prof. Ing., Ph.D. (DITS FIT BUT), předseda
Burget Radek, doc. Ing., Ph.D. (DIFS FIT BUT), člen
Drahanský Martin, prof. Ing., Dipl.-Ing., Ph.D. (DITS FIT BUT), člen
Hrubý Martin, Ing., Ph.D. (DITS FIT BUT), člen
Rozinajová Viera, doc. Ing., Ph.D. (FIIT STU), člen
Ryšavý Ondřej, doc. Ing., Ph.D. (DIFS FIT BUT), člen

Citation

KAJAN, Dušan. Výpočetní historie Turingových strojů a jejich generování gramatikami s rozptýleným kontextem. Brno, 2015. Master's Thesis. Brno University of Technology, Faculty of Information Technology. 2015-06-24. Supervised by Meduna Alexander. Available from: https://www.fit.vut.cz/study/thesis/16787/

BibTeX

@mastersthesis{FITMT16787,
    author = "Du\v{s}an Kajan",
    type = "Master's thesis",
    title = "V\'{y}po\v{c}etn\'{i} historie Turingov\'{y}ch stroj\r{u} a  jejich generov\'{a}n\'{i} gramatikami s rozpt\'{y}len\'{y}m kontextem",
    school = "Brno University of Technology, Faculty of Information Technology",
    year = 2015,
    location = "Brno, CZ",
    language = "czech",
    url = "https://www.fit.vut.cz/study/thesis/16787/"
}

Theses