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

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