Seminár Ústavu informatiky

Prednáška

New Results on the Minimum Amount of Useful Space

RNDr. Zuzana Bednárová, PhD.
Ústav informatiky, PF UPJŠ

1. marca 2017 (streda) o 13:10
SJ2S07 (3.16T), PF UPJŠ

Abstrakt

We present several new results on minimal space requirements to recognize a nonregular language: (i) realtime nondeterministic Turing machines can recognize a nonregular unary language within weak log log n space, (ii) log log n is a tight space lower bound for accepting general nonregular languages on weak realtime pushdown automata, (iii) there exist unary nonregular languages accepted by realtime alternating one-counter automata within weak log n space, (iv) there exist nonregular languages accepted by two-way deterministic pushdown automata within strong log log n space.