Seminár Ústavu informatiky

Prednáška

Alternujúca pamäť je uzavretá na doplnok a ďalšie simulácie v sublogaritmickej pamäti

prof. RNDr. Viliam Geffert, DrSc.
Ústav informatiky, PF UPJŠ

12. apríla 2017 (streda) o 12:45
SJ2S07 (3.16T), PF UPJŠ

Abstrakt

V [Ge1,Ge2], bol vyriešený po desaťročia otvorený problém. Bolo dokázané, že ASpace(s(n)) = co-ASpace(s(n)), a to bez použitia akýchkoľvek predpokladov o pamäťovej zložitosti s(n). Teda trieda jazykov, ktoré sa dajú rozpoznávať pomocou alternujúcich strojov vybavených pamäťou o veľkosti O(s(n)), je uzavretá na komplement, a to bez ohľadu na to, či funkcia s(n) rastie rýchlejšie ako log n alebo či sa pôvodný stroj môže dostať do nekonečného cyklu. Okrem toho bolo vyvinutých viacero ďalších nových simulácií pre ASpace(s(n)) pomocou deterministických a nedeterministických strojov so súčasným ohraničením na čas výpočtu a na použitú pamäť.

[Ge1] V.Geffert. Alternating demon space is closed under Complement and other simulations for sublogarithmic space. Proc. of International Conference on Developments in Language Theory, Lect. Notes Comput. Sci., vol. 9840, pp. 190-202, Springer-Verlag, 2016. (DLT 2016, July 25-28, 2016, Montréal, Canada)

[Ge2] V.Geffert: Alternating space is closed under complement and other simulations for sublogarithmic space, Information and Computation, Elsevier, 2017, Vol.253, pt.1, pp.163-178