Seminár z teoretickej informatiky - Šimon Sádovský (6.3.2020)

v piatok 6.3.2020 o 11:00 hod. v miestnosti M/213

04. 03. 2020 08.30 hod.
Od: Rastislav Královič

Prednášajúci: Šimon Sádovský

Názov: Limited Automata: Properties, Complexity and Variants

Termín: 6.3.2020, 11:00 hod., M/213

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