Seminár z teoretickej informatiky - Viliam Geffert (6.11.2015)
v piatok 6.11.2015 o 11:00 hod. v miestnosti M/213
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