Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

Seminár z teoretickej informatiky - Viliam Geffert (6.11.2015)

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


02. 11. 2015 11.59 hod.
Od: Rastislav Královič

Prednášajúci: prof. RNDr. Viliam Geffert, DrSc. (UPJŠ Košice)

Názov: Popisná zložitosť Booleovských operácií na automatoch s ohraničenou výškou zásobníka

Termín: 6.11.2015, 11:00 hod., miestnosť M/213


Abstrakt:
We study the size-cost of Boolean operations on constant height nondeterministic pushdown automata, i.e. on pushdown automata with a constant limit on the size of the pushdown. For intersection, we show an exponential simulation and prove that the exponential blowup is necessary. For union, instead, we provide a linear trade-off while, for complement, we have a double-exponential gap.

Výsledky boli prezentované na konferencii CSR'2013, spoluatori Z. Bednárová (UPJŠ Košice), C. Mereghetti, B. Palano (Univerzita Milano)

web: http://kedrigern.dcs.fmph.uniba.sk/STI2
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php