Seminár z teoretickej informatiky - Peter Kostolányi (12.10.2018)

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

08. 10. 2018 12.50 hod.
Od: Rastislav Královič

Prednášajúci: Peter Kostolányi

Názov: O sile deterministických automatov s váhami

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

Abstrakt:
Konečné automaty s váhami sú kvantitatívnym rozšírením klasických nedeterministických konečných automatov: namiesto rozoznávania jazykov realizujú funkcie (mocninové rady) priraďujúce slovám hodnoty z nejakého polokruhu. Doposiaľ sa skúmali dva varianty determinizmu v automatoch s váhami: sekvenčné a o niečo obmedzenejšie čisto sekvenčné automaty. Bolo pritom známe, že existujú polokruhy, nad ktorými sú sekvenčné automaty s váhami ostro slabšie, než nedeterministické automaty. Na prednáške dokážeme charakterizáciu polokruhov, nad ktorými sú čisto sekvenčné automaty s váhami rovnako silné ako nedeterministické automaty a čiastočnú charakterizáciu dokážeme aj pre sekvenčné automaty.
(Publikované v Inf. Process. Lett. 140, s. 42-47, 2018.)

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