Seminar of Theoretical Computer Science - Šimon Sádovský (6.3.2020)
Friday 6.3.2020 at 11:00, room M/213
Šimon Sádovský:
Limited Automata: Properties, Complexity and Variants
Abstract:
When considering the well known Chomsky hierarchy, some inclusion results follow directly from the fact that one type of automata is some restriction of another: e.g. linearly bounded automata (LBA) are actually Turing machines with restricted memory, finite automata are LBA with prohibited rewrites, etc. More problematic is to see that context-free languages (CFL) are contained in context languages (CL), since push-down automata (PDA) are not just restricted version of LBA. It would be interesting to have some automata model which characterizes CFL and has the properties that it is a restricted version of LBA, and FA can be seen as a restricted version of this model. In the presentation we will talk about d-limited automata, which have this desired property. D-limited automata are LBA which can rewrite a given memory cell only during its first d visits. We will show main ideas of equivalence of push-down automata and d-limited automata and also talk about the deterministic version of d-limited automata.
Our talk is based on the paper: Pighizzini G.: Limited Automata: Properties, Complexity and Variants, DCFS 2019: p. 57-73
web: https://beda.dcs.fmph.uniba.sk/seminar