Jste zde

Skákající konečné automaty

10. prosince 2012 jsem měl společně s prof. Medunou úvodní přednášku na studentské konferenci Language Theory With Applications 2012 na téma "Skákající konečné automaty". O čem tato přednáška byla, kde můžete zhlédnout (konečně zveřejněný) záznam a kde si lze stáhnout materiály se dozvíte v následujícím krátkém příspěvku.

O čem tato přednáška byla?

Přednáška vycházela z našeho společného článku Jumping Finite Automata, který nedávno vyšel v časopise International Journal of Foundations of Computer Science. Zavedli jsme v něm modifikaci konceptu konečného automatu, který nyní místo toho, aby četl vstupní pásku zleva doprava, symbol po symbolu, tak může po přečtení symbolu skočit na jakékoliv místo na pásce a pokračovat ve výpočtu odtud. Tato poměrně přirozená modifikace má však poměrně dalekosáhlé důsledky, ať co se týče přijímající síly, tak vlastností takto modifikovaných konečných automatů.

V přednášce jsme tuto modifikaci nejdříve vysvětlili a formálně definovali. Definici jsme pak ilustrovali na dvou příkladech. Následně jsme se vrhli na studium vlastností těchto automatů, a to konkrétně přijímající síly, konverzí, uzávěrových vlastností, omezení skoků doprava či doleva a různých počátečních konfigurací. Na závěr jsme shrnuli hlavní otevřené problémy a diskutovali toto téma s publikem.

Pokud vás téma přednášky zaujalo a budete mít večer chvilku čas, určitě mrkněte na záznam (viz níže). Abyste si přednášku užili, tak stačí, že víte, co je to a jak pracuje konečný automat a nebojíte se trochu matematična :).

Kde si můžu stáhnout záznam a doplňující materiály?

Tady:

Dále, pokud by to někoho zajímalo, tak část mých přednášek a prezentací je ke stažení zde (záznam je však jen z několika prezentací). Pokud vás něco zaujme, ozvěte se mi :).

Přidat komentář